快捷導(dǎo)航

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

B樹(shù)

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

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

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

B樹(shù)的特征：

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

B+樹(shù)

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

B+樹(shù)的特征：

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

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

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