Efficient Locking for Concurrent Operations on B-Trees

[mrdrivingduck]

p650-lehman.pdf

[mrdrivingduck]

几种面向磁盘的存储结构的约定和特点：

• B-Tree：以 disk page 为单元的自平衡多叉查找树，多个 search key 的 search value 可以保存在同一个 page 上，按 search key 顺序排列，从而避免节点过多，树过高，在搜索时发生多次 I/O 操作
• B+-Tree：在 B-Tree 的基础上，非叶子节点上只保存 key，只有叶子节点可以保存 value，这样可以让中间层的节点上存放尽可能多的 key，进一步减少节点的数量，避免树过高；对所有 key 的查找都要到达叶子节点，查找代价稳定；另外叶子节点之间用左右指针相连，方便范围查询

[mrdrivingduck]

索引的搜索和插入可能发生的并发问题：

• 进程 1 在父节点上查找到需要搜索的下一层节点
• 进程 2 在下一层节点上进行了插入操作，导致下层节点分裂，索引结构发生了变化
• 进程 1 进入了错误的下一层节点

B-Tree 索引的并发设计经历了锁粒度从粗到细的发展。

锁整个子树？

Lock-coupling: 沿索引的访问节点路径依次加锁，先锁住 parent node，确认要访问的 child node 后，再锁住 child node，访问到 child node 后释放 parent node 的锁；只要同时持有父子节点的锁，其它进程就无法使这个 sub-tree 发生 SMO，这样是并发安全的

[mrdrivingduck]

本文提出 B-link-Tree，允许更高的并发性。

引入的修改：

1. 每个节点加入一个 high key 字段，用于表示这个节点子树里的最大 key 值
2. 引入了一个 link pointer，指向右侧隔壁节点；由 B-Tree 的性质可知，右侧隔壁节点的最小 key 值肯定大于 high key

在之前的并发问题中，出现的问题是，由于并发插入引发了 SMO，导致另一个进程查询错子树了，实际上要查询的数据已经在右兄弟子树中。有没有什么办法能够识别出访问错子树了，并且能够修正到正确的子树上去？

1. high key 可以识别访问错误，如果要查找的 key 已经大于当前节点的 high key 了（理论上这不该出现），那么说明这个节点一定发生 SMO 了
2. 可以顺着 link pointer 找到右兄弟节点去，完成查询

索引节点分裂的步骤如下：

这样理论上可以不再需要 lock-coupling 了，因为索引分裂的中间状态也是合法的：

1. 如果需要发生分裂，则将被分裂的节点复制一份并进行构造，right link 和 high key 应该都不需要改，只需要改 key set
2. 分裂节点构造完后，修改被分裂节点上的 key set，更新 high key，更新 right link 到分裂节点
3. 将新建的分裂节点更新到 parent 节点，递归向上

1 和 2 之间的索引查询，由于其他进程还无法访问到分裂页面，其它页面的结构和内容也还暂时没有发生改变，所以是合法的；2 和 3 之间的索引查询，由于 parent 节点暂未更新，所以查询都会进入到被分裂节点中，但依旧可以通过 high key 和 right link 进入到分裂节点，所以也是合法的。3 之后的索引查询，符合条件的查询将会直接进入到新的分裂节点中。

最多同时锁三个节点？

[mrdrivingduck]

还需要看下 PostgreSQL 中的 B-Link-Tree 工程实现。