database - BLink 树插入操作

Question

Lehman 和 Yao (1981)中B-link tree介绍的.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 锁场景实际上只是极小的时间。

粗略的图解说明。