1、平衡二叉樹
（1）由來：平衡二叉樹是基於二分法的策略提高數據的查找速度的二叉樹的數據結構；
（2）特點：
平衡二叉樹是採用二分法思維把數據按規則組裝成一個樹形結構的數據，用這個樹形結構的數據減少無關數據的檢索，大大的提升了數據檢索的速度；平衡二叉樹的數據結構組裝過程有以下規則：
非葉子節點只能允許最多兩個子節點存在，每一個非葉子節點數據分佈規則為左邊的子節點小當前節點的值，右邊的子節點大於當前節點的值(這裡值是基於自己的算法規則而定的，比如hash值)；
平衡樹的層級結構：因為平衡二叉樹查詢性能和樹的層級（h高度）成正比、為了保證樹的結構左右兩端數據大致平衡降低二叉樹的查詢難度一般會採用一種算法機制實現節點數據結構的平衡，實現了這種算法的有比如AVL、Treap、紅黑樹，使用平衡二叉樹能保證數據的左右兩邊的節點層級相差不會大於1.，通過這樣避免樹形結構由於刪除增加變成線性鏈表影響查詢效率，保證數據平衡的情況下查找數據的速度近於二分法查找；
總結平衡二叉樹特點：
（1）非葉子節點最多擁有兩個子節點；
（2）非葉子節值大於左邊子節點、小於右邊子節點；
（3）樹的左右兩邊的層級數相差不會大於1;
（4）沒有值相等重複的節點;
二叉樹的優點：
二叉排序樹是一種比較有用的折衷方案。
數組的搜索比較方便，可以直接用下標，但刪除或者插入某些元素就比較麻煩。
鏈表與之相反，刪除和插入元素很快，但查找很慢。
二叉排序樹就既有鏈表的好處，也有數組的好處。
在處理大批量的動態的數據是比較有用。
文件系統和數據庫系統一般都採用樹（特別是B樹）的數據結構數據，主要為排序和檢索的效率。二叉樹是一種最基本最典型的排序樹，用於教學和研究樹的特性，本身很少在實際中進行應用，因為缺點太明顯了（看看教科書怎麼說的）。就像冒泡排序一樣，雖然因為效率問題並不實用，單不失一種教學例子的好手段。
平衡二叉樹都有哪些應用場景
二叉樹支持動態的插入和查找，保證操作在O(height)時間，這就是完成了哈希表不便完成的工作，動態性。但是二叉樹有可能出現worst-case，如果輸入序列已經排序，則時間複雜度為O(N)
平衡二叉樹/紅黑樹就是為了將查找的時間複雜度保證在O(logN)範圍內。
所以如果輸入結合確定，所需要的就是查詢，則可以考慮使用哈希表，如果輸入集合不確定，則考慮使用平衡二叉樹/紅黑樹，保證達到最大效率
平衡二叉樹主要優點集中在快速查找。
如果你知道SGI/STL的set/map底層都是用紅黑樹（平衡二叉樹的一種）實現的，相信你會對這些樹大有興趣。
2、B樹(B-tree)
注意:之前有看到有很多文章把B樹和B-tree理解成了兩種不同類別的樹，其實這兩個是同一種樹;
1、概念：
B樹和平衡二叉樹稍有不同的是B樹屬於多叉樹又名平衡多路查找樹（查找路徑不只兩個），數據庫索引技術裡大量使用者B樹和B+樹的數據結構，讓我們來看看他有什麼特點;
2、規則：
（1）樹種的每個節點最多擁有m個子節點且m>=2,空樹除外（注：m階代表一個樹節點最多有多少個查找路徑，m階=m路,當m=2則是2叉樹,m=3則是3叉）；
（2）除根節點外每個節點的關鍵字數量大於等於ceil(m/2)-1個小於等於m-1個;（注：ceil()是個朝正無窮方向取整的函數 如ceil(1.1)結果為2)
（3）所有葉子節點均在同一層、葉子節點除了包含了關鍵字和關鍵字記錄的指針外也有指向其子節點的指針只不過其指針地址都為null對應下圖最後一層節點的空格子
（4）如果一個非葉節點有N個子節點，則該節點的關鍵字數等於N-1;
（5）所有節點關鍵字是按遞增次序排列，並遵循左小右大原則；
最後我們用一個圖和一個實際的例子來理解B樹（這裡為了理解方便我就直接用實際字母的大小來排列C>B>A）
3、B樹的查詢流程：
如上圖我要從上圖中找到E字母，查找流程如下
（1）獲取根節點的關鍵字進行比較，當前根節點關鍵字為M，E要小於M（26個字母順序），所以往找到指向左邊的子節點（二分法規則，左小右大，左邊放小於當前節點值的子節點、右邊放大於當前節點值的子節點）；
（2）拿到關鍵字D和G，D （3）拿到E和F，因為E=E 所以直接返回關鍵字和指針信息（如果樹結構裡面沒有包含所要查找的節點則返回null）； 4、B樹的插入節點流程 定義一個5階樹（平衡5路查找樹;），現在我們要把3、8、31、11、23、29、50、28 這些數字構建出一個5階樹出來; 遵循規則： （1）當前是要組成一個5路查找樹，那麼此時m=5,關鍵字數必須大於等於cei(5/2)-1小於等於5-1（關鍵字數小於cei(5/2)-1 就要進行節點合併，大於5-1就要進行節點拆分）； （2）滿足左大右小的排序規則; 5、B樹節點的刪除 規則： （1）當前是要組成一個5路查找樹，那麼此時m=5,關鍵字數必須大於等於cei(5/2)-1小於等於5-1； （2）滿足左大右小的排序規則; （3）關鍵字數小於二時先從子節點取，子節點沒有符合條件時就向向父節點取，取中間值往父節點放； 6、特點： B樹相對於平衡二叉樹的不同是，每個節點包含的關鍵字增多了，特別是在B樹應用到數據庫中的時候，數據庫充分利用了磁盤塊的原理（磁盤數據存儲是採用塊的形式存儲的，每個塊的大小一般為4K，每次IO進行數據讀取時，同一個磁盤塊的數據可以一次性讀取出來）把節點大小限制和充分使用在磁盤快大小範圍；把樹的節點關鍵字增多後樹的層級比原來的二叉樹少了，減少數據查找的次數和複雜度; B+樹是B樹的一個升級版，相對於B樹來說B+樹更充分的利用了節點的空間，讓查詢速度更加穩定，其速度完全接近於二分法查找。為什麼說B+樹查找的效率要比B樹更高、更穩定；我們先看看兩者的區別 （1）B+跟B樹不同B+樹的非葉子節點不保存關鍵字記錄的指針，這樣使得B+樹每個節點所能保存的關鍵字大大增加； （2）B+樹葉子節點保存了父節點的所有關鍵字和關鍵字記錄的指針，每個葉子節點的關鍵字從小到大鏈接； 
3、B+樹
（3）B+樹的根節點關鍵字數量和其子節點個數相等;
（4）B+的非葉子節點只進行數據索引，不會存實際的關鍵字記錄的指針，所有數據地址必須要到葉子節點才能獲取到，所以每次數據查詢的次數都一樣；
特點：
在B樹的基礎上每個節點存儲的關鍵字數更多，樹的層級更少所以查詢數據更快，所有指關鍵字指針都存在葉子節點，所以每次查找的次數都相同所以查詢速度更穩定;
4、B*樹
B*樹是B+樹的變種，相對於B+樹他們的不同之處如下：
（1）首先是關鍵字個數限制問題，B+樹初始化的關鍵字初始化個數是cei(m/2)，b*樹的初始化個數為（cei(2/3*m)）
（2）B+樹節點滿時就會分裂，而B*樹節點滿時會檢查兄弟節點是否滿（因為每個節點都有指向兄弟的指針），如果兄弟節點未滿則向兄弟節點轉移關鍵字，如果兄弟節點已滿，則從當前節點和兄弟節點各拿出1/3的數據創建一個新的節點出來；
特點：
在B+樹的基礎上因其初始化的容量變大，使得節點空間使用率更高，而又存有兄弟節點的指針，可以向兄弟節點轉移關鍵字的特性使得B*樹額分解次數變得更少；
總結：
從平衡二叉樹、B樹、B+樹、B*樹總體來看它們的貫徹的思想是相同的，都是採用二分法和數據平衡策略來提升查找數據的速度；
不同點是他們一個一個在演變的過程中通過IO從磁盤讀取數據的原理進行一步步的演變，每一次演變都是為了讓節點的空間更合理的運用起來，從而使樹的層級減少達到快速查找數據的目的；
閱讀更多 cpp軟件架構獅 的文章
