Concurrent Descent and Page Latching in a Shared B-Tree

A B-tree’s correctness under concurrency is harder than a single-threaded B-tree’s because a structural change modifies two pages that must both remain consistent from every reader’s point of view, and because a reader that has already passed a parent page cannot be told that the child it is about to read has moved. The protocols that solve this are among the more delicate pieces of database engineering, and the standard solution is not a lock on the tree but a set of rules about the order in which latches are taken and released during a descent.

Latches are not locks

The first distinction is between a latch and a lock. A lock protects logical data and is held until transaction end, participates in deadlock detection, and is visible in the lock table. A latch protects a physical page for the duration of one operation, is released before the operation completes, and uses no deadlock detection because the code is written so that deadlock cannot occur. A page latch is typically a read-write mutex with a small spin phase and a queue for waiters; a lock is a heavyweight structure with a wait graph.

Everything below concerns latches. The question is how a descent through $h$ levels takes latches so that no reader sees a torn page, no writer corrupts a page, and no two operations wait on each other in a cycle.

The naive protocol and why it fails

The simplest protocol takes a read latch on a page, finds the child, takes a read latch on the child, then releases the parent, and repeats. It works for a descent with no modifications, and it is adequate while no split occurs. The failure is a split of the page the reader is descending into: the split moves half the entries to a new page, and the reader, which selected the child from a parent whose separator was written before the split, may be looking at a page that no longer contains the key it seeks.

The naive fix is to hold latches on the whole path from root to leaf, an exclusive latch on any page that will be modified and a read latch on the rest, and to release them all when the operation finishes. This is correct and it serializes the tree: every writer holds the root, so every writer blocks every other writer, and every reader blocks behind them. It is the protocol that a first implementation uses and that no production engine keeps.

What a reader needs is a bound, not a path

The key insight of the Lehman-Yao protocol is that a reader descending the tree only needs the guarantee that the page it is reading still contains the key it wants, or that it can be redirected to a page that does. If a split moves entries to a new page, a reader that arrives at the old page mid-split can be redirected if the old page records where the new page is.

Their design adds a link from the old page to the new page, written as part of the split, and the rule that a reader which finds a key above the old page’s current high key follows the link. The reader therefore never needs the parent to be stable; it needs the page it is on to be self-describing enough to redirect it. Splits are performed bottom-up, with the child split and linked before the parent is updated, so there is no window in which the parent points at a page that does not exist, only a window in which the parent points at a page whose high key has shrunk.

This is the same idea as a high-key field in a page header, and most modern formats carry one. A page records its own upper bound; a search that finds the key above the bound follows the right link or the split link rather than trusting the parent’s separator. The parent’s separator becomes a hint that may be stale, and the page’s own bound is the authority.

The latch coupling rule

With redirection in place, the descent can release each parent before acquiring its child. The protocol is: latch the child, then release the parent, which is called latch coupling and is what prevents the deadlock that would arise if a writer held a parent while waiting for a child that another writer held while waiting for the same parent.

The ordering matters and it is the opposite of the naive intuition. Releasing the parent before latching the child would leave a gap in which the tree could change; latching the child first and then releasing the parent means that at every instant the operation holds a latch on at least one page on the path, so the path is never entirely free for a concurrent split to rearrange. A split needs an exclusive latch on the child and then on the parent; a descent needs a read latch on the child before releasing the parent. The two orderings are compatible because the split’s parent acquisition happens after it holds the child, and the descent’s parent release happens after it holds the child.

For an insert that must split, the writer has to hold the child exclusively and then acquire the parent, which is upward in the tree. That is the direction that conflicts with a descending reader holding the parent and wanting the child. Lehman-Yao resolves it by having the split write the link first and update the parent later, possibly after releasing the child, so the parent update is not required for correctness of the descent. The cost is that the tree is briefly in a state where the parent’s separator is stale, and any code that assumes otherwise is wrong.

Optimistic descent and restarts

The pessimistic protocol latches every page it visits, even when nothing is being modified, which on a read-heavy workload spends most of its time acquiring latches that nobody contends for. Optimistic descent takes no latch to read a page: it reads the page’s version number, copies the bytes it needs, reads the version number again, and retries if the two differ or if the page was found inconsistent. If the descent reaches a leaf whose version is stable, the operation succeeds with no latch at all; only a modification takes latches.

The version number must be odd while a modification is in progress and even when the page is stable, so a reader that sees an odd version knows a writer is mid-operation and retries. The reader also has to be prepared for the page’s contents to have changed under it in a way that is not detectable by the version alone, which is why the protocol also validates that the child pointer it followed is still within the page’s current bounds.

A restart is cheap, and the expected number of restarts is low when modifications are rare relative to reads. The failure case is a workload with heavy splits on the pages being read, where restarts become frequent and the optimistic protocol degenerates into repeated work. That case is exactly the right-edge insert pattern of a monotonic key, which is why engines special-case the rightmost path.

The lock-free and Bw-tree variants

A further step removes latches from the page entirely and makes each page update an atomic pointer swap of a new version of the page. The Bw-tree does this: a mapping table from logical page identifier to physical location is updated atomically, and a modification installs a delta record rather than rewriting the page. Readers follow the mapping table and apply the deltas they find, and consolidation of deltas into a clean page happens in the background.

The gain is that a reader never blocks a writer and a writer never blocks a reader, so the tree has no latch contention at all and scales across cores without the cache-line bouncing that a page latch causes. The cost is that a read may have to apply a chain of deltas, that the mapping table is itself a structure needing careful memory management, and that reclamation of old page versions requires either epoch-based reclamation or hazard pointers, because a reader may still be holding a pointer to a version that has been superseded.

The engineering trade is stark. A latched B-tree is simple to reason about, has bounded read cost, and concentrates contention on hot pages. A delta-updated B-tree has no contention and unbounded read cost in the worst case, because a page that has accumulated many deltas costs many applications per read. Consolidation bounds that cost in practice, and the bound is a tuning parameter rather than a structural guarantee.

What the protocol must preserve for the rest of the engine

The latching protocol is not self-contained. A page that is being split must not be freed until no reader can still be traversing it, which requires the same reclamation discipline as any concurrent data structure: hazard pointers, epochs, or a rule that pages are freed only after a quiescent point. An engine that frees a split page immediately after the parent is updated will hand a freed page to a reader that selected it a moment earlier, and the resulting failure is a use-after-free that appears under load and not in tests.

The protocol also interacts with the buffer pool, which may evict a page while an operation holds a latch on it. The usual rule is that latching a page pins it, so eviction cannot select it, and the buffer pool’s replacement policy must respect the pin count. A page that is pinned for the duration of a descent through the whole tree is a page that cannot be evicted, which is one reason long descents are avoided by caching the upper levels, as the height arithmetic suggests they can be.

Finally, the protocol must be correct for the index’s own consistency, not just for individual pages. A concurrent range scan that follows the leaf chain must not miss a page inserted into the chain during the scan, and the standard fix is the same as the split fix: the page that a scan has reached records a link to its successor, and the scan follows links rather than trusting a snapshot of the chain. A page split during a scan therefore extends the chain in a way the scan sees, and the only requirement is that the link be written before the new page is reachable from the parent, which is the bottom-up ordering again.