? ? ? ?我們都知道MySQL底層數(shù)據(jù)結(jié)構(gòu)是選用的B+樹(shù)，那為什么不用紅黑樹(shù)，或者其他什么數(shù)據(jù)結(jié)構(gòu)呢？

????????紅黑樹(shù)是一種自平衡二叉查找樹(shù)，Java8中的hashmap就用到紅黑樹(shù)來(lái)優(yōu)化它的查詢效率，可見(jiàn)，紅黑樹(shù)的查詢效率還是比較高的，但是為什么MySQL的底層不用紅黑樹(shù)而用B+數(shù)呢？

????????下圖是紅黑樹(shù)依次插入1,2,3,4,5,6之后的情況：

?然后再在上面的紅黑樹(shù)中插入7：

???????可以看到，盡管紅黑樹(shù)經(jīng)過(guò)了自平衡，數(shù)據(jù)整體仍然偏向樹(shù)的右側(cè)，如果繼續(xù)添加更多數(shù)據(jù)，添加的數(shù)據(jù)上百萬(wàn)、千萬(wàn)之后，樹(shù)的層級(jí)將會(huì)非常高，查詢時(shí)每多經(jīng)過(guò)一層，就會(huì)多進(jìn)行一次io，樹(shù)的層級(jí)多了之后查找效率就會(huì)很慢。這個(gè)時(shí)候可能就會(huì)有人問(wèn)了，那為什么不用平衡性更好的AVL樹(shù)呢？

????????AVL樹(shù)在一次插入1,2,3,4,5,6,7之后是這樣的：

? ? ? ? ?的確變順眼了很多，樹(shù)的層數(shù)也變少了，可AVL仍然沒(méi)有解決根本問(wèn)題，當(dāng)數(shù)據(jù)量達(dá)到百萬(wàn)、千萬(wàn)之后，樹(shù)的層數(shù)仍然會(huì)比較大，先不說(shuō)AVL樹(shù)維護(hù)平衡所需的代價(jià)，單論AVL樹(shù)的層數(shù)就無(wú)法達(dá)到我們的要求。

? ? ? ? 那么什么樣的數(shù)據(jù)結(jié)構(gòu)可以讓數(shù)據(jù)量達(dá)到百萬(wàn)，千萬(wàn)，甚至更大的體量時(shí)，層數(shù)仍然很小呢？很顯然，想要減少層數(shù)，就必須要讓每層儲(chǔ)存的數(shù)據(jù)數(shù)更多，二叉樹(shù)不管平衡性再好也只能做到每個(gè)節(jié)點(diǎn)有兩個(gè)分叉，每層的數(shù)據(jù)量從數(shù)據(jù)結(jié)構(gòu)被限制住了，那么，我們就不能從二叉樹(shù)中選。所以這個(gè)時(shí)候B樹(shù)的優(yōu)勢(shì)就體現(xiàn)出來(lái)了，B樹(shù)每個(gè)節(jié)點(diǎn)可以存儲(chǔ)多個(gè)元素，每個(gè)元素之間可以都可以擁有一個(gè)分叉，下圖是B樹(shù)每個(gè)節(jié)點(diǎn)最多可以存儲(chǔ)3個(gè)元素的情況：

?????????可以看到樹(shù)的層級(jí)減小到兩層，如果說(shuō)每次每個(gè)節(jié)點(diǎn)最多可以存儲(chǔ)的元素個(gè)數(shù)足夠大，那么就算數(shù)據(jù)量達(dá)到上千萬(wàn)的量級(jí)，也可以將樹(shù)的層級(jí)控制在一個(gè)可以接受的范圍內(nèi)。

????????但B樹(shù)還有一個(gè)問(wèn)題，下圖展示的是B樹(shù)層級(jí)達(dá)到三層時(shí)的情況：

?????????如果現(xiàn)在我需要取出5-10號(hào)元素，當(dāng)我通過(guò)層層查詢，找到5號(hào)元素，然后發(fā)現(xiàn)其他元素不在這個(gè)節(jié)點(diǎn)，還需要通過(guò)局部中序遍歷查詢其他元素，找到7之后還需如此操作找到8,9,10，這又會(huì)增加io次數(shù)，所以也就有了B+樹(shù)。

? ? ? ? B+樹(shù)是對(duì)B樹(shù)的優(yōu)化，主要是從兩個(gè)地方進(jìn)行優(yōu)化的：

? ? ? ? 第一個(gè)優(yōu)化是在每個(gè)葉子節(jié)點(diǎn)之間加上了一個(gè)雙向指針，指向相鄰節(jié)點(diǎn)，這樣就解決了剛才的范圍查詢問(wèn)題，范圍查詢?nèi)绻缌硕鄠€(gè)節(jié)點(diǎn)，就可以通過(guò)這個(gè)雙向指針快速找到相鄰節(jié)點(diǎn)，而不需要通過(guò)局部的中序遍歷，從而減少了io次數(shù)。下圖演示的是B+樹(shù)：

? ? ? ?但如果要找的元素不在葉子節(jié)點(diǎn)上呢？別擔(dān)心，B+樹(shù)的另一個(gè)優(yōu)化就是的葉子節(jié)點(diǎn)包含了這顆樹(shù)的所有元素！B+樹(shù)的非葉子節(jié)點(diǎn)不再保存元素的data數(shù)據(jù)或者指針了，只是作為冗余的索引構(gòu)成完整的B+樹(shù)來(lái)方便查詢。可以看到上圖的15號(hào)元素不僅僅存在于非葉子節(jié)點(diǎn)中，也存在于葉子節(jié)點(diǎn)中。這樣的設(shè)計(jì)雖然帶來(lái)了很多冗余的索引，但是卻讓范圍查詢時(shí)不再需要向上查找非葉子節(jié)點(diǎn)了，而且每一層可以保存的索引數(shù)量變多了，讓數(shù)據(jù)庫(kù)每次io可以查詢到更多的索引元素，畢竟在正常情況下，數(shù)據(jù)占的空間比索引占的空間要大很多。（需要注意的是，InnoDB和MyISAM引擎雖然都是用的B+樹(shù)，但I(xiàn)nnoDB的聚簇索引和數(shù)據(jù)是保存在一起的，而MyISAM是將聚簇索引和相應(yīng)數(shù)據(jù)的指針保存在一起的，索引和數(shù)據(jù)是分開(kāi)的。MyISAM引擎下的B+樹(shù)也只有葉子節(jié)點(diǎn)才保存數(shù)據(jù)的指針）

? ? ? ? 由上面的分析我們可以知道，選用B+樹(shù)作為MySQL的底層是為了減少io次數(shù)，那我們?yōu)槭裁床恢苯訕O端一點(diǎn)，使用hash來(lái)保存數(shù)據(jù)或者索引呢？其實(shí)MySQL確實(shí)支持hash類型的索引。

? ? ? ? 但是hash索引一般都不用，主要是因?yàn)閔ash索引的儲(chǔ)存的是hash碼，儲(chǔ)存的順序與索引列的值大小無(wú)關(guān)，所以只有在進(jìn)行精確查找時(shí)hash索引才能生效，范圍查詢時(shí)會(huì)進(jìn)行全表掃描。同時(shí)，如果表中的數(shù)據(jù)量非常大的話，發(fā)生hash碰撞的次數(shù)會(huì)增多，單個(gè)查找的效率不一定比B+樹(shù)高。

? ? ? ? 簡(jiǎn)單總結(jié)一下，B+樹(shù)相比其他樹(shù)來(lái)說(shuō)，每個(gè)節(jié)點(diǎn)可以存儲(chǔ)更多元素，可以大大減少查詢時(shí)需要的io次數(shù)，非葉子節(jié)點(diǎn)不存儲(chǔ)數(shù)據(jù)或指針的設(shè)計(jì)可以提高每個(gè)節(jié)點(diǎn)存儲(chǔ)元素的數(shù)量，葉子節(jié)點(diǎn)具有的雙向指針可以提高范圍查詢的效率。

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

最新評(píng)論