B+树中的删除操作

Question

3

作为一名学生，我一直在尝试用C语言实现B+树。插入操作没问题，但删除操作却让我束手无策。我的一个问题是：当叶子节点中的关键字被删除后，内部节点中是否可以保留该关键字？当内部节点不是叶子节点的父节点时，可能会出现这种情况。我的描述清楚吗？有没有人有类似的经验？

- manuzhang

你想要一个是或否的答案吗？这是作业吗？ - Micromega

可以保留一个键吗？你的意思是“留下一个键”吗？这句话让我有些困惑。 - Joey Adams

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Dietrich Epp · Accepted Answer

在处理数据结构时，你需要问自己的问题是，“什么是不变量？”对于B+树而言，一些不变量如下：

因此，如果你决定B+树允许你保留不再对应记录的键，那很好。请确保插入和搜索算法在遵循特定的不变量集合时仍能正常工作。

通常，在任何类型的树中遇到不对应记录的键有点奇怪。我也期望在具有大扇出的B+树中纠正这个问题的成本相当小。