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

Question

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

那么，如果“根”已经被另一个线程分割并且“根”现在不是真正的根怎么办。因此，由线程 A 创建新根是不正确的。

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

Answer 1

我不确定作者打算如何处理这个问题（我确实认为这是真的）。一种可能性是添加一个包含树高度（深度）的标题块和叶子上方每个高度的第一个块的地址。如果您曾经跑出堆栈的末尾，则需要锁定该块并读取它以确定新的根（或者更准确地说，是堆栈中高于树高的第一个块）。如果它在那里，请解锁标题块并将该块添加到您的堆栈中，然后再继续。如果新根不存在，您可以创建它并将其添加到头块，然后再写回索引块（在写入新根之后）。从理论上讲，如果根在上升和下降阶段之间多次分裂，这可能会发生不止一次。