如何从b-tree中删除元素？

Question

我正在尝试了解有关B树和每个我可以找到的源似乎都省略了有关如何从树中删除元素同时保留B树属性的讨论。

有人可以解释算法或指向我的资源，解释它是如何完成的？

Answer 1

在Wikipedia页面上有一个解释。 B-tree - Deletion

Answer 2

如果你还没有，我强烈建议卡门& al 算法简介第3版。

它没有被描述，因为操作自然来自B-Tree属性。

由于您对节点中元素数量的下限，如果删除元素违反了这个不变量，那么您需要恢复它，这通常涉及与邻居合并（或窃取其中的一些元素） 。

如果与邻居合并，则需要移除父节点中的元素，这会触发相同的算法。你递归地申请，直到你到达顶端。

B-Tree没有重新平衡（至少不是我看到的），所以维护一棵红黑树或一棵AVL树可能不那么复杂，这可能是为什么人们不会被迫写关于去除。

Answer 3

关于哪些b-树你在说什么？有链接的叶子或不？此外，删除项目有不同的方式（上下，下下等）。本文可能有帮助：B-trees, Shadowing, and Clones（即使有许多文件系统特定的相关内容）。

Answer 4

从CLRS（第2版）的删除例子可以在这里找到：http://ysangkok.github.io/js-clrs-btree/btree.html

按“初始化书”，然后按以删除按钮。这将涵盖所有情况。在推动每个按钮之前尝试并预测新的树状态，并尝试识别这些情况是如何独特的。