https://zhuanlan.zhihu.com/p/27700617
## **1、平衡二叉樹**
* **概念**
平衡二叉樹是基于二分法的策略提高數據的查找速度的二叉樹的數據結構；
* **特點：**
平衡二叉樹是采用二分法思維把數據按規則組裝成一個樹形結構的數據，用這個樹形結構的數據減少無關數據的檢索，大大的提升了數據檢索的速度；平衡二叉樹的數據結構組裝過程有以下規則：
（1）非葉子節點只能允許最多兩個子節點存在。
（2）每一個非葉子節點數據分布規則為左邊的子節點小當前節點的值，右邊的子節點大于當前節點的值(這里值是基于自己的算法規則而定的，比如hash值)；
平衡樹的層級結構：因為平衡二叉樹查詢性能和樹的層級（h高度）成反比，h值越小查詢越快、為了保證樹的結構左右兩端數據大致平衡降低二叉樹的查詢難度一般會采用一種算法機制實現節點數據結構的平衡，實現了這種算法的有比如[Treap](https://link.zhihu.com/?target=http%3A//baike.baidu.com/item/Treap)、紅黑樹，使用平衡二叉樹能保證數據的左右兩邊的節點層級相差不會大于1.，通過這樣避免樹形結構由于刪除增加變成線性鏈表影響查詢效率，保證數據平衡的情況下查找數據的速度近于二分法查找；
總結平衡二叉樹特點：
（1）非葉子節點最多擁有兩個子節點；
（2）非葉子節值大于左邊子節點、小于右邊子節點；
（3）樹的左右兩邊的層級數相差不會大于1;
（4）沒有值相等重復的節點;
## **2、B樹(B-tree)**
注意:之前有看到有很多文章把B樹和B-tree理解成了兩種不同類別的樹，其實這兩個是同一種樹;
* **概念：**
B樹和平衡二叉樹稍有不同的是B樹屬于多叉樹又名平衡多路查找樹（查找路徑不只兩個），數據庫索引技術里大量使用者B樹和B+樹的數據結構，讓我們來看看他有什么特點;
* **規則：**
（1）排序方式：所有節點關鍵字是按遞增次序排列，并遵循左小右大原則；
（2）子節點數：非葉節點的子節點數>1，且=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）
* **B樹的查詢流程：**
如上圖我要從上圖中找到E字母，查找流程如下
（1）獲取根節點的關鍵字進行比較，當前根節點關鍵字為M，E<M（26個字母順序），所以往找到指向左邊的子節點（二分法規則，左小右大，左邊放小于當前節點值的子節點、右邊放大于當前節點值的子節點）；
（2）拿到關鍵字D和G，D<E<G 所以直接找到D和G中間的節點；
（3）拿到E和F，因為E=E 所以直接返回關鍵字和指針信息（如果樹結構里面沒有包含所要查找的節點則返回null）；
* **B樹的插入節點流程**
定義一個5階樹（平衡5路查找樹;），現在我們要把3、8、31、11、23、29、50、28 這些數字構建出一個5階樹出來;
遵循規則：
（1）節點拆分規則：當前是要組成一個5路查找樹，那么此時m=5,關鍵字數必須4就要進行節點拆分）；
（2）排序規則：滿足節點本身比左邊節點大，比右邊節點小的排序規則;
先插入 3、8、31、11
再插入23、29
再插入50、28
* **B樹節點的刪除**
**規則：**
（1）節點合并規則：當前是要組成一個5路查找樹，那么此時m=5,關鍵字數必須大于等于ceil（5/2）（這里關鍵字數<2就要進行節點合并）；
（2）滿足節點本身比左邊節點大，比右邊節點小的排序規則;
（3）關鍵字數小于二時先從子節點取，子節點沒有符合條件時就向向父節點取，取中間值往父節點放；
**特點：**
B樹相對于平衡二叉樹的不同是，每個節點包含的關鍵字增多了，特別是在B樹應用到數據庫中的時候，數據庫充分利用了磁盤塊的原理（磁盤數據存儲是采用塊的形式存儲的，每個塊的大小為4K，每次IO進行數據讀取時，同一個磁盤塊的數據可以一次性讀取出來）把節點大小限制和充分使用在磁盤快大小范圍；把樹的節點關鍵字增多后樹的層級比原來的二叉樹少了，減少數據查找的次數和復雜度;
## **3、B+樹**
* **概念**
B+樹是B樹的一個升級版，相對于B樹來說B+樹更充分的利用了節點的空間，讓查詢速度更加穩定，其速度完全接近于二分法查找。為什么說B+樹查找的效率要比B樹更高、更穩定；我們先看看兩者的區別
* **規則**
（1）B+跟B樹不同B+樹的**非葉子**節點不保存關鍵字記錄的指針，只進行數據索引，這樣使得B+樹每個**非葉子**節點所能保存的關鍵字大大增加；
（2）B+樹**葉子**節點保存了父節點的所有關鍵字記錄的指針，所有數據地址必須要到葉子節點才能獲取到。所以每次數據查詢的次數都一樣；
（3）B+樹葉子節點的關鍵字從小到大有序排列，左邊結尾數據都會保存右邊節點開始數據的指針。
（4）非葉子節點的子節點數=關鍵字數（來源百度百科）（根據各種資料 這里有兩種算法的實現方式，另一種為非葉節點的關鍵字數=子節點數-1（來源維基百科)，雖然他們數據排列結構不一樣，但其原理還是一樣的Mysql 的B+樹是用第一種方式實現）;
* **特點**
1、B+**樹的層級更少**：相較于B樹B+每個**非葉子**節點存儲的關鍵字數更多，樹的層級更少所以查詢數據更快；
2、B+**樹查詢速度更穩定**：B+所有關鍵字數據地址都存在**葉子**節點上，所以每次查找的次數都相同所以查詢速度要比B樹更穩定;
3、B+**樹天然具備排序功能：**B+樹所有的**葉子**節點數據構成了一個有序鏈表，在查詢大小區間的數據時候更方便，數據緊密性很高，緩存的命中率也會比B樹高。
4、B+**樹全節點遍歷更快：**B+樹遍歷整棵樹只需要遍歷所有的**葉子**節點即可，，而不需要像B樹一樣需要對每一層進行遍歷，這有利于數據庫做全表掃描。
**B樹**相對于**B+樹**的優點是，如果經常訪問的數據離根節點很近，而**B樹**的**非葉子**節點本身存有關鍵字其數據的地址，所以這種數據檢索的時候會要比**B+樹**快。
## **4、B\*樹**
* **規則**
B\*樹是B+樹的變種，相對于B+樹他們的不同之處如下：
（1）首先是關鍵字個數限制問題，B+樹初始化的關鍵字初始化個數是cei(m/2)，b\*樹的初始化個數為（cei(2/3\*m)）
（2）B+樹節點滿時就會分裂，而B\*樹節點滿時會檢查兄弟節點是否滿（因為每個節點都有指向兄弟的指針），如果兄弟節點未滿則向兄弟節點轉移關鍵字，如果兄弟節點已滿，則從當前節點和兄弟節點各拿出1/3的數據創建一個新的節點出來；
* **特點**
在B+樹的基礎上因其初始化的容量變大，使得節點空間使用率更高，而又存有兄弟節點的指針，可以向兄弟節點轉移關鍵字的特性使得B\*樹額分解次數變得更少；
