Database · 理论基础 · B link Tree

这篇文章将会介绍一份B+树并发控制协议。 论文链接:Efficient Locking for Concurrent Operations on B-Trees 文章分为2部分,第一部分通过伪代码介绍这份协议,第二部分证明这份协议是正确的。 严格意义上来说这是B link树而不是B+树,具体区别在于B link树每个节点上都会附加一个key和指针。附加的key(如下图左边的红色圆点)值等于同一层下一节点的第一个key(右边红色圆点),附加的指针(红色箭头)指向同一层下一