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

Question

在Blink树中执行插入时，它将存储从根节点到叶节点的路径。并且当子节点拆分时，它会将这样的更改传播到父节点。假设当传播搜索线程A中的根节点时，当前插入检查堆栈(用于存储路径)，并发现堆栈上的底部节点是“根”。而“根”也需要拆分。它将创建一个新的根目录。

那么，如果" root“已经被另一个线程拆分，而"root”现在不是真正的root，该怎么办呢？因此，由线程A创建新根是不正确的。

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

Answer 1

我不确定作者打算如何处理这个问题(我确实认为这是真实的)。一种可能性是添加一个标题块，其中包含树的高度(深度)和树叶上方每个高度的第一个块的地址。如果您曾经超出堆栈的末尾，则需要锁定此块并读取它以确定新的根(或者，更准确地说，是位于堆栈中树高度以上的第一个块)。如果存在，请解锁标头块并将其添加到堆栈中，然后再继续。如果新的根不存在，您可以在写回索引块之前创建它并将其添加到头块中(在写入新的根之后)。理论上，如果根在向上和向下阶段之间被多次分割，这种情况可能会发生不止一次。通过在检查头块和添加新根之前锁定它，我认为您可以维护排序不变量以避免死锁。