快捷導(dǎo)航

淺析MySQL索引結(jié)構(gòu)采用B+樹(shù)的問(wèn)題

更新時(shí)間：2022年06月21日 14:31:51 作者：Tom彈架構(gòu)

數(shù)據(jù)庫(kù)的存儲(chǔ)引擎都是采用B樹(shù)或者B+樹(shù)來(lái)實(shí)現(xiàn)索引的存儲(chǔ),總體來(lái)說(shuō)，我認(rèn)為技術(shù)方案的選型，更多的要根據(jù)具體的業(yè)務(wù)場(chǎng)景來(lái)決定，并不一定是說(shuō)B+樹(shù)就是最好的選擇，就像MongoDB里面采用B樹(shù)結(jié)構(gòu),本文介紹我對(duì)MySQL索引結(jié)構(gòu)采用B+樹(shù)的理解

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

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

1、B樹(shù)和B+樹(shù)

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

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

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

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

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

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

1、B+樹(shù)的所有數(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+樹(shù)，有以下4個(gè)原因：

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

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

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

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

3、總結(jié)

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

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

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

您可能感興趣的文章: