Blink-tree如何應對這種情況？

Question

在Blink樹中插入時，它將存儲從根節點到葉節點的路徑。當子節點拆分時，它會將這些更改傳播給父節點。假設當傳播研究線程A中的根節點，並且當前插入檢查堆棧（用於存儲路徑）並且發現堆棧中的底層節點是「根」。而「根」也需要分裂。它會創建一個新的根。

那麼，如果「root」已被另一個線程拆分並且「root」現在不是真正的根目錄呢？所以，創建由線程A完成的新根並不正確。

Blink-tree如何應對這種情況？

Answer 1

我不知道作者如何處理這個問題（我認爲它是真實的）。一種可能性是添加包含樹高度（深度）的標題塊以及樹葉上方每個高度的第一個塊的地址。如果你跑掉堆棧的末端，你需要鎖定這個塊並讀取它來確定一個新的根（或者更準確地說，是堆棧中樹高以上高度的第一個塊）。如果它在那裏，請解鎖標題欄並在繼續之前將該塊添加到您的堆棧中。如果新的根目錄不存在，則可以在寫入新的根目錄塊之前（在寫入新根目錄之前）創建它並將其添加到標頭塊。從理論上講，如果根在上升和下降階段之間分裂多次，這可能會發生一次以上。通過在檢查頭塊之前鎖定頭塊，並在添加新的根之前，我認爲可以保持避免死鎖的順序不變量。