目錄

• MySQL中一個B+樹能存儲多少數(shù)據(jù)
• MySQL聚簇索引的存儲結(jié)構(gòu)
• MySQL中B樹與B+樹的區(qū)別
• B樹
• B+樹
• B樹與B+樹的區(qū)別
• 總結(jié)

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

MySQL聚簇索引的存儲結(jié)構(gòu)

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

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

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

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

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

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

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

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

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

MySQL中B樹與B+樹的區(qū)別

B樹

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

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

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

B樹的特征：

• 關(guān)鍵字集合分布在整顆樹中；
• 任何一個關(guān)鍵字出現(xiàn)且只出現(xiàn)在一個結(jié)點(diǎn)中；
• 搜索有可能在非葉子結(jié)點(diǎn)結(jié)束；
• 其搜索性能等價于在關(guān)鍵字全集內(nèi)做一次二分查找；

B+樹

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

B+樹的特征：

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

B樹與B+樹的區(qū)別

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

總結(jié)

以上為個人經(jīng)驗(yàn)，希望能給大家一個參考，也希望大家多多支持。