B树和B+树的插入、删除

1. B树

1.1 B树的定义

$B$ 树也称 $B-$ 树，它是一颗多路平衡查找树。我们描述一颗 $B$ 树时需要指定它的阶数，阶数表示了一个结点最多有多少个孩子结点，用字母 $m$ 表示阶数。当 $m$ 取 $2$ 时，就是我们常见的二叉搜索树。

一颗 $m$ 阶的 $B$ 树定义如下：

每个结点最多有 $m-1$ 个关键字。
根结点最少可以只有 $1$ 个关键字。
非根结点至少有 $Math.ceil({m\over 2})-1$ 个关键字。
每个结点中的关键字都按照从小到大的顺序排列，每个关键字的左子树中的所有关键字都小于该结点，而右子树中的所有关键字都大于该结点。
所有叶子结点都位于同一层，或者说根结点到每个叶子结点的长度都相同。

上图是一颗阶数为 $4$ 的 $B$ 树。在实际应用中的 $B$ 树的阶数 $m$ 都非常大（通常大于 $100$ ），所以即使存储大量的数据， $B$ 树的高度仍然比较小。每个结点中存储了关键字 $(key)$ 和关键字对应的数据 $(value)$ ，以及孩子结点的指针。我们将一个 $key$ 和其对应的 $value$ 称为一个记录。为方便描述，除非特别说明，后续文中就用 $key$ 来代替 $(key, value)$ 键值对这个整体。在数据库中我们将 $B$ 树（和 $B+$ 树）作为索引结构，可以加快查询速速，此时 $B$ 树中的 $key$ 就表示键，而 $value$ 表示了这个键对应的条目在硬盘上的逻辑地址。

1.2 B树的插入操作

插入操作是指插入一条记录，即 $(key, value)$ 的键值对。如果 $B$ 树中已存在需要插入的键值对，则用需要插入的 $value$ 替换旧 $value$ 。若 $B$ 树不存在该 $key$ ，则一定是在叶子结点中进行插入操作。

根据要插入的 $key$ 的值，找到叶子结点并插入；
判断当前结点 $key$ 的个数是否小于等于 $m-1$ ，若满足则结束，否则进行第3步；
以结点中间的 $key$ 为中心分裂成左右两部分，将这个中间的 $key$ 插入到父结点中，让这个 $key$ 的左侧指针指向分裂后的左半部分， $key$ 的右侧指针指向分裂后的右半部分，然后设置当前结点指向父结点（也就是 $key$ 此时所在的结点），继续进行第3步；
下面以 $5$ 阶 $B$ 树为例，介绍 $B$ 树的插入操作，结点最多有 $4$ 个 $key$ ，最少有 $2$ 个 $key$ 。

a）在空树中插入 $39$

此时根结点就一个 $key$ ，此时根结点也是叶子结点

b）继续插入 $22$ ， $97$ 和 $41$

根结点此时有 $4$ 个 $key$

c）继续插入 $53$

插入后超过了最大允许的关键字个数 $4$ ，以 $key$ 值为 $41$ 为中心进行分裂，结果如下图所示，分裂后当前结点指针指向父结点，满足 $B$ 树条件，插入操作结束。当阶数 $m$ 为偶数时，需要分裂时就不存在排序恰好在中间的 $key$ ，那么选择中间位置的前一个 $key$ 或后一个 $key$ 为中心进行分裂即可。

d）依次插入 $13$ ， $21$ ， $40$ ，同样会造成分裂，结果如下图所示。

e）依次插入 $30$ ， $27$ , $33$ ； $36$ ， $35$ ， $34$ ； $24$ ， $29$ ，结果如下图所示。

f）插入 $key$ 值为 $26$ 的记录，插入后的结果如下图所示。

当前结点需要以 $27$ 为中心分裂，并向父结点插入 $27$ ，然后当前结点指向父结点，结果如下图示。

父（当前即根结点）结点插入 $27$ 后导致父结点也需要分裂，分裂的结果如下图所示。

分裂后当前结点指向新的根，此时无需调整。

g）最后再依次插入 $key$ 为 $17$ ， $28$ ， $29$ ， $31$ ， $32$ 的记录，结果如下图所示。

在实现 $B$ 树的代码中，为了使代码编写更加容易，我们可以将结点中存储记录的数组长度定义为 $m$ 而非 $m-1$ ，这样方便底层的结点由于分裂向上插入一个记录时，上层有多余位置暂存这个记录。同时，每个结点还可以存储它的父结点的引用，这样就不必编写递归程序。

一般来说，对于确定的 $m$ 和确定类型的记录，结点大小是固定的，无论它实际存储了多少个记录。但是分配固定结点大小的方法会存在浪费的情况，比如 $key$ 为 $28$ ， $29$ 所在的结点，还有 $2$ 个 $key$ 的位置没有使用，但已不可能再在此插入任何值了，因为这个结点的前序 $key$ 是27，后继 $key$ 是 $30$ ，所有整数值都用完了。

1.3 B树的删除操作

删除操作是指，根据 $key$ 删除记录，如果 $B$ 树中的记录中不存对应 $key$ 的记录，则删除失败。

如果当前需要删除的 $key$ 位于非叶子结点上，则用后继 $key$ （这里的后继 $key$ 均指后继记录的意思）覆盖要删除的 $key$ ，然后在后继 $key$ 所在的子支中删除该后继key。后继 $key$ 一定位于叶子结点上，这个过程和二叉搜索树删除结点的方式类似。删除这个记录后执行第2步；
该结点 $key$ 个数大于等于 $Math.ceil({m\over 2})-1$ ，结束删除操作，否则执行第3步；
如果兄弟结点 $key$ 个数大于 $Math.ceil({m\over 2})-1$ ，则在父结点与兄弟结点夹住的 $key$ 下移到当前结点，兄弟结点中的一个 $key$ 上移到父结点，删除操作结束；
否则，将父结点中的 $key$ 下移与当前结点及它的兄弟结点中的 $key$ 合并，形成一个新的结点。原父结点中的 $key$ 的两个孩子指针就变成了一个孩子指针，指向这个新结点。然后当前结点的指针指向父结点，重复上第2步。

有些结点它可能即有左兄弟，又有右兄弟，那么我们任意选择一个兄弟结点进行操作即可。

下面以 $5$ 阶 $B$ 树为例，介绍 $B$ 树的删除操作， $5$ 阶 $B$ 树中，结点最多有 $4$ 个 $key$ ，最少有 $2$ 个 $key$

a）原始状态

b）在上面的 $B$ 树中删除 $21$ ，删除后结点中的关键字个数仍然大于等 $2$ ，所以删除结束。

c）在上述情况下接着删除 $27$ 。从上图可知 $27$ 位于非叶子结点中，所以用 $27$ 的后继替换它。图中可以看出， $27$ 的后继为 $28$ ，我们用 $28$ 替换 $27$ ，然后在 $28$ （原 $27$ ）的右孩子结点中删除 $28$ 。删除后的结果如下图所示。

删除后发现，当前叶子结点的记录的个数小于 $2$ ，而它的兄弟结点中有 $3$ 个记录（当前结点还有一个右兄弟，选择右兄弟就会出现合并结点的情况，不论选哪一个都行，只是最后 $B$ 树的形态会不一样而已），我们可以从兄弟结点中借取一个 $key$ 。所以父结点中的 $28$ 下移，兄弟结点中的 $26$ 上移，删除结束。结果如下图所示。

d）在上述情况下接着 $32$ ，结果如下图。

当删除后，当前结点中只 $key$ ，而兄弟结点中也仅有 $2$ 个 $key$ 。只能让父结点中的 $30$ 下移和这两个孩子结点中的 $key$ 合并，成为一个新的结点，当前结点的指针指向父结点。结果如下图所示。

当前结点 $key$ 的个数满足条件，故删除结束。

e）上述情况下，我们接着删除 $key$ 为 $40$ 的记录，删除后结果如下图所示。

同理，当前结点的记录数小于 $2$ ，兄弟结点中没有多余 $key$ ，所以父结点中的 $key$ 下移，和兄弟（这里我们选择左兄弟，选择右兄弟也可以）结点合并，合并后的指向当前结点指针指向父结点。

同理，对于当前结点而言只能继续合并了，最后结果如下所示。

合并后结点当前结点满足条件，删除结束。

B+树

2.1 B+树的定义

各种资料上 $B+$ 树的定义各有不同，一种定义方式是关键字个数和孩子结点数相同。这里我们采取维基百科上所定义的方式，即关键字个数比孩子结点个数小 $1$ ，这种方式是和B树基本等价的。上图就是一颗阶数为 $4$ 的 $B+$ 树。

除此之外 $B+$ 树还有以下的要求。

$B+$ 树包含 $2$ 种类型结点：内部结点（也称索引结点）和叶子结点。根结点本身既可以是内部结点，也可以是叶子结点。根结点的 $key$ 个数最少可以只有 $1$ 个；
$B+$ 树与 $B$ 树最大的不同是内部结点不保存数据，只用于索引，所有的数据（或者说记录）都保存在叶子结点中；
$m$ 阶 $B+$ 树表示了内部结点最多有 $m-1$ 个 $key$ （或者说内部结点最多有 $m$ 个子树），阶数 $m$ 同时限制了叶子结点最多存储 $m-1$ 个记录；
内部结点中的 $key$ 都按照从小到大的顺序排列，对于内部结点中的一个 $key$ ，左树中的所有 $Key$ 都小于它，右子树中的 $key$ 都大于等于它。叶子结点中记录也按照 $key$ 大小排列；
每个叶子结点都存有相邻叶子结点的指针，叶子结点本身依 $key$ 自小而大顺序链接。

2.2 B+树的插入操作

若为空树，创建一个叶子结点，然后将记录插入其中，此时这个叶子结点也是根结点，插入操作结束；
根据 $key$ 值找到叶子结点，向这个叶子结点插入记录。插入后，当前结点 $key$ 的个数小于等于 $m-1$ ，则插入结束。否则将这个叶子结点分裂成左右两个叶子结点，左叶子结点包含前 ${m-1}\over 2$ 个记录，右结点包含剩下记录，将第 ${{m-1}\over 2} + 1$ 个记录的 $key$ 进位到父结点中（父结点一定是索引类型结点），父结点 $key$ 左侧孩子指针向左结点，右侧孩子指针向右结点。将当前结点的指针指向父结点，然后执行第3步；
若当前非叶子结点 $key$ 的个数不多于 $m-1$ ，则插入结束。否则，将这个索引类型结点分裂成两个索引结点，左索引结点包含前 ${m-1}\over 2$ 个key，右结点包含 $m - {{m-1}\over 2}$ 个 $key$ ，将第 ${{m-1}\over 2} + 1$ 个 $key$ 进位到父结点中，父结点的 $key$ 左孩子指向左结点，父结点的 $key$ 右孩子指向右结点。将当前结点的指针指向父结点，然后重复第3步。

下面是一颗 $5$ 阶 $B+$ 树的插入过程， $5$ 阶 $B+$ 数的非根结点最少 $2$ 个 $key$ ，最多4个 $key$ 。

a）空树中插入 $5$

b）依次插入 $8$ ， $10$ ， $15$

c）插入 $16$

插入 $16$ 后超过了关键字的个数限制，所以要进行分裂。在叶子结点分裂时，分裂出来的左结点 $2$ 个记录，右边 $3$ 个记录，中间 $key$ 成为索引结点中的 $key$ ，分裂后当前结点指向父结点（根结点）。结果如下图所示。

当然还有另一种分裂方式，给左结点 $3$ 个记录，右结点 $2$ 个记录，此时索引结点中的 $key$ 就变为 $15$ 。

d）插入 $17$

e）插入 $18$ ，插入后如下图所示

当前结点的关键字个数大于 $5$ ，进行分裂。分裂成两个结点，左结点 $2$ 个记录，右结点 $3$ 个记录， $16$ 进到父结点（索引类型）中，将当前结点的指针指向父结点。

当前结点的关键字个数满足条件，插入结束。

f）插入若干数据后

g）在上图中插入 $7$ ，结果如下图所示

当前结点的关键字个数超过 $4$ ，需要分裂。左结点 $2$ 个记录，右结点 $3$ 个记录。分裂后关键字 $7$ 进入到父结点中，将当前结点的指针指向父结点，结果如下图所示。

当前结点关键字个数超过 $4$ ，需要继续分裂。左结点 $2$ 个关键字，右结点 $2$ 个关键字， $16$ 进入父结点中，将当前结点指向父结点，结果如下图所示。

当前结点的关键字个数满足条件，插入结束。

2.3 B+树的删除操作

如果叶子结点中没有相应的 $key$ ，则删除失败。否则执行下面的步骤

删除叶子结点中对应的 $key$ 。删除后若结点的 $key$ 的个数大于等于 ${Math.ceil(m-1)\over 2}-1$ ，删除操作结束,否则执行第 $2$ 步；
若兄弟结点 $key$ 有大于 ${Math.ceil(m-1)\over 2}-1$ ，向兄弟结点借一个 $key$ ，同时用借到的 $key$ 替换父结点（指当前结点和兄弟结点共同的父结点）中的 $key$ ，删除结束。否则执行第 $3$ 步；
若兄弟结点中没有富余的 $key$ ，则当前结点和兄弟结点合并成一个新的叶子结点，并删除父结点中的 $key$ （父结点中的这个 $key$ 两边的孩子指针就变成了一个指针，正好指向这个新叶子结点），将当前结点指向父结点（必为索引结点），执行第 $4$ 步（以后操作和 $B$ 树完全一样，主要是为了更新索引结点）；
若索引结点的 $key$ 的个数大于等于 ${Math.ceil(m-1)\over 2}-1$ ，则删除操作结束，否则执行第 $5$ 步；
若兄弟结点有富余，父结点 $key$ 下移，兄弟结点 $key$ 上移，删除结束，否则执行第 $6$ 步；
当前结点和兄弟结点及父结点下移 $key$ 合并成一个新的结点。将当前结点指向父结点，重复第 $4$ 步。