BST
即二叉搜索樹:
1.所有非葉子結點至多擁有兩個兒子(Left和Right);
2.所有結點存儲一個關鍵字;
3.非葉子結點的左指針指向小於其關鍵字的子樹,右指針指向大於其關鍵字的子樹;
如:
B-樹(B樹)
是一種多路搜索樹(並不是二叉的):
1.定義任意非葉子結點最多只有M個兒子;且M>2;
2.根結點的兒子數為[2, M];
3.除根結點以外的非葉子結點的兒子數為[M/2, M];
4.每個結點存放至少M/2-1(取上整)和至多M-1個關鍵字;(至少2個關鍵字)
5.非葉子結點的關鍵字個數=指向兒子的指針個數-1;
6.非葉子結點的關鍵字:K[1], K[2], …, K[M-1];且K[i] ;
7.非葉子結點的指針:P[1], P[2], …, P[M];其中P[1]指向關鍵字小於K[1]的子樹,P[M]指向關鍵字大於K[M-1]的子樹,其它P[i]指向關鍵字屬於(K[i-1], K[i])的子樹;
8.所有葉子結點位於同一層;
如:(M=3)
B-樹的搜索,從根結點開始,對結點內的關鍵字(有序)序列進行二分查找,如果命中則結束,否則進入查詢關鍵字所屬范圍的兒子結點;重復,直到所對應的兒子指針為空,或已經是葉子結點;
B-樹的特性:
1.關鍵字集合分布在整顆樹中;
2.任何一個關鍵字出現且只出現在一個結點中;
3.搜索有可能在非葉子結點結束;
4.其搜索性能等價於在關鍵字全集內做一次二分查找;
5.自動層次控制;
由於限制了除根結點以外的非葉子結點,至少含有M/2個兒子,確保了結點的至少利用率,其最底搜索性能為O(LogN)
B+樹
B+樹是B-樹的變體,也是一種多路搜索樹:
1.其定義基本與B-樹同,除了:
2.非葉子結點的子樹指針與關鍵字個數相同;
3.非葉子結點的子樹指針P[i],指向關鍵字值屬於[ K[i], K[i+1] )的子樹(B-樹是開區間);
5.為所有葉子結點增加一個鏈指針;
6.所有關鍵字都在葉子結點出現;
如:(M=3)
B+的搜索與B-樹也基本相同,區別是B+樹只有達到葉子結點才命中(B-樹可以在非葉子結點命中),其性能也等價於在關鍵字全集做一次二分查找;
B+的特性:
1.所有關鍵字都出現在葉子結點的鏈表中(稠密索引),且鏈表中的關鍵字恰好是有序的;
2.不可能在非葉子結點命中;
3.非葉子結點相當於是葉子結點的索引(稀疏索引),葉子結點相當於是存儲(關鍵字)數據的數據層;
4.更適合文件索引系統;
更多詳情見請繼續閱讀下一頁的精彩內容: http://www.linuxidc.com/Linux/2014-11/109103p2.htm