快捷導(dǎo)航

解讀MySQL中一個B+樹能存儲多少數(shù)據(jù)

更新時間：2023年02月14日 16:00:24 作者：碳基生物與硅

這篇文章主要介紹了解讀MySQL中一個B+樹能存儲多少數(shù)據(jù)的問題，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教

MySQL中一個B+樹能存儲多少數(shù)據(jù)

MySQL中InnoDB頁的大小默認(rèn)是16k。也可以自己進行設(shè)置。（計算機在存儲數(shù)據(jù)的時候，最小存儲單元是扇區(qū)，一個扇區(qū)的大小是 512 字節(jié)，而文件系統(tǒng)（例如 XFS/EXT4）最小單元是塊，一個塊的大小是 4KB。

InnoDB 引擎存儲數(shù)據(jù)的時候，是以頁為單位的，每個數(shù)據(jù)頁的大小默認(rèn)是 16KB，即四個塊。）

在B+樹中，一個結(jié)點就是一頁。非葉子結(jié)點由主鍵值和一個指向下一層的地址的指針組成的組合組成。葉子結(jié)點中由一組鍵值對和一個指向該層下一頁的指針組成，鍵值對存儲的主鍵值和數(shù)據(jù)。

由存儲結(jié)構(gòu)，可以大概計算出一個B+樹能存儲的數(shù)據(jù)數(shù)量。

指針在InnoDB中為6字節(jié)，設(shè)主鍵的類型是bigint，占8字節(jié)。一組就是14字節(jié)。

計算出一個非葉子結(jié)點可以存儲16 * 1024 / 14 = 1170個索引指針。

假設(shè)一條數(shù)據(jù)的大小是1KB，那么一個葉子結(jié)點可以存儲16條數(shù)據(jù)。

得出兩層B+樹可以存儲1170 x 16 = 18720 條數(shù)據(jù)。

三層B+樹可以存儲1170 x 1170 x 16 = 21902400條數(shù)據(jù)。

B樹和B+樹都是應(yīng)用在數(shù)據(jù)庫索引上，可以認(rèn)為是m叉的多路平衡查找樹，但是理論上講，二叉樹的查找速度和比較次數(shù)都更小，為什么不用二叉樹呢？

這是因為我們要考慮磁盤IO的影響，它相對于內(nèi)存來說是很慢的，數(shù)據(jù)庫索引是存儲在磁盤上的，當(dāng)數(shù)據(jù)量很大時，就不能把整個索引全部加載到內(nèi)存中，只能逐一加載每一個磁盤頁（對應(yīng)索引樹的節(jié)點）。

所以我們要減少IO的次數(shù)，對于樹來說，IO次數(shù)就是樹的高度，而“矮胖”就是B樹的特征之一。

B樹的特征：

B+樹是B樹的變體，是一種查詢性能更好的B樹。B+樹是一種平衡查找樹。在B+樹中，所有記錄節(jié)點都是按鍵值的大小順序存放在同一層的葉節(jié)點中，各葉結(jié)點指針進行連接。

B+樹的特征：

有n棵子樹的非葉子結(jié)點中含有n個關(guān)鍵字（b樹是n-1個），這些關(guān)鍵字不保存數(shù)據(jù)，只用來索引，所有數(shù)據(jù)都保存在葉子節(jié)點（b樹是每個關(guān)鍵字都保存數(shù)據(jù)）。
所有的葉子結(jié)點中包含了全部關(guān)鍵字的信息，及指向含這些關(guān)鍵字記錄的指針，且葉子結(jié)點本身依關(guān)鍵字的大小自小而大順序鏈接。
所有的非葉子結(jié)點可以看成是索引部分，結(jié)點中僅含其子樹中的最大（或最?。╆P(guān)鍵字。
通常在b+樹上有兩個頭指針，一個指向根結(jié)點，一個指向關(guān)鍵字最小的葉子結(jié)點。
同一個數(shù)字會在不同節(jié)點中重復(fù)出現(xiàn)，根節(jié)點的最大元素就是b+樹的最大元素。

B樹的中間節(jié)點保存節(jié)點和數(shù)據(jù)，B+樹的中間節(jié)點不保存數(shù)據(jù)，數(shù)據(jù)保存在葉子節(jié)點中；所以磁盤頁能容納更多的節(jié)點元素，更“矮胖”；
B樹的查找要只要匹配到元素，就不用管在什么位置，B+樹查找必須匹配到葉子節(jié)點，所以B+樹查找更穩(wěn)定；
對于范圍查找到說，B樹要從頭到尾查找，而B+樹只需要在一定的范圍內(nèi)的葉子節(jié)點中查找就可以；
B+樹的葉子節(jié)點通過指針連接，從左到右順序排列；
B+樹的非葉子節(jié)點與葉子節(jié)點冗余；