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树但是终端节点下面连接的是一条条记录同时，所有元素都存在于总端，允许非终端节点存在终端元素值，且分支节点包含子节点的最大值及其指针。