BLink树插入操作

Question

在雷曼与姚(1981)中引入的雷曼与姚(1981)声称any insert operation need at most 3 locks simultaneously。

我很难找到一个获得3个锁的具体场景。什么情况？

Answer 1

当下列情况出现时，就会出现这种情况：

1. 拆分叶。叶节点(最初是A)被拆分(分为A1和A2)，因此需要将拆分键(max(A1))插入到父节点(T)中。
2. 父节点具有链接。父节点T还具有指向S的有效链接指针。该值必须插入到S中，而不是T中。

这三个锁是：

1. 在叶节点A1上:防止进一步分割该节点(以及其链接指向的节点)
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锁方案实际上只是一小部分时间。

简略的图解。