B+樹和B/B-樹的區別？Mysql為啥用B+樹來做索引？

程序編寫夢想

這是我組建的一棵平衡二叉樹，查找效果比較理想，但是也有不理想的情況，比如下面二種情況：

像這樣二種情況，查找效率就低非常多了，時間複雜度是O(n)。

像第一種平衡二叉樹在mysql中也有很大的不足之處：隨著表中數據的增加，二叉樹的深度將會非常大，這樣導致查找的次數非常多，上面我們提到索引是存儲在硬盤上的，如果樹的深度太大的話，性能將會非常的低下。

針對二叉樹的這種缺點，科學家們引進了多叉樹，如下面場景：

多叉樹的優點就是極大的減少了樹的深度，我們下面要講的B+和B樹就是多叉樹。四、B/B-樹介紹

B樹 英文名是Balance Tree， 全名是平衡多路搜索樹。B樹的結構圖如下：

這裏的B樹，我不可能畫太多數據，只能給大家看看大體樣子。3層深度的B樹大約能存儲100萬的數據。深度減少能極大的減少磁盤讀取次數，雖然每個節點比較次數不少，但是如果把每個節點的數據讀到內存中比較，那這個比較時間就可以忽略不計了。所以用B樹來存儲對MySQL來說是非常合適的。

B樹有以下特點：1.所有鍵值分布在整顆樹中（索引值和具體data都在每個節點裏）；

2.任何一個關鍵字出現且只出現在一個結點中；

3.搜索有可能在非葉子結點結束（最好情況O(1)就能找到數據）；

4.在關鍵字全集內做一次查找,性能逼近二分查找；

5.所有葉子節點位於同一層。五、B+樹介紹

B+樹是B樹的升級版，結構圖如下：

B+樹相對於B樹有以下特點：1.所有關鍵字都會在在葉子節點出現,

2.內部節點(非葉子節點)不存儲數據，數據只在葉子節點存儲

3.所有葉子結點構成了一個鏈指針，而且所有的葉子節點按照順序排列。

那B+樹比B樹有什麼優勢呢？

每一層更寬，更胖，存儲的數據更多。因為B+樹只存儲關鍵字，而不存儲多餘data.所以B+樹的每一層相比B樹能存儲更多節點。

所有的節點都會在葉子節點上出現，查詢效率更穩定。因為B+樹節點上沒有數據，所以要查詢數據就必須到葉子節點上，所以查詢效率比B樹穩定。而在 B 樹中，非葉子節點也會存儲數據，這樣就會造成查詢效率不穩定的情況，有時候訪問到了非葉子節點就可以找到關鍵字，而有時需要訪問到葉子節點才能找到關鍵字。

查詢效率比B樹高。因為B+樹更矮，更胖，所以和磁盤交互的次數比B樹更少，而且B+樹通過底部的鏈表也可以完成遍曆，但是B樹需要找到每個節點才能遍曆，所以B+樹效率更高。

總體來說，B+樹因為更矮更胖能存儲更多數據、效率穩定，讀寫磁盤次數少，比B-樹效率更高，據統計，一棵深度為3的B+樹能存儲2000萬以上條數據。所以最終選擇了B+樹。結尾

好了，就介紹到這裏吧，關注我，每天更新優質內容。