baotiao
·
PostgreSQL blink-tree 实现以及和 PolarDB blink-tree 对比
💡
原文中文，约4700字，阅读约需12分钟。
📝
内容提要
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的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的情况。
➡️
