从 B-Tree 删除 - M=5
Deletion from B-Tree - M=5
在非常具体的情况下，我正在处理 BTree 中的删除问题
M=5 - 即 - 节点中键的最大数量为 4，节点中键的最小数量为 2
现在，当我接近一个节点时，使用防御方法（我必须使用这种方法）在 BTree 中删除时，我必须保证它比所需的最小值多一个键。
这是我的问题 - 假设我有一个带一把钥匙的根和两个带两个钥匙的 children。
当我接近这些 children 之一时，我将必须保证它至少有 3 个键（因为 M=5）。
我有两种方法 - 向邻居借用或向父亲借用并合并。我不能从邻居那里借用，因为它至少有 2 个键，但是从父亲那里借用并合并创建了一个具有 5 个键的节点 - 它超过了允许键的最大值（因为 M = 5）。
遇到这种情况怎么办？
更具体地说 - 处理这种情况的正确方法是什么
对于某些 d，经典 B 树将非根节点的键计数限制在 d 和 2d 之间。这意味着只有在下溢已经发生并且参与合并的其他节点具有最小占用率时才可能合并节点。连同从父节点提取的分隔键，这使得键计数为 (d - 1) + d + 1 = 2d，这是适合节点的最大值。在下降的路上合并 'just in case' 是不可能的。
在非常具体的情况下，我正在处理 BTree 中的删除问题
M=5 - 即 - 节点中键的最大数量为 4，节点中键的最小数量为 2
现在，当我接近一个节点时，使用防御方法（我必须使用这种方法）在 BTree 中删除时，我必须保证它比所需的最小值多一个键。
这是我的问题 - 假设我有一个带一把钥匙的根和两个带两个钥匙的 children。 当我接近这些 children 之一时，我将必须保证它至少有 3 个键（因为 M=5）。
我有两种方法 - 向邻居借用或向父亲借用并合并。我不能从邻居那里借用，因为它至少有 2 个键，但是从父亲那里借用并合并创建了一个具有 5 个键的节点 - 它超过了允许键的最大值（因为 M = 5）。
遇到这种情况怎么办？ 更具体地说 - 处理这种情况的正确方法是什么
对于某些 d，经典 B 树将非根节点的键计数限制在 d 和 2d 之间。这意味着只有在下溢已经发生并且参与合并的其他节点具有最小占用率时才可能合并节点。连同从父节点提取的分隔键，这使得键计数为 (d - 1) + d + 1 = 2d，这是适合节点的最大值。在下降的路上合并 'just in case' 是不可能的。