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