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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

B樹的特征：

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

B+樹的特征：

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