Blink-tree如何应对这种情况？

Question

在Blink树中插入时，它将存储从根节点到叶节点的路径。当子节点拆分时，它会将这些更改传播给父节点。假设当传播研究线程A中的根节点，并且当前插入检查堆栈（用于存储路径）并且发现堆栈中的底层节点是“根”。而“根”也需要分裂。它会创建一个新的根。

那么，如果“root”已被另一个线程拆分并且“root”现在不是真正的根目录呢？所以，创建由线程A完成的新根并不正确。

Blink-tree如何应对这种情况？

Answer 1

我不知道作者如何处理这个问题（我认为它是真实的）。一种可能性是添加包含树高度（深度）的标题块以及树叶上方每个高度的第一个块的地址。如果你跑掉堆栈的末端，你需要锁定这个块并读取它来确定一个新的根（或者更准确地说，是堆栈中树高以上高度的第一个块）。如果它在那里，请解锁标题栏并在继续之前将该块添加到您的堆栈中。如果新的根目录不存在，则可以在写入新的根目录块之前（在写入新根目录之前）创建它并将其添加到标头块。从理论上讲，如果根在上升和下降阶段之间分裂多次，这可能会发生一次以上。通过在检查头块之前锁定头块，并在添加新的根之前，我认为可以保持避免死锁的顺序不变量。