data-structures - B+树删除

Question

所以我有这个 B+ 树：

我必须在这里删除 49。我该怎么做？

会不会是这样：

还是像这样？：

标签： data-structures

Answer 1

1. 删除 49 后，将 48 合并到包含 32 和 40 的相邻节点中。我们最终得到叶节点 (32, 40, 48)。
2. 合并后，将其父节点从（45）更新为（32）。
3. 由于节点(32)只有1个指针，所以可以将其剔除。

因此，我们最终在根的右子树上得到根节点 (32)--->(32,40,48)。

深入解释：

删除密钥有 3 种情况。删除节点的密钥后，

如果节点仍然包含多于 floor((n+1)/2) 个键：

1. 只需删除密钥。无需更新。

如果节点包含少于 floor((n+1)/2) 个键：

2. 如果相邻叶节点有备用密钥（即，给出一个密钥仍会导致其自身拥有多于 floor((n+1)/2) 个密钥），则向邻居借用一个密钥。
3. 如果邻居无法借出密钥，则将当前节点与邻居节点合并。

** 对于情况 2 和 3，请务必记住在借用或合并后更新父节点。