GreenHatHG の Blog

单线程版 B + 树删除操作

Delete

在删除时用到两个重要的属性是，也就是 node 最多有多少个 search-key value，最少有多少个，根据这个可以决定采用什么措施去维持整个树的平衡

• Each leaf can hold up to n−1 search-key values. We allow leaf nodes to contain as few as ⌈(n−1)/2⌉ search-key values.
• Each nonleaf node in the tree (other than the root) has between ⌈n/2⌉ and n children.

下面举例课本中的删除过程，粗略了解一下删除的过程：

已经有一棵 B + 树如下，从 leaf node 可知 N=4

所以 leaf node 最多放 3 个 search-key value，最少 2 个 search-key value；nonleaf node 最多 4 个 children，最少 2 个 children。

Coalesce

一开始要删除 Srini 这个 Index，首先查找到 Srini 位于哪个 leaf node，然后将其删除，如下图：

删除后这个 leaf node 只剩下一个 key，不符合树的属性，树的 key 总共有那么多，为了让每个 node 都符合上述的属性，有两种方法可以来调整，一个是 coalesce，另一个则是 redistribute。前者意思是合并兄弟节点，后者意思是节点间重新分配。

在这里该 leaf node 可以和左边的兄弟节点合并，然后删除剩下的空 leaf node 和指向其的 parent node

Redistribute

此时有一个 internal node（第二层最右边）只有一个 entry（key 没有用到，value 指向下一个节点），不符合树的属性，需要调整。

如果采用合并的策略，那么明显左边的 node 已经有 4 个 children 了，加上现有一个，总共 5 个，超出最大值。

只能是采取兄弟节点间重新分配的策略，以便每个 nonleaf 节点至少有 2 个 children

如上图，将左边兄弟节点的 Gold search-key 移动到右边的节点，此时右边节点共有两个 children。此时 root 节点并不能区分其两个 children，因为 Mozart 左边 children 的范围应该是小于”Mozart”，右边 children 的范围应该是大于等于”Mozart”，右边的 children 不符合要求。所以需要将 root 节点”Mozart” 和 children 节点”Gold” 进行交换，如下图所示。其实也挺好理解的，原本要移动的值是小于其父节点的，现在需要移动到右边，那么肯定不能直接移动，移动了就不符合大小定义了，所以可以直接移动到父节点，而父节点移动到右边，就能满足了，因为整体从左到右是增大的顺序，这样移动保持了相对位置没有发生改变。

现在接着删除”Singh” 和”Wu”，删除”Singh” 后还剩下两个 search-key value，删除”Wu” 后只剩下一个了，该 leaf node 处于 underfull 状态。

由上图可知不能合并兄弟节点，只能执行重新分配策略，将左边兄弟节点的”Kim” 移动到右边

上图中第二层右边的”Mozart” 不能区分其 children 节点，为此需要将其变成”Kim”，如下图：

Underflow

接着删除”Gold”，如下图，该 leaf node 处于 underfull 状态

由上图，该 leaf node 可以和右边的兄弟节点进行合并，同时删除一个 parent node：

树中第二层右边那个 internal node 只有一个 children，处于 underfill 状态，此时可以执行合并或者重新分配策略，用于演示，在书本中选择的是合并。

对于 nonleaf node 的合并来讲，需要将特定的 parent key 移动到合并的节点。

这也好理解，因为 parent key 是区分两个 child 的关键，现在只剩下一个 child 了，但是之前的 underfill child 还有个空的 key，但是 value 有用的 item，这个指引功能可以由 parent key 代替，所以就将 parent key 移动到合并节点，因为之前得通过 parent key 能找到那个 underfill child，再找到其指向的 child，现在 underfill child 没了，通过 parent key 直接指引到其指向的 child。

将 Gold 移动到左边 child node，此时 root 只剩下一个 child，但是 root 至少得两个 child，所以 root 被删除。

需要注意的是，”Gold” 从叶子节点中删除了，但是在 nonleaf node 中还存在。

删除一个节点，可能还需要递归处理其父节点，极端情况下会处理到 root 节点，调整了整一棵树。

Four Case

上面的流程可以大概知道删除过程什么样

一般来讲可以将删除操作抽象成四个部分：leaf node merge、nonleaf node merge、leaf node redistribute、nonleaf node redistribute

下面的图来自：CMU 15445-2022 P2 B+Tree Insert/Delete - 知乎

Leaf Node Merge

最简单就是叶子节点合并了

1. 删除 P1 节点的 5
2. 合并右边兄弟节点 P2 到 P1
3. 删除掉 P2
4. 删除掉指向的 P2 的节点（P3 中的 19）

NonLeaf Node Merge

1. 删除掉 P17 中的 11
2. 删除掉 11 后，不满足容量最少为 1 的条件，需要合并兄弟节点，这里只有一个右边的兄弟节点
3. 合并完后，P19 的 12 移动到 P17 中，P19 删除掉
4. P14 中删除掉指向 P19 的节点
5. 此时 P14 处于 underfill 状态，需要 merge（为了举例子暂不考虑 redistribute），将 P14 合并到 P3（见下图）
6. P7 中的 parent key 移动到 P3
7. 删除 P14
8. 删除 P7 的指向 P14 的 index

这里有一个特殊情况就是可能会造成 root 节点的删除（此时的策略是 leaf node merge）

1. 删除 P2 的 23 这个节点，P2 处于 underfill 状态
2. P2 合并到 P1，删除 P2
3. 在 P3 中删除指向 P2 的 index
4. root 节点处于 underfill 状态，删除掉

Leaf Node Redistribute

1. P1 中删除 2
2. 触发重新分配
3. 重新分配完成后，为了能够区分两个 child，需要更改 parent key

NonLeaf Node Redistribute

1. 从 P1 中删除 2
2. 需要和 P2 进行 merge（leaf node merge 策略）
3. 删除掉 P2
4. 在 P3 中删除掉指向 P2 的 index
5. P3 处于 underfill 状态，需要重新分配
6. 为了保持相对大小的关系不变，这里可以直接将 parent key 5 移动到 P3
7. 那么相对应的将 P9 中的 7 移动到 P11

---

For more：

• B + 树的删除 - 知乎