幾種平衡樹的總結(jié)

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

總而言之，B 樹在提高了磁盤IO 性能的同時(shí)并沒有解決元素遍歷效力低下的問題。正是為了解決這個(gè)問題，B+樹應(yīng)運(yùn)而生。B+樹只要遍歷葉子節(jié)點(diǎn)就能夠?qū)崿F(xiàn)整棵樹的遍歷，支持基于范圍的查詢，而B樹不支持range-query 這樣的操作（或說效力太低）。

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