一次傳遞B樹刪除

Question

是否可以在一次傳遞中從B樹中刪除元素？

維基百科說：「在樹中進行一次傳遞，但在進入（訪問）一個節點之前，重構樹，以便一旦遇到要刪除的密鑰，就可以刪除它，而不會觸發任何進一步重構「 但沒有說明它是如何完成的。

Google只給我一個刪除元素的過程，這個元素不得不重構樹。

Cormen也沒有對此發表任何評論。

Answer 1

它可能在B +樹的變體名爲PO-B+ tree。在這個「準備操作B +樹」中，在通常的B +樹（引自論文）中，節點中密鑰的數量可以在n-1和2n + 1之間，而不是n和2n。對於刪除操作（本文中稱爲PO刪除），您只需合併（在本文中稱爲「catenate」）所有可合併（或從鄰居獲取密鑰）的節點（除根節點之外）朝向葉子。對於PO插入操作，您拆分所有節點（包括根）。描述在文章中給出。

只有在多線程環境中使用該樹時，此搶先重構纔有意義，因爲它減少了鎖定並提高了協調性。如果只有一名演員訪問一棵樹，它不會付費。