B樹(B-tree、B-樹)
? B樹是一種平衡的多路搜索樹，多用于文件系統(tǒng)、數據庫的實現
? 仔細觀察B樹，有什么眼前一亮的特點?
1、1 個節(jié)點可以存儲超過 2 個元素、可以擁有超過 2 個子節(jié)點
2、擁有二叉搜索樹的一些性質
3、平衡，每個節(jié)點的所有子樹高度一致
3、比較矮
m階B樹的性質(m≥2)
?假設一個節(jié)點存儲的元素個數為 x
根節(jié)點:1 ≤ x ≤ m ? 1
非根節(jié)點:┌ m/2 ┐ ? 1 ≤ x ≤ m ? 1
如果有子節(jié)點，子節(jié)點個數 y = x + 1
?根節(jié)點:2 ≤ y ≤ m
?非根節(jié)點:┌ m/2 ┐ ≤ y ≤ m
?比如 m = 3，2 ≤ y ≤ 3，因此可以稱為(2, 3)樹、2-3樹
?比如 m = 4，2 ≤ y ≤ 4，因此可以稱為(2, 4)樹、2-3-4樹
?比如 m = 5，3 ≤ y ≤ 5，因此可以稱為(3, 5)樹
?比如 m = 6，3 ≤ y ≤ 6，因此可以稱為(3, 6)樹
?比如 m = 7，4 ≤ y ≤ 7，因此可以稱為(4, 7)樹
注釋：┌ ┐表示向上取整
?思考:如果 m = 2，那B樹是什么樣子?
?你猜數據庫實現中一般用幾階B樹?
200 ~ 300
B樹 VS 二叉搜索樹
?B樹 和 二叉搜索樹，在邏輯上是等價的
?多代節(jié)點合并，可以獲得一個超級節(jié)點
2代合并的超級節(jié)點，最多擁有 4 個子節(jié)點(至少是 4階B樹)
3代合并的超級節(jié)點，最多擁有 8 個子節(jié)點(至少是 8階B樹)
n代合并的超級節(jié)點，最多擁有 2?個子節(jié)點( 至少是 2?階B樹)
?m階B樹，最多需要 log2m 代合并
搜索
? 跟二叉搜索樹的搜索類似
- 先在節(jié)點內部從小到大開始搜索元素
- 如果命中，搜索結束
- 如果未命中，再去對應的子節(jié)點中搜索元素，重復步驟1
添加
? 新添加的元素必定是添加到葉子節(jié)點
?插入55
?插入95
?再插入 98 呢?(假設這是一棵 4階B樹)
最右下角的葉子節(jié)點的元素個數將超過限制
這種現象可以稱之為:上溢(overflow)
添加 – 上溢的解決(假設5階)
?上溢節(jié)點的元素個數必然等于 m
?假設上溢節(jié)點最中間元素的位置為 k
將 k 位置的元素向上與父節(jié)點合并
將 [0, k-1] 和 [k + 1, m - 1] 位置的元素分裂成 2 個子節(jié)點
?這 2 個子節(jié)點的元素個數，必然都不會低于最低限制(┌ m/2 ┐ ? 1)
? 一次分裂完畢后，有可能導致父節(jié)點上溢，依然按照上述方法解決
最極端的情況，有可能一直分裂到根節(jié)點
添加
?插入 98
?插入 52
?插入 54
刪除 – 葉子節(jié)點
?假如需要刪除的元素在葉子節(jié)點中，那么直接刪除即可
?刪除 30
刪除 – 非葉子節(jié)點
?假如需要刪除的元素在非葉子節(jié)點中
1.先找到前驅或后繼元素，覆蓋所需刪除元素的值
2.再把前驅或后繼元素刪除
?刪除 60
?非葉子節(jié)點的前驅或后繼元素，必定在葉子節(jié)點中
所以這里的刪除前驅或后繼元素 ，就是最開始提到的情況:刪除的元素在葉子節(jié)點中
真正的刪除元素都是發(fā)生在葉子節(jié)點中
刪除 – 下溢
?刪除 22 ?(假設這是一棵 5階B樹)
葉子節(jié)點被刪掉一個元素后，元素個數可能會低于最低限制( ≥ ┌ m/2 ┐ ? 1 )
這種現象稱為:下溢(underflow)
刪除 – 下溢的解決
?下溢節(jié)點的元素數量必然等于 ┌ m/2 ┐ ? 2
?如果下溢節(jié)點臨近的兄弟節(jié)點，有至少 ┌ m/2 ┐ 個元素，可以向其借一個元素
將父節(jié)點的元素 b 插入到下溢節(jié)點的 0 位置(最小位置)
用兄弟節(jié)點的元素 a(最大的元素)替代父節(jié)點的元素 b
這種操作其實就是:旋轉
?如果下溢節(jié)點臨近的兄弟節(jié)點，只有 ┌ m/2 ┐ ? 1 個元素
將父節(jié)點的元素 b 挪下來跟左右子節(jié)點進行合并
合并后的節(jié)點元素個數等于┌ m/2 ┐ + ┌ m/2 ┐ ? 2，不超過 m ? 1
這個操作可能會導致父節(jié)點下溢，依然按照上述方法解決，下溢現象可能會一直往上傳播
刪除
?刪除 22 ?(假設這是一棵 5階B樹)
4階B樹
? 如果先學習4階B樹(2-3-4樹)，將能更好地學習理解紅黑樹
? 4階B樹的性質
所有節(jié)點能存儲的元素個數 x :1 ≤ x ≤ 3
所有非葉子節(jié)點的子節(jié)點個數 y :2 ≤ y ≤ 4
?添加
從 1 添加到 22
?刪除
從1刪除到22
