如何從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

按「初始化書」，然後按以刪除按鈕。這將涵蓋所有情況。在推動每個按鈕之前嘗試並預測新的樹狀態，並嘗試識別這些情況是如何獨特的。