B+樹,由二叉樹和雙向鏈表引申出來的一種數據結構。 通常數據庫的索引是通過B+樹來實現的。聚集索引和非聚集索引都是B+樹的結構。聚集索引不但描述了數據是如何組織的,聚集索引其實就是數據本身。數據存放在“葉頁”上,葉頁也就是數據頁,和下文的索引頁需要區分開來。
B 樹
?????? 即二叉搜索樹:
?????? 1. 所有非葉子結點至多擁有兩個兒子( Left 和 Right );
?????? 2. 所有結點存儲一個關鍵字;
?????? 3. 非葉子結點的左指針指向小于其關鍵字的子樹,右指針指向大于其關鍵字的子樹;
?????? 如:
???????
?????? B 樹的搜索,從根結點開始,如果查詢的關鍵字與結點的關鍵字相等,那么就命中;否則,如果查詢關鍵字比結點關鍵字小,就進入左兒子;如果比結點關鍵字大,就進入右兒子;如果左兒子或右兒子的指針為空,則報告找不到相應的關鍵字;
?????? 如果 B 樹的所有非葉子結點的左右子樹的結點數目均保持差不多(平衡),那么 B 樹的搜索性能逼近二分查找;但它比連續內存空間的二分查找的優點是,改變 B 樹結構(插入與刪除結點)不需要移動大段的內存數據,甚至通常是常數開銷;
?????? 如:
??????
???但 B 樹在經過多次插入與刪除后,有可能導致不同的結構:
?? 右邊也是一個 B 樹,但它的搜索性能已經是線性的了;同樣的關鍵字集合有可能導致不同的樹結構索引;所以,使用 B 樹還要考慮盡可能讓 B 樹保持左圖的結構,和避免右圖的結構,也就是所謂的“平衡”問題; ??????
?????? 實際使用的 B 樹都是在原 B 樹的基礎上加上平衡算法,即“平衡二叉樹”;如何保持 B 樹結點分布均勻的平衡算法是平衡二叉樹的關鍵;平衡算法是一種在 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] < K[i+1] ;
?????? 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 個兒子,確保了結點的至少利用率,其最底搜索性能為:
????
?????? 其中, M 為設定的非葉子結點最多子樹個數, N 為關鍵字總數;
?????? 所以 B- 樹的性能總是等價于二分查找(與 M 值無關),也就沒有 B 樹平衡的問題;
?????? 由于 M/2 的限制,在插入結點時,如果結點已滿,需要將結點分裂為兩個各占 M/2 的結點;刪除結點時,需將兩個不足 M/2 的兄弟結點合并;
?
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. 更適合文件索引系統;
小結
?????? B 樹:二叉樹,每個結點只存儲一個關鍵字,等于則命中,小于走左結點,大于走右結點;
?????? B- 樹:多路搜索樹,每個結點存儲 M/2 到 M 個關鍵字,非葉子結點存儲指向關鍵字范圍的子結點;
?????? 所有關鍵字在整顆樹中出現,且只出現一次,非葉子結點可以命中;
?????? B+ 樹:在 B- 樹基礎上,為葉子結點增加鏈表指針,所有關鍵字都在葉子結點中出現,非葉子結點作為葉子結點的索引; B+ 樹總是到葉子結點才命中;
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索:z360901061

微信掃一掃加我為好友
QQ號聯系: 360901061
您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。
【本文對您有幫助就好】元
