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

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

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

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

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

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

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

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

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

????????但B樹還有一個問題，下圖展示的是B樹層級達(dá)到三層時的情況：

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

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

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

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

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

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

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

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

最新評論