B樹(shù)(B-tree刨晴、B-樹(shù))
? B樹(shù)是一種平衡的多路搜索樹(shù)，多用于文件系統(tǒng)垛玻、數(shù)據(jù)庫(kù)的實(shí)現(xiàn)
? 仔細(xì)觀察B樹(shù)，有什么眼前一亮的特點(diǎn)?
1奶躯、1 個(gè)節(jié)點(diǎn)可以存儲(chǔ)超過(guò) 2 個(gè)元素帚桩、可以擁有超過(guò) 2 個(gè)子節(jié)點(diǎn)
2、擁有二叉搜索樹(shù)的一些性質(zhì)
3嘹黔、平衡账嚎，每個(gè)節(jié)點(diǎn)的所有子樹(shù)高度一致
3、比較矮
m階B樹(shù)的性質(zhì)(m≥2)
?假設(shè)一個(gè)節(jié)點(diǎn)存儲(chǔ)的元素個(gè)數(shù)為 x
根節(jié)點(diǎn):1 ≤ x ≤ m ? 1
非根節(jié)點(diǎn):┌ m/2 ┐ ? 1 ≤ x ≤ m ? 1
如果有子節(jié)點(diǎn)儡蔓，子節(jié)點(diǎn)個(gè)數(shù) y = x + 1
?根節(jié)點(diǎn):2 ≤ y ≤ m
?非根節(jié)點(diǎn):┌ m/2 ┐ ≤ y ≤ m
?比如 m = 3郭蕉，2 ≤ y ≤ 3，因此可以稱為(2, 3)樹(shù)喂江、2-3樹(shù)
?比如 m = 4召锈，2 ≤ y ≤ 4，因此可以稱為(2, 4)樹(shù)获询、2-3-4樹(shù)
?比如 m = 5涨岁，3 ≤ y ≤ 5，因此可以稱為(3, 5)樹(shù)
?比如 m = 6吉嚣，3 ≤ y ≤ 6梢薪，因此可以稱為(3, 6)樹(shù)
?比如 m = 7，4 ≤ y ≤ 7尝哆，因此可以稱為(4, 7)樹(shù)
注釋：┌ ┐表示向上取整
?思考:如果 m = 2秉撇，那B樹(shù)是什么樣子?
?你猜數(shù)據(jù)庫(kù)實(shí)現(xiàn)中一般用幾階B樹(shù)?
200 ~ 300
B樹(shù) VS 二叉搜索樹(shù)
?B樹(shù) 和 二叉搜索樹(shù)，在邏輯上是等價(jià)的
?多代節(jié)點(diǎn)合并秋泄，可以獲得一個(gè)超級(jí)節(jié)點(diǎn)
2代合并的超級(jí)節(jié)點(diǎn)琐馆，最多擁有 4 個(gè)子節(jié)點(diǎn)(至少是 4階B樹(shù))
3代合并的超級(jí)節(jié)點(diǎn)，最多擁有 8 個(gè)子節(jié)點(diǎn)(至少是 8階B樹(shù))
n代合并的超級(jí)節(jié)點(diǎn)恒序，最多擁有 2?個(gè)子節(jié)點(diǎn)( 至少是 2?階B樹(shù))
?m階B樹(shù)啡捶，最多需要 log2m 代合并
搜索
? 跟二叉搜索樹(shù)的搜索類似
- 先在節(jié)點(diǎn)內(nèi)部從小到大開(kāi)始搜索元素
- 如果命中，搜索結(jié)束
- 如果未命中奸焙，再去對(duì)應(yīng)的子節(jié)點(diǎn)中搜索元素瞎暑，重復(fù)步驟1
添加
? 新添加的元素必定是添加到葉子節(jié)點(diǎn)
?插入55
?插入95
?再插入 98 呢?(假設(shè)這是一棵 4階B樹(shù))
最右下角的葉子節(jié)點(diǎn)的元素個(gè)數(shù)將超過(guò)限制
這種現(xiàn)象可以稱之為:上溢(overflow)
添加 – 上溢的解決(假設(shè)5階)
?上溢節(jié)點(diǎn)的元素個(gè)數(shù)必然等于 m
?假設(shè)上溢節(jié)點(diǎn)最中間元素的位置為 k
將 k 位置的元素向上與父節(jié)點(diǎn)合并
將 [0, k-1] 和 [k + 1, m - 1] 位置的元素分裂成 2 個(gè)子節(jié)點(diǎn)
?這 2 個(gè)子節(jié)點(diǎn)的元素個(gè)數(shù)彤敛，必然都不會(huì)低于最低限制(┌ m/2 ┐ ? 1)
? 一次分裂完畢后，有可能導(dǎo)致父節(jié)點(diǎn)上溢了赌，依然按照上述方法解決
最極端的情況墨榄，有可能一直分裂到根節(jié)點(diǎn)
添加
?插入 98
?插入 52
?插入 54
刪除 – 葉子節(jié)點(diǎn)
?假如需要?jiǎng)h除的元素在葉子節(jié)點(diǎn)中，那么直接刪除即可
?刪除 30
刪除 – 非葉子節(jié)點(diǎn)
?假如需要?jiǎng)h除的元素在非葉子節(jié)點(diǎn)中
1.先找到前驅(qū)或后繼元素勿她，覆蓋所需刪除元素的值
2.再把前驅(qū)或后繼元素刪除
?刪除 60
?非葉子節(jié)點(diǎn)的前驅(qū)或后繼元素袄秩，必定在葉子節(jié)點(diǎn)中
所以這里的刪除前驅(qū)或后繼元素 ，就是最開(kāi)始提到的情況:刪除的元素在葉子節(jié)點(diǎn)中
真正的刪除元素都是發(fā)生在葉子節(jié)點(diǎn)中
刪除 – 下溢
?刪除 22 ?(假設(shè)這是一棵 5階B樹(shù))
葉子節(jié)點(diǎn)被刪掉一個(gè)元素后逢并，元素個(gè)數(shù)可能會(huì)低于最低限制( ≥ ┌ m/2 ┐ ? 1 )
這種現(xiàn)象稱為:下溢(underflow)
刪除 – 下溢的解決
?下溢節(jié)點(diǎn)的元素?cái)?shù)量必然等于 ┌ m/2 ┐ ? 2
?如果下溢節(jié)點(diǎn)臨近的兄弟節(jié)點(diǎn)之剧，有至少 ┌ m/2 ┐ 個(gè)元素，可以向其借一個(gè)元素
將父節(jié)點(diǎn)的元素 b 插入到下溢節(jié)點(diǎn)的 0 位置(最小位置)
用兄弟節(jié)點(diǎn)的元素 a(最大的元素)替代父節(jié)點(diǎn)的元素 b
這種操作其實(shí)就是:旋轉(zhuǎn)
?如果下溢節(jié)點(diǎn)臨近的兄弟節(jié)點(diǎn)砍聊，只有 ┌ m/2 ┐ ? 1 個(gè)元素
將父節(jié)點(diǎn)的元素 b 挪下來(lái)跟左右子節(jié)點(diǎn)進(jìn)行合并
合并后的節(jié)點(diǎn)元素個(gè)數(shù)等于┌ m/2 ┐ + ┌ m/2 ┐ ? 2背稼，不超過(guò) m ? 1
這個(gè)操作可能會(huì)導(dǎo)致父節(jié)點(diǎn)下溢，依然按照上述方法解決玻蝌，下溢現(xiàn)象可能會(huì)一直往上傳播
刪除
?刪除 22 ?(假設(shè)這是一棵 5階B樹(shù))
4階B樹(shù)
? 如果先學(xué)習(xí)4階B樹(shù)(2-3-4樹(shù))蟹肘，將能更好地學(xué)習(xí)理解紅黑樹(shù)
? 4階B樹(shù)的性質(zhì)
所有節(jié)點(diǎn)能存儲(chǔ)的元素個(gè)數(shù) x :1 ≤ x ≤ 3
所有非葉子節(jié)點(diǎn)的子節(jié)點(diǎn)個(gè)數(shù) y :2 ≤ y ≤ 4
?添加
從 1 添加到 22
?刪除
從1刪除到22
