池塘魚

二叉樹——>二叉搜索樹——>平衡二叉樹——>B樹——>B+樹

 概念：

• 二叉樹：每個結點最多有兩個子結點的樹。
• 二叉搜索樹（二叉排序樹）：每一個結點都滿足“左結點小于當前結點，右結點大于等于當前結點”的二叉樹。
• 平衡二叉樹：要么是一顆空樹，要么保證其中隨意一個結點都滿足“左右子樹的高度差不大于1”的二叉搜索樹。
• 紅黑樹：是一種大致的平衡二叉樹，不完全滿足平衡二叉樹，因為它舍棄了平衡二叉樹追求的完全平衡，而在大致平衡的基礎上保證每次插入結點后達到平衡最多需要旋轉3次。
• B樹（B-樹）：多路搜索樹，相對二叉搜索樹來說，子結點數量大于2，但滿足左中右的有序。
• B+樹：同樣是多路搜索樹，相比于B樹，它的所有數據結點全部在葉結點，且葉結點之間通過指針形成有序鏈表，同時中間結點不存放數據只存放鍵。
• PS：B樹全稱Balance-樹，因此B是平衡的意思，橫杠也不是減號的意思。

產生原因：

• 二叉樹——>二叉搜索樹：二叉樹搜索樹是為了提升查找效率而生，一顆合格的二叉搜索樹，它的中序遍歷結果一定是從小到大有序排列的，這使得在查找數據時相當于使用二分查找，在大多數情況下時間復雜度從O（n）升級到O（logn），但是最壞的情況，當數據有序插入時，就會退化為鏈表，時間復雜度退化為O（n）。
• 二叉搜索樹——>平衡二叉樹：為了解決上述有序插入時退化為鏈表的情況，使結點分布盡可能均勻，出現了平衡二叉樹。平衡二叉樹通過每次數據都變更都進行多次旋轉操作來保持子樹之間的高度差。此時插入、刪除、查詢的時間復雜度都是O（n）。但是當數據量大的時候，平衡二叉樹因子節點的數量限制深度log₂n就會很大，從而導致查詢效率降低。
• 平衡二叉樹——>紅黑樹：解決最壞情況下為了保證樹的平衡性需要旋轉太多次的情況，保證最壞的情況下都是高效的。
• 平衡二叉樹——>B樹：為了解決數據量大時平衡二叉樹的深度問題，B樹通過允許子結點數量放開來實現樹高的限制，一顆M路（每個結點最多有M個子結點）B樹的深度為log_mn。路數越多，高度越低。但是路數也不能無限制大，否則會退化成有序數組。但是B樹不利于一個區間內多個數據的查詢，查完一個數字后查其他數字可能還需要跨層查詢。
• B樹——>B+樹：B+樹解決了查找一段有序區間的效率問題，通過給存放了所有數據的葉結點之間的指針連接，可以很便利地找到其前后的數據，只需要找到首尾數據就可以找到其區間的多個數據。同時，因為所有數據都存放在葉結點，B+樹的查詢時間復雜度穩定在O（log_mn），查詢更為穩定。

應用場景：

• B樹：大量單個key查詢的場景，比如隨機搜索，可以考慮B樹。
• B+樹：存在大量范圍查詢的場景，適合使用B+樹，比如數據庫。實際應用中操作系統的文件索引和數據庫索引也更適合B+樹，因為B+樹的內部結點不存放數據，一個結點就比較小，磁盤IO操作是以頁為單位的，同樣的頁空間就可以存檔更多的數據，一次IO就可以獲取更多數據。

參考：

 【通俗易懂的圖文 紅黑樹,B樹,B+樹 本質區別及應用場景】