BLinkTree 正确性的疑问

[wine99]

请问插入的时候，为什么不会发生这样的情况：

树的各个节点均已满，一个线程P企图插入，它下降到了某个叶节点，此时另外几个线程也开始插入，它们下降了不同的叶节点然后插入结束，导致旧root分裂，新root生成，并且导致旧root所在那一层再次满了，这时线程P向上回溯，回溯到旧root后依然要进行分裂，可是线程P并不知道旧root的parent（也就是新root）是谁。

您的代码中，下面这行代码

aili/blink/blink_tree.c

Line 133 in a2f3225

assert(blink_node_is_root(left));

似乎表明这样的情况并不会发生，如果您还记得这篇paper的话，可以解答一下吗？谢谢！

[starrocks-xupeng]

旧 root 发生改变的话，正常插入旧 root 或者最多往右移动一个节点（假设旧 root 分裂了一个右节点）然后插入就行了，不需要知道更上层的新 root。

[wine99]

正常插入旧 root 或者最多往右移动一个节点（假设旧 root 分裂了一个右节点）然后插入就行了

我感觉这个不太对。

我发现 Postgres 的实现也采用了 Blinktree 的变体，它的 readme 里面写道，root split 时可能需要 re-descending，见 https://github.com/postgres/postgres/blob/205db0114e03496f1d6febf276374900b6314e67/src/backend/access/nbtree/README#L112-L137

[starrocks-xupeng]

理论上是有这个可能性的，实际发生条件会非常苛刻，甚至永远不会发生，你看他文档里自己也说了 in principle 和 rare