在B +樹上刪除

Question

作爲一名學生，我一直試圖在C中自己實現B +樹。插入是好的，但刪除阻止我。我的一個問題是這樣的： 在葉節點中的鍵已被刪除的情況下，在內部節點中保持鍵是否可以？ 當內部節點不是葉的父節點時，可能會發生這種情況。 我的描述是否足夠清晰？有沒有人有類似的經歷？

Answer 1

在處理數據結構時，您應該問自己的問題是「什麼是不變量？」對於B +樹，一些不變的是：

• 記錄存儲在葉節點，
• 葉節點必須是至少半滿。

因此，如果您決定B +樹允許您保留不再對應記錄的鍵，那很好。只要確定你的插入和搜索算法仍然適用於你的特定不變量。

一般來說，在任何種類的樹中遇到與其中一個記錄不對應的密鑰都是有點古怪的。我還希望在一個有大扇出的B +樹中糾正它的代價是相當小的。