平衡二叉樹是基于二分法的策略提高數據的查找速度的二叉樹的數據結構。

平衡二叉樹是采用二分法思維把數據按規則組裝成一個樹形結構的數據，用這個樹形結構的數據減少無關數據的檢索，大大的提升了數據檢索的速度；平衡二叉樹的數據結構組裝過程有以下規則：

1. 非葉子節點隻能允許最多兩個子節點存在。
2. 每一個非葉子節點數據分布規則為左邊的子節點小當前節點的值，右邊的子節點大于當前節點的值(這裡值是基于自己的算法規則而定的，比如 hash 值)。

因為平衡二叉樹查詢性能和樹的層級（h 高度）成反比，h 值越小查詢越快、為了保證樹的結構左右兩端數據大緻平衡降低二叉樹的查詢難度一般會采用一種算法機制實現節點數據結構的平衡，實現了這種算法的有比如 Treap、紅黑樹，使用平衡二叉樹能保證數據的左右兩邊的節點層級相差不會大于 1。

通過這樣避免樹形結構由于删除增加變成線性鍊表影響查詢效率，保證數據平衡的情況下查找數據的速度近于二分法查找：

總結平衡二叉樹特點：

1. 非葉子節點最多擁有兩個子節點；
2. 非葉子節值大于左邊子節點、小于右邊子節點；
3. 樹的左右兩邊的層級數相差不會大于 1;
4. 沒有值相等重複的節點;

B 樹和平衡二叉樹稍有不同的是 B 樹屬于多叉樹又名平衡多路查找樹（查找路徑不隻兩個），數據庫索引技術裡大量使用者 B 樹和 B 樹的數據結構，讓我們來看看他有什麼特點。

1. 排序方式：所有節點關鍵字是按遞增次序排列，并遵循左小右大原則；
2. 子節點數：非葉節點的子節點數 >1，且 <=M ，且 M>=2，空樹除外（注：M 階代表一個樹節點最多有多少個查找路徑，M=M 路，當 M=2 則是 2 叉樹,M=3 則是 3 叉）；
3. 關鍵字數：枝節點的關鍵字數量大于等于 ceil(m/2)-1 個且小于等于 M-1 個（注：ceil() 是個朝正無窮方向取整的函數 如 ceil(1.1) 結果為 2);
4. 所有葉子節點均在同一層、葉子節點除了包含了關鍵字和關鍵字記錄的指針外也有指向其子節點的指針隻不過其指針地址都為 null 對應下圖最後一層節點的空格子;

最後我們用一個圖和一個實際的例子來理解 B 樹（這裡為了理解方便我就直接用實際字母的大小來排列 C>B>A）

如上圖我要從上圖中找到 E 字母，查找流程如下

1. 獲取根節點的關鍵字進行比較，當前根節點關鍵字為M，E<M（26 個字母順序），所以往找到指向左邊的子節點（二分法規則，左小右大，左邊放小于當前節點值的子節點、右邊放大于當前節點值的子節點）；
2. 拿到關鍵字 D 和 G，D<E<G 所以直接找到 D 和 G 中間的節點；
3. 拿到 E 和 F，因為 E=E 所以直接返回關鍵字和指針信息（如果樹結構裡面沒有包含所要查找的節點則返回 null）；

定義一個 5 階樹（平衡 5 路查找樹），現在我們要把 3、8、31、11、23、29、50、28 這些數字構建出一個 5 階樹出來，遵循如下規則：

1. 節點拆分規則：當前是要組成一個 5 路查找樹，那麼此時 m=5，關鍵字數必須 <=5-1（這裡關鍵字數 >4 就要進行節點拆分）；
2. 排序規則：滿足節點本身比左邊節點大，比右邊節點小的排序規則；

先插入 3、8、31、11

再插入 23、29

再插入 50、28

1. 節點合并規則：當前是要組成一個 5 路查找樹，那麼此時 m=5，關鍵字數必須大于等于 ceil（5/2）（這裡關鍵字數 <2 就要進行節點合并）；
2. 滿足節點本身比左邊節點大，比右邊節點小的排序規則；
3. 關鍵字數小于二時先從子節點取，子節點沒有符合條件時就向向父節點取，取中間值往父節點放；

B 樹相對于平衡二叉樹的不同是，每個節點包含的關鍵字增多了，特别是在 B 樹應用到數據庫中的時候，數據庫充分利用了磁盤塊的原理（磁盤數據存儲是采用塊的形式存儲的，每個塊的大小為 4K，每次 IO 進行數據讀取時，同一個磁盤塊的數據可以一次性讀取出來）把節點大小限制和充分使用在磁盤快大小範圍；把樹的節點關鍵字增多後樹的層級比原來的二叉樹少了，減少數據查找的次數和複雜度。

B 樹是 B 樹的一個升級版，相對于 B 樹來說 B 樹更充分的利用了節點的空間，讓查詢速度更加穩定，其速度完全接近于二分法查找。為什麼說 B 樹查找的效率要比 B 樹更高、更穩定；我們先看看兩者的區别。

1. B 跟 B 樹不同 B 樹的非葉子節點不保存關鍵字記錄的指針，隻進行數據索引，這樣使得 B 樹每個非葉子節點所能保存的關鍵字大大增加；
2. B 樹葉子節點保存了父節點的所有關鍵字記錄的指針，所有數據地址必須要到葉子節點才能獲取到。所以每次數據查詢的次數都一樣；
3. B 樹葉子節點的關鍵字從小到大有序排列，左邊結尾數據都會保存右邊節點開始數據的指針；
4. 非葉子節點的子節點數=關鍵字數。

1. B 樹的層級更少：相較于 B 樹 B 樹每個非葉子節點存儲的關鍵字數更多，樹的層級更少所以查詢數據更快。
2. B 樹查詢速度更穩定：B 樹所有關鍵字數據地址都存在葉子節點上，所以每次查找的次數都相同所以查詢速度要比B樹更穩定。
3. B 樹天然具備排序功能：B 樹所有的葉子節點數據構成了一個有序鍊表，在查詢大小區間的數據時候更方便，數據緊密性很高，緩存的命中率也會比 B 樹高。
4. B 樹全節點遍曆更快：B 樹遍曆整棵樹隻需要遍曆所有的葉子節點即可，，而不需要像 B 樹一樣需要對每一層進行遍曆，這有利于數據庫做全表掃描。

B 樹相對于 B 樹的優點是，如果經常訪問的數據離根節點很近，而 B 樹的非葉子節點本身存有關鍵字其數據的地址，所以這種數據檢索的時候會要比 B 樹快。

B* 樹是 B 樹的變種，相對于 B 樹他們的不同之處如下：

1. 首先是關鍵字個數限制問題，B 樹初始化的關鍵字初始化個數是 cei(m/2)，b* 樹的初始化個數為（cei(2/3*m)）。
2. B 樹節點滿時就會分裂，而 B* 樹節點滿時會檢查兄弟節點是否滿（因為每個節點都有指向兄弟的指針），如果兄弟節點未滿則向兄弟節點轉移關鍵字，如果兄弟節點已滿，則從當前節點和兄弟節點各拿出 1/3 的數據創建一個新的節點出來。

在 B 樹的基礎上因其初始化的容量變大，使得節點空間使用率更高，而又存有兄弟節點的指針，可以向兄弟節點轉移關鍵字的特性使得 B* 樹額分解次數變得更少

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!