七、B-树

文中所有结点，都应该是结点，而不是节点，请注意，因为在记录笔记的时候打字不太注意，也懒得花时间纠结这个了，这里提及下。

B-树就叫做B树，虽然带了一个-号，但是确实就是叫B树

B+树就正常的叫做B+树

1.B-树

下图是一个二叉排序树，也是一个平衡二叉树

而B-树就是可以有多个分支，如下：

原来的二叉树中一个节点只有一个关键字，现在的B-树一个节点可以有多个关键字，有多个关键字，就有多个分支了。

image.png image.png

节点内的各关键字互不相等

叶子结点处于同一层；可以用指针表示，是查找失败达到的位置。

image.png

有一点需要注意的是计算高度时候，计算树的高度的时候不算空指针那一层，但是如果计算叶子节点时候，就需要算上空指针，如图，高度为3，但是叶子结点就是30

下图就是严格意义上B树的画法

image.png

可以看到每个结点都分配了4个关键字的存储空间，即使删掉几个关键字，也不影响他的阶数，他仍然是5阶。

下图中第一行的数据代表的是关键字，第二行代表的是指向关键字的孩子节点

image.png

2.B-树关键字查找

image.png

关键字的查找首先从根节点开始，比如要查找44，那么根节点不是，然后因为44>30所以往右子节点查找，39发现不对，然后因为44大于39所以到39的右子节点查找，就找到了。

3.B-树插入关键字

image.png image.png

插入过程详细描述：
因为是五阶树，所以最多的关键字可以放4个，我们先放了 1，2，6，7 然后准备放11的时候该怎么放呢，这个时候取 5/2 然后向上取整得到3，我们把第三个数字提出来：

image.png image.png

接下来需要插入10，这个时候问题又来了：

image.png image.png

因为10处于第三个位子，所以提出来，放到了上一层

然后继续插入数据，直到遇到20：

image.png image.png image.png image.png image.png image.png image.png

最终就建立好了一颗B树了。

4.B-树删除关键字

首先删除关键字我们参照二叉树的删除节点方式：
首先到右分支所指的子树种查找最小的关键字，或者到左分支所指的所有子树中查找最大的关键字，用这两个关键字任意一个取代我们要删除的关键字的位子。

image.png

首先要再提及一下概念，除了根节点是2个关键字外，其他节点的分支数至少要是 2/5 向上取整也就是3个分支，那么也就证明了一个结点至少要有2个关键字

删除8这个关键字没有问题，删除完之后关键字是2个满足要求

image.png

与删除8这个关键字不一样的地方在于，我们删除16这个关键的时候首先看一下16所在节点的左子树的最大数15这个关键字，他是无法删除的，因为删除之后这个节点的关键字就小于2了，不符合要求；

然后我们看16右子树的节点，发现最小的17是可以取代16的

我们删掉16的关键字，然后把17这个关键字移动到16的位子即可。

image.png image.png

再举一个查找的例子：在查找可以替换的关键字问题，我们在做一个例子，如果我们要删除10，那么就看10所在节点的左子树种最大的关键字是9，然后右边是11。

步入正题，现在我们删除15这个关键字：

我们看到15关键字所在结点目前只有2个关键字，所以无法删除，这个时候我们可以向右边去借一个关键字，具体操作如下：

我们可以先让17这个关键字移动下来，然后再将18给挪上去即可。

image.png
image.png

这个时候就可以删掉15这个关键字了。

最后我们需要删除4这个关键字：

image.png

发现无法删除，因为只有2个关键字，而且他左右兄弟节点的关键字都达到了下限无法借调，这个时候我们可以删除，然后合并节点来操作；

image.png

这个时候5这个节点该合并到左边的节点还是右边节点呢，原则上合并到关键字少的节点，但是两边都一样，所以任选一个合并即可。

方法就是让关键字6下来，然后跟左右节点合并即可；

image.png

这个时候新的问题又出来了，3这个节点目前不符合要求，这个时候我们进一步合并：

image.png

刚刚是跟右兄弟节点合并，现在试一试跟左兄弟节点合并：

image.png