BLink 树插入操作

Question

Lehman and Yao (1981)中介绍的B-link tree声称any insert operation need at most 3 locks simultaneously。

我很难找到一个获取3个锁的具体场景。 场景是什么？

Answer 1

场景出现时间：

1. Split leaf. 一个叶节点（原来是A）被拆分（分为A1和A2），因此拆分键(max(A1))需要插入父节点(T)。
2. 父节点有link。父节点 T 也有一个指向 S 的有效 link 指针。该值必须插入 S 而不是 T.

三把锁是：

1. 在叶节点上A1：防止进一步分裂该节点（以及其link指向的节点）
2. On T：当执行Move.right时（见下文）。
3. On S：当执行Move.right时（见下文）。

[Move.right]
while True:
  S = scannode(v, T)
  if isLinkPointer(S):
    lock(S)   # <-- 3 locks *
    unlock(T) # <-- 2 locks
    T = S

锁2和3更像是向右移动时必须获得的“转换锁”。所以3锁的场景真的只是极小的时间。

A Crude Graphic Illustration.