一位6年經(jīng)驗(yàn)的小伙伴去字節(jié)面試的時(shí)候被問到這樣一個(gè)問題，為什么MySQL索引結(jié)構(gòu)要采用B+樹？這位小伙伴從來就沒有思考過這個(gè)問題。只因?yàn)楝F(xiàn)在都這么卷，后面還特意查了很多資料，他也希望聽聽我的見解。

另外，我花了1個(gè)多星期把往期的面試題解析配套文檔準(zhǔn)備好了，一共有10萬字，想獲取的小伙伴可以在我的煮葉簡介中找到。

1、B樹和B+樹

一般來說，數(shù)據(jù)庫的存儲(chǔ)引擎都是采用B樹或者B+樹來實(shí)現(xiàn)索引的存儲(chǔ)。首先來看B樹，如圖所示。

B樹是一種多路平衡樹，用這種存儲(chǔ)結(jié)構(gòu)來存儲(chǔ)大量數(shù)據(jù)，它的整個(gè)高度會(huì)相比二叉樹來說，會(huì)矮很多。

而對(duì)于數(shù)據(jù)庫而言，所有的數(shù)據(jù)都將會(huì)保存到磁盤上，而磁盤I/O的效率又比較低，特別是在隨機(jī)磁盤I/O的情況下效率更低。

所以 高度決定了磁盤I/O的次數(shù)，磁盤I/O次數(shù)越少，對(duì)于性能的提升就越大，這也是為什么采用B樹作為索引存儲(chǔ)結(jié)構(gòu)的原因，如圖所示。

而MySQL的InnoDB存儲(chǔ)引擎，它用了一種增強(qiáng)的B樹結(jié)構(gòu)，也就是B+樹來作為索引和數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)。

相比較于B樹結(jié)構(gòu)來說，B+樹做了兩個(gè)方面的優(yōu)化，如圖所示。

1、B+樹的所有數(shù)據(jù)都存儲(chǔ)在葉子節(jié)點(diǎn)，非葉子節(jié)點(diǎn)只存儲(chǔ)索引。

2、葉子節(jié)點(diǎn)中的數(shù)據(jù)使用雙向鏈表的方式進(jìn)行關(guān)聯(lián)。

2、原因分析

我認(rèn)為，MySQL索引結(jié)構(gòu)采用B+樹，有以下4個(gè)原因：

1、從磁盤I/O效率方面來看：B+樹的非葉子節(jié)點(diǎn)不存儲(chǔ)數(shù)據(jù)，所以樹的每一層就能夠存儲(chǔ)更多的索引數(shù)量，也就是說，B+樹在層高相同的情況下，比B樹的存儲(chǔ)數(shù)據(jù)量更多，間接會(huì)減少磁盤I/O的次數(shù)。

2、從范圍查詢效率方面來看：在MySQL中，范圍查詢是一個(gè)比較常用的操作，而B+樹的所有存儲(chǔ)在葉子節(jié)點(diǎn)的數(shù)據(jù)使用了雙向鏈表來關(guān)聯(lián)，所以B+樹在查詢的時(shí)候只需查兩個(gè)節(jié)點(diǎn)進(jìn)行遍歷就行，而B樹需要獲取所有節(jié)點(diǎn)，因此，B+樹在范圍查詢上效率更高。

3、從全表掃描方面來看：因?yàn)?，B+樹的葉子節(jié)點(diǎn)存儲(chǔ)所有數(shù)據(jù)，所以B+樹的全局掃描能力更強(qiáng)一些，因?yàn)樗恍枰獟呙枞~子節(jié)點(diǎn)。而B樹需要遍歷整個(gè)樹。

4、從自增ID方面來看：基于B+樹的這樣一種數(shù)據(jù)結(jié)構(gòu)，如果采用自增的整型數(shù)據(jù)作為主鍵，還能更好的避免增加數(shù)據(jù)的時(shí)候，帶來葉子節(jié)點(diǎn)分裂導(dǎo)致的大量運(yùn)算的問題。

3、總結(jié)

總體來說，我認(rèn)為技術(shù)方案的選型，更多的要根據(jù)具體的業(yè)務(wù)場景來決定，并不一定是說B+樹就是最好的選擇，就像MongoDB里面采用B樹結(jié)構(gòu)，本質(zhì)上來說，其實(shí)是關(guān)系型數(shù)據(jù)庫和非關(guān)系型數(shù)據(jù)庫的差異。

以上就是我對(duì)為什么MySQL索引結(jié)構(gòu)采用B+樹 的理解。

到此這篇關(guān)于淺析MySQL索引結(jié)構(gòu)采用B+樹的問題的文章就介紹到這了,更多相關(guān)mysql 索引B+樹內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論