B+树删除

Question

所以我有这个B+树：

​

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

会是这样的吗：

​

或者像这样？：

​

Answer 1

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

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

深度解释：

删除密钥有3种情况。在删除节点的关键字之后，

如果节点仍包含楼层((n+1)/2)以上的关键点：

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

如果节点包含小于地板((n+1)/2)的关键字：

1. 如果邻居叶节点有空闲的密钥(即，分发密钥仍然会导致其本身具有多于floor((n+1)/2)密钥)，则从无法借出密钥的邻居处借用密钥，将当前节点与邻居节点合并。

**对于第二种和第三种情况，请始终记住在借用或合并后更新父节点。