B樹
性質
可以看見一個節點可以有多個數字了
然后也滿足左小右大的特征
?然后所有的葉子節點都在同一層，然后2個數字的節點就可以有3個分支
然后呢，每個節點里面到底有幾個數字是有規定的公式的
?就這個公式，m是5階的，算出來是2和4，也就是說最少2個最多4個
然后5階的意思就是最多有5個分叉
前提是非根
?
做題
1
這里最多有3個關鍵字，所以是4階的B樹
當然這種非真題不是很嚴謹，因為5階，6階都有可能
但不能7階，因為7階的時候就是 7/2 - 1 = 3，每個節點至少有3個關鍵字
2
先看第14題
算出來最少2個，最多4個
這個公式要注意的是根節點是例外，可以是1個，其他至少得2個
圖畫出來是這樣
a
然后第15題
它問的是結點個數最多哈，也就是一個結點一個關鍵字就行，也就是15個
d
3
根據公式最少是1個節點，最多2個，所以這里也就是求高度為5的滿二叉樹
2的5次方-1 = 31
b
B樹的插入
做法
有一個概念就是分裂，看圖就行了
比如這里已經算好了，最少是1個關鍵字，最多是2個關鍵字
然后我要插入60，插入后發現b圖這里有3個關鍵字，不滿足要求
然后開始分裂，也就是說把中間的關鍵字提到上面去
那如果是4個，你可以把第2個放上面，也可以把第3個放上面都行
做題
1
這里把刪除先改成插入61，刪除還沒學
最多2個，最少1個關鍵字不多說
第一次分裂后還是超出的上限，繼續分裂
最后變成這樣
2
?
B樹的刪除
做法
這上面也就是說，你刪的不是葉子節點就要用左邊最大或右邊最小的去替代
這里即可以放78也可以放90
然后是葉子節點的刪除
這是第一種
這是第二種
這里是4階的，最少也得1個呢，所以過程是這樣的
65：兄弟我被被刪了，能不能借一個
74：兄弟你太性情了，沒問題啊
71：不是就你想借就借啊，你放我左邊我可借不了
74：那行，爹，那你下去，我替您上去得了
這是第三種
5：兄弟，借一下
65，byd找你爹去，我不夠借
然后60替換到下面去，可以發現60和65可以合并，合并的時候不用擔心會不會超出上限，因為本來就不夠借，多一個不會怎么樣
題目
1
d
2
重點
B+樹
概念
B+樹 = 畢加索
左邊是小于等于60的? 右邊是大于60小于等于85的
然后數字是必須要有重復出現的，比如60就一直跑到了葉子節點，也就是說，上面的只是索引，告訴你應該往哪里走
并且葉子節點是通過指針連起來的，變成有序表
與B樹的差異
然后就是B+樹有二種方式查找
