幾種平衡樹的總結

1、2⑶⑷樹介紹
2⑶⑷樹是1種多叉樹(multiway tree)，它的每一個節點最多有4個子節點和3個數據項，2⑶⑷ 樹可以看作是階為4 的B樹。B樹是另外一種平衡的多叉樹，專門用在外部存儲中來組織數據(通常是指磁盤驅動器)。B樹中的節點可以有幾時或幾百個。
2⑶⑷樹名字中的2、3、4的含義是指1個節點可能含有的子節點數。
有1個數據項的節點總是有2個子節點
有2個數據項的節點總是有3個子節點
有3個數據項的節點總是有4個子節點
簡言之，非葉子節點的子節點數總是比它含有的數據項多1
在2⑶⑷樹中不允許1個節點只有1個鏈接,這與傳統的2叉樹不同。
2、B樹、B+樹
2叉樹提供了良好的性能，但是當數據有序插入時會失去平衡，2⑶⑷樹和2⑶樹是1種平衡樹,是多路的，而紅-黑樹（見上1篇文章）是1種2叉平衡樹，通過嚴格的紅黑規則保持平衡。B樹是1種平衡的多路查找樹，可以看作1種擴大的2⑶⑷樹，它的數據項個數和子節點數沒有限制(如果結點的元素數量非常多的話那就退化成節點內部的線性查找了)，在文件系統中有所利用，主要用作文件的索引。
B樹插入節點要注意從子節點開始分裂,1直上溯到根
B+樹是B樹的1種變型
B+樹中的非葉子節點不是終究指向文件內容的節點，而只是葉子節點中關鍵字的索引。所有的葉子節點包括了全部關鍵字的信息，且葉子節點本身依關鍵字自小而大順序鏈接。所以任何關鍵字的查找都必須走1條從根節點到葉子節點的路(致使每個數據的查詢效力相當)。

總而言之，B 樹在提高了磁盤IO 性能的同時并沒有解決元素遍歷效力低下的問題。正是為了解決這個問題，B+樹應運而生。B+樹只要遍歷葉子節點就能夠實現整棵樹的遍歷，支持基于范圍的查詢，而B樹不支持range-query 這樣的操作（或說效力太低）。

通過以上介紹，大致將B 樹，B+樹，B*樹總結以下：
● B 樹：有序數組+平衡多叉樹；
● B+樹：有序數組鏈表+平衡多叉樹；
● B*樹：1棵飽滿的B+樹。
B樹相干的參考資料http://blog.csdn.net/v_july_v/article/details/6530142