The Grand Archive of the capital was a nine-story, octagonal pagoda perched against the hillside, housing centuries of empire-wide tax rolls, household registers, and judicial edicts.

Every dawn, clerks from the ministries, retinues of inspecting censors, and scholars preparing for imperial examinations poured through the lower gates. Navigating through tens of thousands of scrolls was made possible only by the tower’s meticulous geometry: the top floor displayed the imperial master index, directing visitors to the right wing; descending floors featured carved cedar screens showing which archive hall held which historical eras; and the ground floors were packed with floor-to-ceiling rosewood cubbies holding the scrolls themselves.

Experienced couriers could descend from the pinnacle along the stairs and emerge clutching the requested docket in less than two incense sticks of time.

Yet prosperity brought chaos. As imperial records multiplied, ground-floor chambers overflowed with increasing frequency. By ancient statute, whenever a chamber exceeded capacity, the archival bailiff was required to seal its doors, partition half the scrolls into an adjacent newly constructed hall, and dispatch runners to sprint up the stairs to padlock the staircase landing above. No one was permitted to descend into that quadrant until the directional signs on the landing above had been planed, repainted, and reinscribed with the new room numbers.

This procedure was known as “staircase latching.”

During spring tax audits or autumn reviews, visitors flooded the archive like a tidal surge. An east room split locked an east staircase; a west room split locked a west staircase. Occasionally, as signs on the third landing were being rewritten, the stairs leading to the fourth landing had to be locked in sympathy to prevent inconsistent descents. Across the Grand Archive, runners stood stranded on stair landings, lantern flames flickering as tempers flared. Angry shouts echoed down the stairwells while the courtyard outside grew hopelessly congested—all because of iron padlocks on wooden steps.

That year, Master Yao, the venerable keeper of archives, and Academician Lehman stood on the top balcony, gazing down at the paralyzed stairs, and decided to banish every padlock from the building.

“Stairs are made for walking,” Master Yao remarked. “Why cage them?” He dipped his brush and issued two concise decrees.

First: every archive room must hang a polished bronze plaque above its lintel, inscribed with the maximum catalog number permitted within that room. This was called the “Ceiling Plaque.”

Second: through the right stone wall of every room, masons must cut a three-foot arched passageway leading directly into the adjacent room on its right. The “Right Door.”

The scribes and junior archivists were terrified: “If a runner descends the stairs while a room below is being divided, won’t they barge into empty shelves and fall into confusion?”

Days later, the autumn grain reckoning arrived, bringing the ultimate test.

At mid-morning, Room Seven filled to bursting. The bailiff stepped in to perform a partition. He did not touch the stairs above, nor did he alert the floor above. He simply unlatched the freshly prepped Room Seven-B on the right, moved all scrolls numbered 401 through 800 into the new room, transferred the old plaque reading “Ceiling 800” to Seven-B’s lintel, hung a new plaque reading “Ceiling 400” over Room Seven, and drew the bolt on the connecting right door.

Having finished this, the bailiff poured himself a bowl of tea, planning to amble upstairs later when the corridors quieted to update the landing directory.

At that exact instant, an imperial bailiff rushed down the stairs, following the landing sign that still directed scroll #452 to Room Seven.

He dashed through Room Seven’s doorway, glanced up, and froze: the bronze plaque above the door now read “Ceiling 400.” The document he sought was clearly no longer in this room.

Under the old rules, he would have had to retreat in frustration to the landing and wait for painters to unlock the gate. But catching sight of the newly carved archway in the right wall, he stepped straight through the side door into Room Seven-B. Looking up, he saw the plaque reading “Ceiling 800.” Within seconds, his fingers brushed against scroll #452. He pulled it from the shelf and departed at a run.

Throughout the entire episode, the stairs on the floor above remained open to the morning breeze. No runner had paused. Not a single person upstairs even realized that Room Seven had just divided in two.

An hour later, the bailiff finished his tea, climbed the stairs, and repainted the directional board at his leisure. Even if an earthquake had struck and the bailiff had fled the building before updating the landing sign, not a single scroll would have been lost or hidden—readers venturing into Room Seven would simply step through the right doorway and find their prize.

From that day forward, iron padlocks were never again clamped upon the stairs of the Grand Archive. No matter how many thousands of scrolls poured into the repository, searchers raced downward unimpeded, stepping through the right doors whenever they crossed a boundary. The river of records flowed without pause, upon staircases that remained forever quiet, unlocked, and free.

— By now you’ve probably recognized it: this is the celebrated Lehman-Yao B-link Tree concurrency algorithm for database index management.

What it is

In database B+ Tree indexing, insertions eventually cause storage nodes to overflow, necessitating a node split. In classical B+ tree concurrency control, avoiding inconsistent reads during structural modification operations (SMOs) required lock crabbing (or lock coupling): a traversing query held an exclusive or shared lock on the parent node until it successfully acquired a lock on the child node. During node splits, writers had to propagate exclusive locks upward toward the root, locking entire ancestor paths. This created catastrophic bottlenecks at root and top-level pages, causing extreme lock contention and deadlock risks under heavy concurrent workloads.

Philip Lehman and S. Bing Yao revolutionized B-tree concurrency in 1981 with the B-link Tree. They augmented every node in the tree (both internal routing nodes and leaf pages) with two minimal structural elements:

1. High Key: The upper bound of the key range stored in that node’s subtree.
2. Right Link Pointer: A horizontal pointer connecting the node to its immediate right sibling at the same level.

When a node overflows and splits, Lehman-Yao decouples the structural modification into two atomic, independent phases:

• Phase One (Half-Split & Right Link): A new right sibling page is allocated. The upper half of the keys and the original High Key are moved into the new page. The original node points its right link pointer to the new sibling, and lowers its High Key to the split boundary. Crucially, the parent node is not touched or locked yet. The split is complete and safe at the current tree level.
• Phase Two (Parent Insertion): Inserting the new sibling’s downlink into the parent node is performed as a separate, asynchronous bottom-up step.

Most brilliantly, readers descend through the tree without acquiring any locks on internal nodes. If a reader descends into a node using an outdated routing entry and finds that the search key exceeds the node’s High Key, it recognizes that a concurrent split occurred. Instead of aborting, backtracking, or waiting for parent locks, the reader simply follows the right link pointer horizontally to the sibling page, locating the desired key transparently!

Why it matters

The Lehman-Yao B-link Tree is the bedrock of concurrency in modern relational database storage engines. Its most famous real-world implementation is PostgreSQL’s core B-tree indexing engine (src/backend/access/nbtree/), which implements Lehman-Yao B-link trees augmented with write-ahead logging (WAL) and page log sequence numbers (LSNs) for crash recovery.

Its core architectural advantages are profound:

1. Lock-Free Index Traversal: Readers traverse internal index nodes without acquiring shared locks (latch-free descent), completely removing read-write contention on root and higher-level internal pages.
2. Deadlock Immunity: Traversal strictly follows two directions: top-to-bottom descending, or left-to-right horizontal walking. It never backtracks upward or walks leftward, topologically precluding circular wait conditions and guaranteeing deadlock freedom.
3. Resilience to System Crashes: If the database crashes after Phase One (node split completed) but before Phase Two (parent downlink inserted), the index on disk remains structurally sound and fully searchable. The right link pointer ensures that subsequent queries can always discover the split data without corrupting query correctness.

From PostgreSQL to WiredTiger (the default storage engine in MongoDB) to CockroachDB’s underlying indexing structures, whenever an enterprise database handles hundreds of thousands of concurrent index lookups and inserts with sub-millisecond latencies, it is the quiet elegance of Lehman and Yao’s “Right Door” and “Ceiling Plaque” keeping the path open.

Metaphor mapping

• Nine-story Grand Archive on the hillside → Multi-level B+ Tree index hierarchy (root, internal nodes, leaves)
• Top master index and landing directional screens → Routing keys and downlink pointers in internal node index pages
• Rosewood cubbies packed with scrolls on lower floors → Data records and index tuples in leaf pages
• Clerks and couriers descending the stairs → Concurrent query reader threads (readers) traversing the index tree
• “Staircase latching” and iron padlocks → Traditional lock crabbing / lock coupling and exclusive structural modification locks
• Bronze “Ceiling Plaque” above each doorway → Node High Key (the strict upper bound of keys in that subtree)
• Three-foot arched “Right Door” in the side wall → Horizontal Right Link Pointer connecting sibling nodes at the same level
• Splitting room and unlatching right door before updating upstairs signs → Two-phase split (completing local sibling link before updating parent)
• Courier seeing High Key exceeded and walking through right door → Concurrent reader detecting Key > High Key and executing a right-walk
• Master bailiff delaying upstairs sign updates without losing scrolls → Crash consistency (decoupling parent update from node accessibility)