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

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

1、B樹和B+樹

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

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

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

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

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

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

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

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

2、原因分析

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

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

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

3、從全表掃描方面來看：因為，B+樹的葉子節(jié)點存儲所有數(shù)據(jù)，所以B+樹的全局掃描能力更強一些，因為它只需要掃描葉子節(jié)點。而B樹需要遍歷整個樹。

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

3、總結(jié)

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

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

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

最新評論