PostgreSQL blink-tree 实现以及和 PolarDB blink-tree 对比

PostgreSQL的blink-tree实现方式引用了Lehman和Yao的高并发B树管理算法及V. Lanin和D. Shasha的对称并发B树算法。

Blink-tree的核心变化包括增加link指针和high key字段。

与PolarDB的blink-tree相比，Blink-tree在搜索操作中没有使用lock-coupling，而在SMO操作中使用自下而上的latch coupling。

Blink-tree通过增加link-page和high key来解决插入和搜索时的问题。

在标准的blink-tree中，搜索操作不需要进行lock coupling，只需加当前层的锁。

SMO操作中，Blink-tree持有子节点锁并加父节点锁，避免了lock coupling的问题。

在插入父节点时，可以释放子节点的锁，重新遍历B树以插入父节点。

Vladimir Lanin的Concurrent Btree提供了进一步的优化，强调了在插入过程中只锁定一个节点的方式。

Blink-tree允许插入和搜索时仅锁定一个节点，提升了并发性能。

在插入父节点时，可以通过保存的记忆列表或重新遍历来找到目标节点。

Blink-tree的设计权衡了复杂性和性能，避免了出现多个link page的情况。