algorithm - 在 B Plus 树中删除后，索引中的键会被删除吗？

Question

我对 B+ 树中的删除有点困惑。我在谷歌中搜索了很多，发现当要删除的键出现在索引中时，有两种实现：

1. 删除索引中的键
2. 将键保留在索引中

https://www.javatpoint.com/b-plus-tree-deletion的算法使用第一种方式。

https://www.cs.princeton.edu/courses/archive/fall08/cos597A/Notes/BplusInsertDelete.pdf的算法使用第二种方式。

所以我真的很想知道哪个是对的。

但我更倾向于将其视为未定义的行为。在这一点上，有人可以帮我弄清楚它们之间的优缺点吗？以及如何在它们之间进行选择？

提前致谢。

Answer 1

两种方法都是正确的。

您强调的区别不是删除/不删除内部密钥，而是更新/不更新它们。

显然，当您删除一个值（即叶节点中的一个键）时，不会违反 b-plus-tree 属性：所有子值仍然在父信息规定的范围内。你永远不能通过仅仅从叶子中删除一个值来打破这个范围规则。当您更新指向该叶子的路径中的内部键（根据方法 1）时，此规则仍然有效，这仅在删除的值是其叶子中最左边的值时才需要。

请注意，这两种方法可能会在长序列的相同操作（插入、删除）之后产生完全不同的树。

但平均而言，第二种方法要做的工作会稍微少一些。不过，这种差异并不显着。