從二叉查找樹到 B* 樹，一文搞懂搜索樹的演進！

在計算機中有一些數(shù)據(jù)結(jié)構(gòu)總是與數(shù)據(jù)的查找分不開，比如二叉查找樹（Binary Search Tree）、紅黑樹、B樹、B+樹等等數(shù)據(jù)結(jié)構(gòu)。你可曾想過為什么會有這么多種用于搜索的數(shù)據(jù)結(jié)構(gòu)？為什么紅黑樹結(jié)構(gòu)在計算機中內(nèi)存中被廣泛應(yīng)用？為什么MySQL多種數(shù)據(jù)引擎都選擇B+樹作為其索引實現(xiàn)？為什么Redis要使用跳表？

帶著這些問題，這篇文章我們探討一下這些數(shù)據(jù)結(jié)構(gòu)在實際中的應(yīng)用以及針對于存在的問題產(chǎn)生的演進。

二分查找

對于查找數(shù)據(jù)，不得不提的一種基礎(chǔ)算法就是二分法，很多數(shù)據(jù)結(jié)構(gòu)的查找算法核心思想都是二分法，其查找效率也經(jīng)常會用來和二分法來做對比。二分法的時間復(fù)雜度為**O(logN)**，這是一個非常優(yōu)秀的時間復(fù)雜度，其效率僅次于常數(shù)時間復(fù)雜度 **O(1)**。

二分查找的實現(xiàn)思路是這樣的：

1. 對數(shù)據(jù)集進行排序
2. 找到數(shù)據(jù)集的中間節(jié)點，判斷是否為查找的值，等于直接返回。
3. 根據(jù)與中間節(jié)點大小的比較結(jié)果，確定收縮查找區(qū)間范圍是中間節(jié)點的左邊還是右邊。
4. 重復(fù)上述 2、3 過程繼續(xù)查找。

從其實現(xiàn)思路來看，有兩個點很重要：一是可以保證數(shù)據(jù)的有序性，二是適合進行數(shù)據(jù)分段存儲，方便縮小區(qū)間查找。所以根據(jù)這種思路，演化出了兩個不同的路線，樹和跳表兩種數(shù)據(jù)結(jié)構(gòu)。

二叉搜索樹BST

二叉搜索樹(BST，Binary Search Tree)（又叫二叉查找樹）是一棵空樹，或者是具有下列性質(zhì)的二叉樹：

• 若它的左子樹不空，則左子樹上所有結(jié)點的值均小于它的根結(jié)點的值
• 若它的右子樹不空，則右子樹上所有結(jié)點的值均大于它的根結(jié)點的值
• 它的左、右子樹也分別為二叉排序樹。

二叉搜索樹的問題

二叉搜索樹符合了使用二分法查詢數(shù)據(jù)的要求，但是有個問題：因為插入順序的不同，二叉樹的高度不穩(wěn)定，極端情況下可能變成鏈表（就是插入的數(shù)據(jù)是有序的，遞增或者遞減）。這就成了線性查詢，時間復(fù)雜度最多變成O(n)，查詢效率不穩(wěn)定。

為了解決這個問題，就產(chǎn)生了各種樹的平衡算法，保證樹的節(jié)點高度不會差太多。所以就有了AVL樹（平衡二叉樹）和紅黑樹等新的數(shù)據(jù)結(jié)構(gòu)。

AVL樹

平衡二叉樹全稱叫做平衡二叉搜索（排序）樹，AVL樹是最早的平衡二叉樹之一。

為了解決一般的二叉搜索樹存在的問題，即根節(jié)點到葉子結(jié)點的高度相差太多，查詢效率不問題，并且極端情況有成為鏈表的可能。所以AVL樹具有以下特點：

• 它是一棵空樹或它的左右兩個子樹的高度差的絕對值不超過1，
• 左右兩個子樹 也都是一棵平衡二叉樹。

在AVL樹中，任何節(jié)點的兩個子樹的高度最大差別為 1 ，所以它也被稱為平衡二叉樹 。

AVL樹查找、插入和刪除在平均和最壞情況下都是O(LogN)。

AVL 什么意思 ？AVL 是大學(xué)教授 G.M. Adelson-Velsky 和 E.M. Landis 名稱的縮寫，他們提出的平衡二叉樹的概念，為了紀念他們，將 平衡二叉樹 稱為 AVL樹。

與普通二叉搜索樹的區(qū)別的是，它在插入和刪除節(jié)點的時候，會根據(jù)需要進行左旋或者右旋，來保證二叉樹的平衡，示意圖如下。這不是本文的討論重點，感興趣自己可以研究。

AVL樹的問題

AVL樹高度的平衡情況固然很好，但這是有代價的。為了維持平衡，其旋轉(zhuǎn)是非常耗時的。

AVL實現(xiàn)平衡的關(guān)鍵在于旋轉(zhuǎn)操作：插入和刪除可能破壞二叉樹的平衡，此時需要通過一次或多次樹旋轉(zhuǎn)來重新平衡這個樹。當插入數(shù)據(jù)時，最多只需要兩次旋轉(zhuǎn)(單旋轉(zhuǎn)或雙旋轉(zhuǎn))；但是當刪除數(shù)據(jù)時，會導(dǎo)致樹失衡，AVL需要維護從被刪除節(jié)點到根節(jié)點這條路徑上所有節(jié)點的平衡，旋轉(zhuǎn)的量級為O(lgn)。

由于旋轉(zhuǎn)的耗時，AVL樹在刪除數(shù)據(jù)時效率很低；在刪除操作較多時，維護平衡所需的代價可能高于其帶來的好處，因此AVL實際使用并不廣泛。

場景：windows對進程地址空間的管理用到了AVL樹。

針對于這種情況，紅黑樹對其做了優(yōu)化。

紅黑樹RB-Tree

紅黑樹是一種自平衡的二叉查找樹，是一種高效的查找樹。它是由 Rudolf Bayer 于1978年發(fā)明，在當時被稱為平衡二叉 B 樹(symmetric binary B-trees)。后來，在1978年被 Leo J. Guibas 和 Robert Sedgewick 修改為如今的紅黑樹。紅黑樹具有良好的效率，它可在 O(logN) 時間內(nèi)完成查找、增加、刪除等操作。

紅黑樹是一種接近平衡的二叉樹（說它是接近平衡因為它并沒有像AVL樹的平衡因子的概念，它只是靠著滿足紅黑節(jié)點的5條性質(zhì)來維持一種接近平衡的結(jié)構(gòu)，進而提升整體的性能，并沒有嚴格的卡定某個平衡因子來維持絕對平衡）。

特性

一棵紅黑樹同時滿足以下特性：

• 節(jié)點是紅色或黑色
• 根是黑色
• 葉子節(jié)點（外部節(jié)點，空節(jié)點）都是黑色，這里的葉子節(jié)點指的是最底層的空節(jié)點（外部節(jié)點），下圖中的那些null節(jié)點才是葉子節(jié)點，null節(jié)點的父節(jié)點在紅黑樹里不將其看作葉子節(jié)點
• 紅色節(jié)點的子節(jié)點都是黑色
• 紅色節(jié)點的父節(jié)點都是黑色
• 從根節(jié)點到葉子節(jié)點的所有路徑上不能有 2 個連續(xù)的紅色節(jié)點
• 從任一節(jié)點到葉子節(jié)點的所有路徑都包含相同數(shù)目的黑色節(jié)點

紅黑樹的查找，插入和刪除操作，時間復(fù)雜度都是O(logN)。

紅黑樹解決了AVL樹什么問題

1. AVL的左右子樹高度差不能超過1，每次進行插入/刪除操作時，幾乎都需要通過旋轉(zhuǎn)操作保持平衡
2. 在頻繁進行插入/刪除的場景中，頻繁的旋轉(zhuǎn)操作使得AVL的性能大打折扣
3. 紅黑樹通過犧牲嚴格的平衡，換取插入/刪除時少量的旋轉(zhuǎn)操作，整體性能優(yōu)于AVL。紅黑樹插入時的不平衡，不超過兩次旋轉(zhuǎn)就可以解決；刪除時的不平衡，不超過三次旋轉(zhuǎn)就能解決
4. 紅黑樹的紅黑規(guī)則，保證最壞的情況下，也能在O(log 2N)時間內(nèi)完成查找操作。

紅黑樹和AVL樹的效率對比：

1. 如果插入一個node引起了樹的不平衡，AVL樹和紅黑樹都是最多只需要2次旋轉(zhuǎn)操作，即兩者都是O(1)；但是在刪除node引起樹的不平衡時，最壞情況下，AVL需要維護從被刪node到root這條路徑上所有node的平衡性，因此需要旋轉(zhuǎn)的量級O(logN)，而紅黑樹最多只需3次旋轉(zhuǎn)，只需要O(1)的復(fù)雜度。
2. 其次，AVL樹的結(jié)構(gòu)相較紅黑樹來說更為平衡，在插入和刪除node更容易引起Tree的不平衡，因此在大量數(shù)據(jù)需要插入或者刪除時，AVL需要rebalance的頻率會更高。因此，紅黑樹在需要大量插入和刪除node的場景下，效率更高。自然，由于AVL高度平衡，因此AVL的search效率更高。
3. map的實現(xiàn)只是折衷了兩者在search、insert以及delete下的效率。總體來說，紅黑樹的統(tǒng)計性能是高于AVL的。

最壞情況下，AVL樹有最多O(logN)次旋轉(zhuǎn)，而紅黑樹最多三次。

場景：

紅黑樹的應(yīng)用就很多了。

• epoll在內(nèi)核中的實現(xiàn)，用紅黑樹管理事件塊。
• nginx中，用紅黑樹管理timer等。
• Java1.8版本后的的hashMap中使用鏈表+紅黑樹解決哈希沖突問題，Java中的TreeMap使用紅黑樹存儲排序鍵值對。
• 著名的linux進程調(diào)度Completely Fair Scheduler，用紅黑樹管理進程控制塊。

紅黑樹的問題

雖然紅黑樹是一種已經(jīng)被性能優(yōu)化了的自平衡的二叉查找樹，插入修改效率和查找銷量得到了平衡，但他依然存在一些問題。

1. 依舊在插入和刪除時需要對節(jié)點進行旋轉(zhuǎn)，頻繁修改數(shù)據(jù)的場景影響效率。
2. 紅黑樹畢竟是一種二叉樹，當數(shù)據(jù)量很大時，樹的高度會變得很大，查找時經(jīng)過的節(jié)點過多，效率變低。
3. 紅黑樹在內(nèi)存中表現(xiàn)優(yōu)秀，但因為樹的高度的問題，當使用磁盤等輔助存儲設(shè)備讀寫數(shù)據(jù)時（如MySQL等數(shù)據(jù)庫），會導(dǎo)致數(shù)據(jù)在磁盤中散布分散，并且IO次數(shù)過多，效率變低。
4. 適合單個查詢，對于數(shù)據(jù)查詢中常見的范圍查詢場景，無法很好支持。

針對于上述問題，有了天生為磁盤存儲而生的B樹。

B樹

B樹是一種多路搜索樹，又名平衡多路查找樹（查找路徑不只兩個），與二叉樹相比，B樹的每個非葉節(jié)點可以有多個子樹。因此，當總節(jié)點數(shù)量相同時，B樹的高度遠遠小于AVL樹和紅黑樹(B樹是一顆“矮胖子”)，磁盤IO次數(shù)大大減少。數(shù)據(jù)庫索引技術(shù)里大量使用者B樹和B+樹的數(shù)據(jù)結(jié)構(gòu)。

定義B樹最重要的概念是階數(shù)(Order)，對于一顆m階B樹（就是一個節(jié)點最多包含幾個子節(jié)點），需要滿足以下條件：

• 每個節(jié)點最多包含 m 個子節(jié)點。
• 如果根節(jié)點包含子節(jié)點，則至少包含 2 個子節(jié)點；除根節(jié)點外，每個非葉節(jié)點至少包含 m/2 個子節(jié)點。
• 擁有 k 個子節(jié)點的非葉節(jié)點將包含 k - 1 條記錄。
• 所有葉節(jié)點都在同一層中。

度數(shù)：在樹中，每個節(jié)點的子節(jié)點（子樹）的個數(shù)就稱為該節(jié)點的度 (degree)。

階數(shù)：階(order)定義為一個節(jié)點最多可以有多少個元素。

如下圖，這是一個2階3度的B樹。

場景：MongoDB索引。

B樹的優(yōu)勢

B樹相對平衡二叉樹在節(jié)點空間的利用率上進行改進，B樹在每個節(jié)點保存更多的數(shù)據(jù)，減少了樹的高度，從而提升了查找的性能。

B樹的優(yōu)勢除了樹高小，還有對訪問局部性原理的利用。

所謂局部性原理，是指當一個數(shù)據(jù)被使用時，其附近的數(shù)據(jù)有較大概率在短時間內(nèi)被使用。B樹將鍵相近的數(shù)據(jù)存儲在同一個節(jié)點，當訪問其中某個數(shù)據(jù)時，數(shù)據(jù)庫會將該整個節(jié)點讀到緩存中；當它臨近的數(shù)據(jù)緊接著被訪問時，可以直接在緩存中讀取，無需進行磁盤IO；換句話說，B樹的緩存命中率更高。

在數(shù)據(jù)庫應(yīng)用中，B樹的每個節(jié)點存儲的數(shù)據(jù)量大約為4K, 這是因為考慮到磁盤數(shù)據(jù)存儲是采用塊的形式存儲的，每個塊的大小為4K，每次對磁盤進行IO數(shù)據(jù)讀取時，同一個磁盤塊的數(shù)據(jù)會被一次性讀取出來，所以每一次磁盤IO都可以讀取到B樹中一個節(jié)點的全部數(shù)據(jù)。

對于順數(shù)插入的數(shù)據(jù)，B樹的結(jié)構(gòu)優(yōu)勢可以使其在內(nèi)存中順序排列，存貯到同一個磁盤頁中，順序插入對磁盤的利用率和讀取效率都非常友好。

場景：MySQL的InnbDB 索引。

B樹的問題

B樹雖然解決了磁盤存儲的問題，但是在查詢范圍數(shù)據(jù)時依舊不夠優(yōu)秀，比如你要查詢1-5的數(shù)據(jù)，必須按照樹的中順遍歷來訪問各個節(jié)點。

對于這個問題，B+樹對其進行了優(yōu)化。

B+樹

B+樹是在B樹的基礎(chǔ)上又一次的改進，其主要對兩個方面進行了提升，一方面是查詢的穩(wěn)定性，另外一方面是在數(shù)據(jù)排序方面更友好。

B+樹也是多路平衡查找樹，其特性主要有以下4點：

• B樹中每個節(jié)點（包括葉節(jié)點和非葉節(jié)點）都存儲真實的數(shù)據(jù)，B+樹中只有葉子節(jié)點存儲真實的數(shù)據(jù)，非葉節(jié)點只存儲鍵。在MySQL中，這里所說的真實數(shù)據(jù)，可能是行的全部數(shù)據(jù)（如Innodb的聚簇索引），也可能只是行的主鍵（如Innodb的輔助索引），或者是行所在的地址（如MyIsam的非聚簇索引）。
• B樹中一條記錄只會出現(xiàn)一次，不會重復(fù)出現(xiàn)，而B+樹的鍵則可能重復(fù)重現(xiàn)——一定會在葉節(jié)點出現(xiàn)，也可能在非葉節(jié)點重復(fù)出現(xiàn)。
• B+樹的葉節(jié)點之間通過雙向鏈表鏈接。B+樹葉子節(jié)點的關(guān)鍵字從小到大有序排列，左邊結(jié)尾數(shù)據(jù)都會保存右邊節(jié)點開始數(shù)據(jù)的指針。因為葉子節(jié)點都是有序排列的，所以B+樹對于數(shù)據(jù)的排序有著更好的支持。
• B+樹非葉子節(jié)點的子節(jié)點數(shù)=關(guān)鍵字數(shù)，或者非葉節(jié)點的關(guān)鍵字數(shù)=子節(jié)點數(shù)-1（這里有兩種算法的實現(xiàn)方式)，雖然他們數(shù)據(jù)排列結(jié)構(gòu)不一樣，但其原理還是一樣的Mysql 的B+樹是用第一種方式實現(xiàn)）。

第一種算法：

第二種算法：

B+樹和B樹的對比

1、B+樹的層級更少：相較于B樹B+每個非葉子節(jié)點存儲的關(guān)鍵字數(shù)更多，所以每個磁盤塊存儲的數(shù)據(jù)更多，樹的層級更少所以查詢數(shù)據(jù)更快

2、B+樹查詢速度更穩(wěn)定：B+所有關(guān)鍵字數(shù)據(jù)地址都存在葉子節(jié)點上，所以每次查找的次數(shù)都相同所以查詢速度要比B樹更穩(wěn)定

3、B+樹天然具備排序功能：所有關(guān)鍵字都出現(xiàn)在葉子結(jié)點的鏈表中（稠密索引），B+樹所有的葉子節(jié)點數(shù)據(jù)構(gòu)成了一個有序鏈表，在查詢大小區(qū)間的數(shù)據(jù)時候更方便，數(shù)據(jù)緊密性很高，緩存的命中率也會比B樹高。

4、B+樹全節(jié)點遍歷更快：B+樹遍歷整棵樹只需要遍歷所有的葉子節(jié)點即可，而不需要像B樹一樣需要對每一層進行遍歷，這有利于數(shù)據(jù)庫做全表掃描。

B樹相對于B+樹的優(yōu)點是，如果經(jīng)常訪問的數(shù)據(jù)離根節(jié)點很近，而B樹的非葉子節(jié)點本身存有關(guān)鍵字其數(shù)據(jù)的地址，所以這種數(shù)據(jù)檢索的時候會要比B+樹快。

5、B+樹更適合文件索引系統(tǒng)

B+樹的缺點

在B+樹的構(gòu)建過程中，為了保持樹的平衡，節(jié)點的合并拆分是比較耗費時間的，所以B*樹就是在如何減少構(gòu)建中節(jié)點合并和拆分的次數(shù)，從而提升樹的數(shù)據(jù)插入、刪除性能。

B*樹

相對于B+樹，B*樹的不同之處如下：

（1）首先是關(guān)鍵字個數(shù)限制問題，B+樹初始化的關(guān)鍵字初始化個數(shù)是cei(m/2)，b樹的初始化個數(shù)為（cei(2/3m)）

（2）B+樹節(jié)點滿時就會分裂，而B*樹節(jié)點滿時會檢查兄弟節(jié)點是否滿（因為每個節(jié)點都有指向兄弟的指針），如果兄弟節(jié)點未滿則向兄弟節(jié)點轉(zhuǎn)移關(guān)鍵字，如果兄弟節(jié)點已滿，則從當前節(jié)點和兄弟節(jié)點各拿出1/3的數(shù)據(jù)創(chuàng)建一個新的節(jié)點出來；

• B*樹 與B+樹對比

在B+樹的基礎(chǔ)上因其初始化的容量變大，使得節(jié)點空間使用率更高，而又存有兄弟節(jié)點的指針，可以向兄弟節(jié)點轉(zhuǎn)移關(guān)鍵字的特性使得B*樹額分解次數(shù)變得更少。

總結(jié)

對于上述的演進過程，這里給出一個簡要總結(jié)，如下圖。建議收藏！