缺失 - M = 5

Question

我处理在B树的删除在非常特殊的情况下

M = 5 - 即 - 在节点密钥的最大数目是4并且在键的最小数量节点是2

现在当使用防御方法（我必须使用这个）在BTree中删除时，当我接近一个节点时，我必须保证它有一个以上所需的关键字。

这是我的问题 - 比方说，我有一个根和一个键，两个孩子每个都有两个键。 当我接近这些孩子时，我必须保证它至少有三把钥匙（因为M = 5）。

我有两种方式来做到这一点 - 从邻居借用或从父亲借来并入。我不能借用邻居，因为它拥有至少2个密钥，但是从父亲借用并且合并会创建一个包含5个密钥的节点 - 并且它超过了允许密钥的最大值（如M = 5）。

在这种情况下该怎么办？ 更具体地说 - 对待这种情况的正确方法是什么

Answer 1

古典B树约束非根节点的密钥计数位于d和2d之间，对于某些d。这意味着仅当下溢具有已经发生且合并中涉及的其他节点具有最小占用率时才可能合并节点。与从父节点拉出的分隔符​​一起，这使得（d-1）+ d + 1 = 2d的关键点数是适合节点的最大值。一路下滑，“万一”是不可能的。