PostgreSQL blink-tree 实现以及和 PolarDB blink-tree 对比
内容提要
PostgreSQL的blink-tree实现方式引用了两个文章的算法。Blink-tree的核心变化是增加了link指针和high key字段。与PolarDB的blink-tree相比，Blink-tree没有使用lock-coupling进行search操作，而在SMO操作中使用了自下而上的latch coupling。Blink-tree通过增加link-page和high key来解决插入和搜索时的问题。与PolarDB类似，Blink-tree也可以使用类似的方式插入父节点以尽早释放子节点的latch。
延伸解读
PostgreSQL 与 PolarDB 的搜索加锁策略差异
PostgreSQL 的 blink-tree 在搜索时仅对当前节点加锁，不采用 lock-coupling；而 PolarDB 的 blink-tree 在搜索时使用自上而下的 lock-coupling。这一差异直接影响并发行为：PostgreSQL 方式减少了锁持有时间，但依赖 high key 和 link 指针来保证正确性；PolarDB 方式通过锁耦合避免搜索过程中节点分裂导致的数据不一致。
SMO 操作中的自下而上锁耦合
PostgreSQL 的 blink-tree 在结构修改操作（SMO）中采用自下而上的锁耦合：先持有子节点锁，再申请父节点锁。由于搜索操作不需要锁耦合，这种自下而上的方式不会引发死锁。同一时刻最多持有三个节点的锁（子、父、父的 link page），且大多数情况下 link page 只有一个，简化了并发控制。
link page 数量与并发性能的权衡
PostgreSQL 的 blink-tree 设计避免了多个 link page 的出现：因为分裂未完成时不会释放页面锁，新的插入无法进行。但这意味着搜索或插入可能需要沿着多个 link page 才能到达目标页面。文章指出，如果采用类似 PolarDB 的方式，在插入子节点后立即释放锁并重新遍历插入父节点，则可能出现多个 link page，增加复杂性。PostgreSQL 选择了更安全的权衡。
Vladimir Lanin 的优化思路与 PostgreSQL 的取舍
Vladimir Lanin 的 Concurrent Btree 提出在 SMO 中每次只锁一个节点，并在 half-split 后释放所有锁，从而提升并发性。PostgreSQL 并未完全采用这一优化，而是保留了自下而上的锁耦合，主要出于安全性考虑。文章认为，类似 PolarDB 的做法——插入子节点后释放锁并重新遍历插入父节点——可以进一步提前释放子节点锁，但需要权衡实现复杂度。
Q&A
PostgreSQL的blink-tree实现有什么核心变化？
PostgreSQL的blink-tree实现增加了link指针和high key字段。
PostgreSQL的blink-tree与PolarDB的blink-tree有什么主要区别？
PostgreSQL的blink-tree在搜索操作中没有使用lock-coupling，而PolarDB使用了lock-coupling进行搜索操作。
Blink-tree是如何解决插入和搜索时的问题的？
Blink-tree通过增加link-page和high key来解决插入和搜索时的问题。
在SMO操作中，PostgreSQL的blink-tree是如何处理锁的？
在SMO操作中，Blink-tree持有子节点锁并加父节点锁，避免了lock coupling的问题。
Blink-tree的设计在复杂性和性能上有什么权衡？
Blink-tree的设计权衡了复杂性和性能，避免了出现多个link page的情况。
Vladimir Lanin的Concurrent Btree对blink-tree有什么优化？
Vladimir Lanin的Concurrent Btree强调在插入过程中只锁定一个节点的方式，提供了进一步的优化。
