如何从 b 树中删除元素？
我正在尝试了解 b 树，我能找到的每个来源似乎都忽略了如何在保留 b 树属性的同时从树中删除元素的讨论。
有人可以解释该算法或向我指出可以解释其工作原理的资源吗？
I'm trying to learn about b-tree and every source I can find seem to omits the discussion about how to remove an element from the tree while preserving the b-tree properties.
Can someone explain the algorithm or point me to resource that do explain how it's done?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
维基百科页面上有对此的解释。 B 树 - 删除
There's an explanation of it on the Wikipedia page. B-tree - Deletion
如果你还没有看过，我强烈推荐《卡门与卡门》。 al算法导论第三版。
没有对其进行描述，因为这些操作自然源于 B 树属性。
由于节点中的元素数量有下限，因此如果删除元素违反了此不变量，则需要恢复它，这通常涉及与邻居合并（或窃取其一些元素）。
如果与邻居合并，则需要删除父节点中的一个元素，这会触发相同的算法。然后你递归地应用，直到到达顶部。
B 树没有重新平衡（至少不是我看到的），因此它比维护红黑树或 AVL 树要简单得多，这可能就是为什么人们不觉得有必要写关于删除的内容。
If you haven't got it yet, I strongly recommend Carmen & al Introduction to Algorithms 3rd Edition.
It is not described because the operations naturally stem from the B-Tree properties.
Since you have a lower-bound on the number of elements in a node, if removing your elements violates this invariant, then you need to restore it, which generally involves merging with a neighbour (or stealing some of its elements).
If you merge with a neighbour, then you need to remove an element in the parent node, which triggers the same algorithm. And you apply recursively till you get to the top.
B-Tree don't have rebalancing (at least not those I saw) so it's far less complicated that maintaining a red-black tree or an AVL tree which is probably why people didn't feel compelled to write about the removal.
您正在谈论哪些 B 树？是否有相连的叶子？此外，删除项目的方式也有多种（从上到下、从下到上等）。本文可能会有所帮助：B 树、阴影和克隆（甚至尽管有许多与文件系统相关的特定内容）。
About which b-trees are you talking about? With linked leaves or not? Also, there are different ways of removing an item (top-bottom, bottom-top, etc.). This paper might help: B-trees, Shadowing, and Clones (even though there are many file-system specific related stuff).
CLRS（第二版）的删除示例可在此处找到：http://ysangkok。 github.io/js-clrs-btree/btree.html
按“Init book”，然后按顺序按下删除按钮。这将涵盖所有情况。在按下每个按钮之前尝试预测新的树状态，并尝试识别这些情况的独特之处。
The deletion example from CLRS (2nd edition) is available here: http://ysangkok.github.io/js-clrs-btree/btree.html
Press "Init book" and then push the deletion buttons in order. That will cover all cases. Try and predict the new tree state before pushing each button, and try to recognize how the cases are all unique.