BLink Tree insert operation

Question

The B-link tree introduced in Lehman and Yao (1981) claims that any insert operation need at most 3 locks simultaneously.

I have a hard time to find a concrete scenario where 3 locks are acquired. What is the scenario?

Answer 1

The scenario appears when:

1. Split leaf. A leaf node (originally A) is split (into A1 and A2), hence the split key (max(A1)) needs to be inserted into the parent node (T).
2. Parent node has link. The parent node T also has a valid link pointer that points to S. The value has to be inserted into S instead of T.

The three locks are:

1. On leaf node A1: to prevent further split of this node (and also nodes that its link points to)
2. On T: when Move.right is performed (see below).
3. On S: when Move.right is performed (see below).

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

Lock 2 and 3 are more like "transitions locks" that has to be acquired when moving right. Therefore the 3 lock scenario really is just a tiny tiny amount of time.

A Crude Graphic Illustration.