lehman blink-tree and Vladimir Lanin cocurrent BtreePosegreSQL blink-tree 实现方式引用了两个文章Lehman and Yao’s high-concurrency B-tree management algorithmV. Lanin and D. Shasha, A Symmetric Concurrent B-Tree AlgorithmMySQL InnoDB 的 btree 实现主要参考的是R. Bayer & M. Schkolnick Concurrency of operations on B-trees March 1977lehman blink-treeBlink-tree 的 2 个核心变化Adding a single “link” pointer field to each node.这里有一个当时时间点的背景, 我们现在见到的大部分的 Btree 实现里面, 都会有 left/right point 指向 left/right page. 但是当时对标准 Btree 的定义并没有这个要求. Btree 是非叶子节点也保存数据, B+tree 是只有叶子节点保存数据, 从而使 btree height 尽可能低. 但是并没有严格的要求把叶子节点连接到一起.但是总体而言, 对 Btr
...
继续阅读
(46)