More  

小編的世界 優質文選 資料

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


2020年12月26日 - 資料小編  
   

程序編寫夢想

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

像這樣二種情況,查找效率就低非常多了,時間複雜度是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+樹。結尾

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

  大家在看