TAOCP 6.2.4 Exercise 10

We consider a large file organized as a $B$-tree of order $m\ge 3$ as defined in Section 6.

taocpmathematicsalgorithmsvolume-3hard

Section 6.2.4: Multiway Trees

Exercise 10. ▶ [35] Discuss how a large file, organized as a $B$-tree, can be used for concurrent accessing and updating by a large number of simultaneous users, in such a way that users of different pages rarely interfere with each other.

Little is known, even for otherwise equivalent algorithms, about the optimization of storage allocation, minimization of the number of required operations, and so on. This area of investigation must draw upon the most powerful resources of both pure and applied mathematics for further progress., ANTHONY G. OETTINGER (1961)

Verified: no
Solve time: 2m04s

Setup

We consider a large file organized as a $B$-tree of order $m\ge 3$ as defined in Section 6.2.4. The tree satisfies:

  • every node has at most $m$ children;
  • every non‑root, non‑leaf node has at least $\lceil m/2\rceil$ children;
  • the root has at least $2$ children (unless it is a leaf);
  • all leaves are on the same level and carry no information (in the basic $B$-tree) or contain the actual data records (in the $B^*$-tree variant);
  • a non‑leaf node with $k$ children contains $k-1$ keys in increasing order.

Each node resides on a single disk page. A multi‑user environment executes three kinds of transactions: search (read‑only), insertion, and deletion. We assume a lock manager that grants shared (S) locks for reading and exclusive (X) locks for writing on individual pages. Locks are held only for the short duration of a single tree operation (latch‑style), not for the lifetime of a user transaction; this is sufficient to maintain structural consistency of the $B$-tree itself. Higher‑level transaction isolation (e.g., serializability) is a separate concern.

The goal is to allow many users to access and update the tree concurrently such that users working on different pages rarely block each other.

Solution

1. Search (read‑only) protocol

A search starts at the root and descends to a single step at a time.

  1. Acquire an S‑lock on the root page.
  2. While the current node is not a leaf:
    • Search the keys in the current node to determine the child pointer $P_i$ to follow.
    • Acquire an S‑lock on the child page pointed to by $P_i$.
    • Release the S‑lock on the parent page.
    • Make the child the current node.
  3. At the leaf level, perform the required access (read the record or confirm absence), then release the S‑lock on the leaf.

Because S‑locks are compatible, any number of searches can proceed simultaneously down different branches. A search holds at most two S‑locks at any moment (parent and child), and the parent lock is released as soon as the child is locked. No search ever waits for an insertion or deletion unless it reaches a page that is currently being restructured (in which case it waits for the X‑lock to be released).

2. Insertion protocol - lock coupling with early release

Insertions modify the tree structure and therefore require X‑locks. The standard technique is lock coupling (also called crabbing): we hold an X‑lock on the current node while acquiring an X‑lock on the child, then decide whether the parent lock can be released.

Let a node be called safe for insertion if it currently contains at most $m-2$ keys (i.e., it has fewer than $m-1$ children). If a node is safe, inserting a new key into its subtree cannot cause it to split, because a split occurs only when a node receives its $m$-th key.

Insertion algorithm (for a new key $K$):

  1. Acquire an X‑lock on the root.
  2. Set current = root.
  3. While current is not a leaf (i.e., not at level $l-1$):
    • Search the keys in current to find the child pointer $P_i$ that leads to the insertion position.
    • Acquire an X‑lock on the child page $C$.
    • If $C$ is safe for insertion (has $\le m-2$ keys), release the X‑lock on current.
    • Set current = C.
  4. Now current is the node on level $l-1$ where the new key belongs. Insert $K$ into current.
  5. Handle splits bottom‑up:
    • If current now has $m$ keys, split it into two nodes as described in (4) of the section, creating a new key $\widehat{K}$ and a new pointer $P'$.
    • Move up to the parent (which we still hold an X‑lock on, because we only released a parent lock when its child was safe). Insert $\widehat{K}$ and $P'$ into the parent.
    • If the parent now has $m$ keys, split it similarly, and continue upward.
    • If the root splits, create a new root node containing the single promoted key and pointers to the two halves; this increases the tree height by one.
  6. Release all remaining X‑locks (at most one per level on the path from the root to the lowest unsafe ancestor).

Why early release is correct:
When we release the X‑lock on a parent $P$ because its child $C$ is safe, we guarantee that no split will ever propagate from $C$ to $P$. The keys and pointers in $P$ that refer to $C$ will never change again during this insertion. Any other transaction that subsequently locks $P$ will see a consistent state: the subtree rooted at $C$ is a valid $B$-tree (possibly being modified deeper down, but those modifications are protected by locks on the deeper nodes). Therefore releasing $P$ does not violate the $B$-tree invariants.

3. Deletion protocol

Deletion is symmetric. A node is safe for deletion if it contains more than the minimum number of keys, i.e., at least $\lceil m/2\rceil$ keys (equivalently, more than $\lceil m/2\rceil-1$ keys). If a node is safe, deleting a key from its subtree cannot cause it to underflow (merge with a sibling or borrow keys), so the parent’s separator key and pointer remain unchanged.

The deletion algorithm mirrors insertion:

  1. Acquire X‑lock on root.
  2. Descend with lock coupling: at each step, lock the child; if the child is safe for deletion, release the parent lock.
  3. At the leaf level (or the level where the key resides), delete the key.
  4. If the node now has fewer than $\lceil m/2\rceil-1$ keys, handle underflow by merging with a sibling or redistributing keys (borrowing). This may require modifying the parent (which we still hold locked because the child was not safe). Propagate upward if necessary.
  5. If the root ends up with only one child, delete the root and make its child the new root (tree height decreases by one).
  6. Release all held locks.

4. Overflow technique (Bayer-McCreight)

The section describes an overflow (or rotation) technique that reduces the frequency of splits. When a node becomes full ($m$ keys) during insertion, before splitting we examine its right sibling (accessible via the parent). If the sibling has $j \le m-2$ keys, we redistribute the $m+j$ keys evenly:

  • leave $\lfloor (m+j)/2\rfloor$ keys in the left node,
  • replace the parent’s separator key by the new median,
  • put the remaining $\lceil (m+j)/2\rceil$ keys (including the old separator) into the right node.

This avoids a split entirely, so the parent node is not modified except for its separator key. In the locking protocol, this means we do not need to hold the parent’s X‑lock for a split; we only need to update the separator key. To perform overflow safely:

  • While descending, we already hold an X‑lock on the parent $P$ and acquire an X‑lock on the full child $C$.
  • We also need to lock the right sibling $S$. To avoid deadlock, we always lock siblings left‑to‑right: after locking $C$, we lock $S$ (which is to the right). Since the tree is always traversed top‑down and left‑to‑right, no cycle can form.
  • If $S$ has $< m-1$ keys, we perform the redistribution, update $P$’s separator key, release $S$ and $C$, and continue (the insertion is complete). The parent lock can then be released (if $C$ was safe after redistribution? Actually after redistribution both nodes have $\le m-1$ keys, so no further structural change is needed; the parent lock is released normally).
  • If $S$ is also full ($j = m-1$), we proceed with a three‑way split as described in the section (creating three nodes each about two‑thirds full). This requires holding $P$, $C$, and $S$ locked during the split.

Overflow significantly reduces the height of the locked region because many insertions that would have caused a split (and thus forced retention of ancestor locks) now terminate at the leaf level.

5. $B^*$-tree variant with sibling pointers

When the file is organized as a $B^*$-tree (records stored in leaves, leaves linked in symmetric order), we can further improve concurrency for leaf splits. Each leaf page contains a next‑leaf pointer to its right neighbour.

During a leaf split:

  1. Hold X‑lock on the full leaf $L$.
  2. Allocate a new leaf $L'$, move the larger half of the records to $L'$.
  3. Atomically update $L$’s next‑leaf pointer to point to $L'$ (and set $L'$’s next‑leaf pointer to $L$’s former successor).
  4. Insert the new separator key and pointer to $L'$ into the parent (using the standard insertion protocol, which may propagate upward).

Readers performing sequential scans can traverse leaves by following next‑leaf pointers. They need only a momentary S‑lock (or latch) on the current leaf to read the pointer to the next leaf; they never need to lock the parent. This allows high‑concurrency range queries.

6. Deadlock freedom

All locks are acquired in a strict top‑down order (root to leaves). When a sibling must be locked (for overflow), it is locked after its left sibling, i.e., left‑to‑right. Locks are released either immediately (early release) or in the reverse order (bottom‑up after splits/merges). Because no transaction ever waits for a lock on an ancestor while holding a lock on a descendant, and sibling locks follow a fixed global order, deadlock cannot occur.

Verification

We verify the most failure‑prone part: the early release condition in the insertion protocol.

Invariant. At any moment during an insertion, for every node $P$ that currently holds an X‑lock by the inserting transaction, the following holds:

  • The subtree rooted at $P$ is a valid $B$-tree (possibly with a temporary “overfull” node on the insertion path that has not yet been split).
  • The keys and child pointers in $P$ that refer to already‑processed children (i.e., children for which the lock has been released) are final and will not change during the remainder of this insertion.

Proof.
We proceed by induction on the descent.

Base. The root is locked initially. The invariant holds trivially.

Step. Suppose we hold an X‑lock on a node $P$ and the invariant holds for $P$. We determine the child $C$ to visit, acquire an X‑lock on $C$, and then decide whether to release $P$.

Case 1: $C$ is safe for insertion (has $\le m-2$ keys).
Because $C$ has at most $m-2$ keys, inserting a key anywhere in the subtree rooted at $C$ can add at most one key to $C$ (if the insertion happens directly in $C$) or cause a split below $C$ that promotes a key into $C$. In either case, $C$ will end up with at most $m-1$ keys. $C$ will never reach $m$ keys, so it will never split. Consequently, the pointer from $P$ to $C$ and the separator key in $P$ that delimits $C$’s range will never change. The subtree rooted at $C$ will remain a valid $B$-tree (the insertion algorithm guarantees this by handling any splits entirely within $C$’s subtree). Therefore releasing the X‑lock on $P$ is safe: any other transaction that later locks $P$ will see a consistent separator and pointer, and the $B$-tree invariants are preserved globally. The invariant now holds for $C$ (which we still hold locked) and for all deeper nodes we will visit.

Case 2: $C$ is not safe (has $m-1$ keys).
We must keep $P$ locked because a split in $C$’s subtree could promote a key into $C$, making it overfull ($m$ keys), which would force a split of $C$ and an insertion into $P$. By retaining the lock on $P$, we ensure that no other transaction can observe $P$ in an intermediate state (e.g., after $C$ has split but before the promoted key is inserted into $P$). The invariant continues to hold for both $P$ and $C$.

Boundary case - root split.
If splits propagate all the way to the root, we hold the root’s X‑lock throughout. When the root splits, we create a new root node, update the root pointer (a single global variable), and then release the lock. This is atomic with respect to other transactions because they must acquire the root lock before reading the root pointer.

Independent check - overflow.
When overflow is used, we lock parent $P$, full child $C$, and right sibling $S$ (in that order). Redistribution changes the keys in $C$ and $S$ and updates the separator key in $P$. No other node is affected. After redistribution, both $C$ and $S$ have $\le m-1$ keys, so no further structural change is needed. The locks on $C$ and $S$ are released, then $P$ is released (or retained if we are higher up). The $B$-tree invariants (order, key ranges, leaf level) are maintained because the keys are simply re‑partitioned between two siblings and the parent’s separator is updated to the new median. This matches the description in the section and does not violate the locking protocol.

Independent check - $B^*$-tree leaf split.
The new leaf $L'$ is fully initialized before the next‑leaf pointer of $L$ is updated. A concurrent scanner holding a latch on $L$ reads the next‑leaf pointer after the update and therefore sees $L'$. It then latches $L'$ and continues. No scanner can “miss” $L'$ because the pointer update is atomic (protected by $L$’s X‑lock). The parent is updated later via the standard insertion protocol, which is already proven safe. Thus sequential scans remain correct.

All critical sections are protected, early release is justified by the safety condition, and deadlock is impossible. This completes the proof. ∎

Notes

  • The protocol described is essentially the Bayer-Schkolnick locking scheme (1977) adapted to the $B$-tree definition of this section. The use of overflow (rotation) is original to Bayer and McCreight (1972) and fits naturally into the lock‑coupling framework.
  • In a real system, latches (short‑duration, non‑transactional locks) are used for the structural modifications described here, while transactional locks (with longer duration) protect logical data consistency. The two layers operate independently.
  • The $B^$-tree sibling pointers are crucial for high‑concurrency range queries; they were popularized by the B$^+$-tree (Comer, 1979) but the idea appears in the $B^$-tree discussion of this section.
  • The average number of locks held during an insertion is very small: by (7) of the section, the average number of splits per insertion is less than $1/(\lceil m/2\rceil-1)$, so the lock coupling rarely needs to retain ancestor locks beyond a few levels.