(3)B+樹
B+樹是B-樹的變體,也是一種多路搜索樹:
1.其定義基本與B-樹同,除了:
2.非葉子結點的子樹指針與關鍵字個數(shù)相同;
3.非葉子結點的子樹指針P[i],指向關鍵字值屬于[K[i], K[i+1])的子樹(B-樹是開區(qū)間);
5.為所有葉子結點增加一個鏈指針;
6.所有關鍵字都在葉子結點出現(xiàn);
如:(M=3)
B+的搜索與B-樹也基本相同,區(qū)別是B+樹只有達到葉子結點才命中(B-樹可以在非葉子結點命中),其性能也等價于在關鍵字全集做一次二分查找;
B+的特性:
1.所有關鍵字都出現(xiàn)在葉子結點的鏈表中(稠密索引),且鏈表中的關鍵字恰好是有序的;
2.不可能在非葉子結點命中;
3.非葉子結點相當于是葉子結點的索引(稀疏索引),葉子結點相當于是存儲(關鍵字)數(shù)據(jù)的數(shù)據(jù)層;
4.更適合文件索引系統(tǒng);
(4)B*樹
是B+樹的變體,在B+樹的非根和非葉子結點再增加指向兄弟的指針;
B*樹定義了非葉子結點關鍵字個數(shù)至少為(2/3)*M,即塊的最低使用率為2/3(代替B+樹的1/2);
B+樹的分裂:當一個結點滿時,分配一個新的結點,并將原結點中1/2的數(shù)據(jù)復制到新結點,最后在父結點中增加新結點的指針;B+樹的分裂只影響原結點和父結點,而不會影響兄弟結點,所以它不需要指向兄弟的指針;
B*樹的分裂:當一個結點滿時,如果它的下一個兄弟結點未滿,那么將一部分數(shù)據(jù)移到兄弟結點中,再在原結點插入關鍵字,最后修改父結點中兄弟結點的關鍵字(因為兄弟結點的關鍵字范圍改變了);如果兄弟也滿了,則在原結點與兄弟結點之間增加新結點,并各復制1/3的數(shù)據(jù)到新結點,最后在父結點增加新結點的指針;
所以,B*樹分配新結點的概率比B+樹要低,空間使用率更高;
(5)紅黑樹
紅黑樹(Red-Black Tree)是二叉搜索樹(BinarySearch Tree)的一種改進。我們知道二叉搜索樹在最壞的情況下可能會變成一個鏈表(當所有節(jié)點按從小到大的順序依次插入后)。而紅黑樹在每一次插入或刪除節(jié)點之后都會花O(log N)的時間來對樹的結構作修改,以保持樹的平衡。也就是說,紅黑樹的查找方法與二叉搜索樹完全一樣;插入和刪除節(jié)點的的方法前半部分節(jié)與二叉搜索樹完全一樣,而后半部分添加了一些修改樹的結構的操作。
map就是采用紅黑樹存儲的,紅黑樹(RB Tree)是平衡二叉樹,其優(yōu)點就是樹到葉子節(jié)點深度一致,查找的效率也就一樣,為logN。在實行查找,插入,刪除的效率都一致,而當是全部靜態(tài)數(shù)據(jù)時,沒有太多優(yōu)勢,可能采用hash表各合適。
相對來說,hash_map是一個hashtable占用內(nèi)存更多,查找效率高一些,但是hash的時間比較費時?傮w而言,hash_map 查找速度會比map快,而且查找速度基本和數(shù)據(jù)數(shù)據(jù)量大小無關,屬于常數(shù)級別;而map的查找速度是log(n)級別。并不一定常數(shù)就比log(n)小, hash還有hash函數(shù)的耗時,明白了吧,如果你考慮效率,特別是在元素達到一定數(shù)量級時,考慮考慮hash_map。但若你對內(nèi)存使用特別嚴格,希望程序盡可能少消耗內(nèi)存,那么一定要小心,hash_map可能會讓你陷入尷尬,特別是當你的hash_map對象特別多時,你就更無法控制了,而且 hash_map的構造速度較慢。
現(xiàn)在知道如何選擇了嗎?權衡三個因素: 查找速度, 數(shù)據(jù)量, 內(nèi)存使用。
紅黑樹的每個節(jié)點上的屬性除了有一個key、3個指針:parent、lchild、rchild以外,還多了一個屬性:color。它只能是兩種顏色:紅或黑。而紅黑樹除了具有二叉搜索樹的所有性質(zhì)之外,還具有以下4點性質(zhì):
1. 根節(jié)點是黑色的。
2. 空節(jié)點是黑色的(紅黑樹中,根節(jié)點的parent以及所有葉節(jié)點lchild、rchild都不指向NULL,而是指向一個定義好的空節(jié)點)。
3. 紅色節(jié)點的父、左子、右子節(jié)點都是黑色。
4. 在任何一棵子樹中,每一條從根節(jié)點向下走到空節(jié)點的路徑上包含的黑色節(jié)點數(shù)量都相同。
相關推薦:北京 | 天津 | 上海 | 江蘇 | 山東 |
安徽 | 浙江 | 江西 | 福建 | 深圳 |
廣東 | 河北 | 湖南 | 廣西 | 河南 |
海南 | 湖北 | 四川 | 重慶 | 云南 |
貴州 | 西藏 | 新疆 | 陜西 | 山西 |
寧夏 | 甘肅 | 青海 | 遼寧 | 吉林 |
黑龍江 | 內(nèi)蒙古 |