B樹

B樹，?稱多路平衡查找樹，B樹中所被允許的孩?個數的最?值稱為B樹的階，通常?m表示。?棵m階B樹或為空樹，或為滿?如下特性的m叉樹：
1）樹中每個結點?多有m棵?樹，即?多含有m-1個關鍵字。
2）若根結點不是終端結點，則?少有兩棵?樹。
3）除根結點外的所有?葉結點?少有 棵?樹，即?少含有 -1個關鍵字。
5）所有的葉結點都出現在同?層次上，并且不帶信息（可以視為外部結點或類似于折半查找判定樹的查找失敗結點，實際上這些結點不存在，指向這些結點的指針為空）。

m階B樹的核?特性：
1） 根節點的?樹數∈[2, m]，關鍵字數∈[1, m-1]。
其他結點的?樹數∈[ ?m/2?, m]；關鍵字數∈[ ?m/2?-1, m-1]
2）對任?結點，其所有?樹?度都相同
3）關鍵字的值：?樹0<關鍵字1<?樹1<關鍵字2<?樹2<…. (類??叉查找樹 左<中<右)

408算B樹的?度不包括葉?結點（失敗結點）

最??度——讓各層的分叉盡可能的少

n個關鍵字的B樹必有n+1個葉?結點

B樹的插入刪除

對于這里的知識點的話，我們只要求處理手算實現，具體的代碼實現我們不要求，在考試中應該也不會涉及得到。

接下來我們從頭開始建立一棵樹

這里超出來了

在插?key后，若導致原結點關鍵字數超過上限，則從中間位置（ ?m/2?）將其中的關鍵字分為兩部分，左部分包含的關鍵字放在原結點中，右部分包含的關鍵字放到新結點中，中間位置（ ?m/2?）的結點插?原結點的?結點

新元素?定是插?到最底層“終端節點”，?“查找”來確定插?位置

第二層節點也已經滿了

其實B樹的插入就一句話總結，

核?要求：
①對m階B樹——除根節點外，結點關鍵字個數≤n≤m-1
②?樹0<關鍵字1<?樹1<關鍵字2<?樹2<….

記住m階B樹的性質節點最多m-1個關鍵子（最少二分之m向上取整減一，最少二分之m向上取整個子樹，最多m個子樹）

簡言之就是符合B樹的定義然后向上拱中間的元素就好。

B樹的刪除

若被刪除關鍵字在終端節點，則直接刪除該關鍵字（要注意節點關鍵字個數是否低于下限 ?m/2? ? 1）刪除了60

刪除了80

若被刪除關鍵字在?終端節點，則?直接前驅或直接后繼來替代被刪除的關鍵字
直接前驅：當前關鍵字左側指針所指?樹中“最右下”的元素

接下來采取采用直接后繼代替的方式

接下來刪除了節點77

若被刪除關鍵字在?終端節點，則?直接前驅或直接后繼來替代被刪除的關鍵字
直接前驅：當前關鍵字左側指針所指?樹中“最右下”的元素
直接后繼：當前關鍵字右側指針所指?樹中“最左下”的元素

右孩子寬裕

若是刪除38則不滿住B樹的定義了節點關鍵字少于2（?m/2? ?1）個了

兄弟夠借。若被刪除關鍵字所在結點刪除前的關鍵字個數低于下限，且與此結點右（或左）兄弟結
點的關鍵字個數還很寬裕，則需要調整該結點、右（或左）兄弟結點及其雙親結點（??換位法）

這里刪除了38需要將49部位下來滿足最低m-1向上取整減一個個元素此處需要最低2個元素。

49落下來以后第二層元素也就少了一個也不滿足此時就需要從孩子節點選一個后繼來不即右下結點的第一個元素也就是70

說?了，當右兄弟很寬裕時，?當前結點的后繼、后繼的后繼 來填補空缺

接下來刪除90這里是針對于左孩子寬裕的情況。

當左兄弟很寬裕時，?當前結點的前驅、前驅的前驅 來填補空缺

直接前驅是左子樹的最右下角元素

直接后繼是右子樹的最左下角元素

兄弟不夠借。

對于兄弟不夠借就涉及到了一個問題就是合并的問題，這里需要注意一下B樹的另外一個性質就是樹高相同。

若被刪除關鍵字所在結點刪除前的關鍵字個數低于下限，且此時與該結點相鄰的左、右兄弟結點的關鍵字個數均=?m/2? ? 1，則將關鍵字刪除后與左（或右）兄弟結點及雙親結點中的關鍵字進?合并

接下來刪除49

刪除49以后最下面一層不夠元素（m/2向上取整減一個元素）

注意一下這里的動態過程25 70 71 72需要先合并成一個元素

然后第二層就只剩下了73也不符合且沒有借的地方，此時就需要再一次的合并，合并73 80 87 93

就是這樣的

為什么這里合并25 70 71 72后不向74 75 76借元素呢？

因為只能同借元素，你現在如果要向 74 75 76借元素的話就是跑向下層借了這是不允許的。所以只能再次向上層元素合并了。

這些就是B樹的刪除操作，最麻煩的就是不夠借的情況，記住不夠借就合并一定不可以向下面的元素借。

接下來介紹一下B+樹

B+樹

?棵m階的B+樹需滿?下列條件：
1）每個分?結點最多有m棵?樹（孩?結點）。
2）?葉根結點?少有兩棵?樹，其他每個分?結點?少有 棵?樹。
3）結點的?樹個數與關鍵字個數相等。
4）所有葉結點包含全部關鍵字及指向相應記錄的指針，葉結點中將關鍵字按??順序排列，并且相鄰葉結點按??順序相互鏈接起來。
5）所有分?結點中僅包含它的各個?結點中關鍵字的最?值及指向其?結點的指針。（聯系一下索引的概念）

其實簡述一下就是一顆B樹但是終端節點下面連接的是一條條記錄同時，所有元素都存在于總端，允許非終端節點存在終端元素值，且分支節點包含子節點的最大值及其指針。

允許按照鏈表來查找也支持索引查找

索引查找其實揉合了B樹查找和索引的方法。

B+樹的查找一定要到終端節點里面去，而B樹就可以停在半路。這是由于B樹不允許節點中關鍵字重復。

接下來對比一下

】

因為B+樹是直接連接子樹，而B樹是通過區域鏈接這就導致了B樹多一個

因為B+樹是直接連接子樹，而B樹是通過區域鏈接這就導致了B樹多一個，如果B樹不減一的話就會不滿足定義會變成M+1叉B樹

！！！！！！！！！！！！！最后聲明一下B樹以及B+樹的內容看到不懂得情況可以戰略性放棄。