B-Tree and B-Plus-Tree Storage Engines

This note is about the storage-engine layer, not the abstract data structure. For the mathematics of the B-tree family — the minimum-degree parameter, the height bound h ≤ log_t((n+1)/2), and the insert/split/delete pseudocode — see [[B+ Tree]] (and [[B-Tree]] for the data-at-every-level ancestor). Here we take that structure as given and ask the engine question: how does a real relational database turn a B+tree into an on-disk, crash-safe, concurrent index? The answer is a stack of engineering decisions that the textbook glosses over — mapping each node onto exactly one fixed-size disk page, tuning how full those pages are packed, making a page split atomic across a power failure by write-ahead logging it, letting thousands of readers descend the tree while writers split pages underneath them via the Lehman-Yao B-link trick, and shrinking the routing layer with suffix truncation so the tree stays three or four levels tall for billions of rows. Every mainstream in-place relational engine is built on this: PostgreSQL’s default btree access method is “a correct implementation of Lehman and Yao’s high-concurrency B-tree management algorithm” (per the nbtree README); MySQL’s InnoDB stores “index records … in leaf pages of the B-tree” (MySQL 8.4 InnoDB physical structure); and SQLite’s “table b-trees … store all data in the leaves” (SQLite file format). This is the read-optimized, update-in-place engine — contrast the write-optimized [[Log-Structured Merge Trees and Sorted String Tables]] engine, which is a different note entirely.

Mental Model — Page Is Node, Fanout Is Everything

The single most important identity in a B+tree storage engine is: one tree node = one fixed-size disk page. A page is the atomic unit of I/O and of buffering — typically 8 KiB in PostgreSQL and 16 KiB in InnoDB. When the engine reads a node, it reads exactly one page from disk (or, far more often, finds it already resident in the [[The Buffer Pool|buffer pool]]). The internal byte layout of that page — the slot directory, the record heap growing toward it — is the subject of [[Database Pages and the Slotted Page Layout]]; what matters here is what the page contains as a tree node. An internal (branch) page holds separator keys and child page numbers (downlinks) and nothing else. A leaf page holds the actual (key, value) pairs for a clustered index, or (key, row-pointer) pairs for a secondary index — the clustered-versus-secondary distinction is [[Clustered versus Secondary Indexes]] and whether the leaf is the table row is [[Heap Files and Index-Organized Tables]].

Because data lives only in leaves, internal pages carry no payload, so they pack in far more downlinks — this is precisely why databases default to the B+tree rather than the plain B-tree (the derivation is in [[B+ Tree]]). More downlinks per page means higher fanout (the number of children a node has), and fanout is the base of the logarithm that sets tree height. The payoff is dramatic and worth making concrete. Jeremy Cole’s reverse-engineering of the InnoDB on-disk format measured that, on a 16 KiB page with a simple integer primary key, a leaf page holds up to 468 records and a non-leaf page up to 1,203 records (blog.jcole.us, 2013). Feed those numbers through the height arithmetic and the result is startling: a three-level tree stores more than 677 million rows, and a four-level tree more than 814 billion (Cole, 2013). That is the whole game — for any realistic table the tree is three or four levels deep, the top one or two levels are permanently cached, and a point lookup is one, maybe two, physical reads.

The leaves are also doubly linked: each page stores a pointer to its left and right sibling. Cole confirms this directly — “each page contains pointers (in the FIL header) for ‘previous page’ and ‘next page’, which for INDEX pages are used to form a doubly-linked list of pages at the same level.” That sibling chain is what makes ordered range scans and ORDER BY ... LIMIT cheap, and — as the next section shows — it is also the load-bearing structure behind lock-free concurrent search.

flowchart TB
    R["Root (internal page 3)<br/>keys: [ 40 | 80 ]<br/>high key: +inf"]
    A["Leaf page 12<br/>records: 10, 25<br/>high key: 40"]
    Ap["Leaf page 47 (just split off)<br/>records: 30, 38<br/>high key: 40"]
    B["Leaf page 13<br/>records: 40, 55<br/>high key: 80"]
    C["Leaf page 14<br/>records: 80, 95<br/>high key: +inf"]
    R -->|"downlink &lt; 40"| A
    R -->|"downlink 40..79"| B
    R -->|"downlink &ge; 80"| C
    A -. "right-link" .-> Ap
    Ap -. "right-link" .-> B
    B -. "right-link" .-> C

A B-link tree mid-split. What it shows: page 12 has just split, moving its upper half onto the new page 47, but the parent root has not yet learned about page 47 — its downlink still points only to 12, 13, 14. Every page carries a high key (an upper bound on the keys it may hold) and a right-link to its right sibling. The insight to take: a reader that descended the old downlink to page 12 while searching for key 35 compares 35 against page 12’s high key (40); since 35 < 40 the record is here — but a reader searching for 38 finds 38 is on page 12’s key range yet the record moved to 47, so it detects the concurrent split by walking the right-link. The high-key/right-link pair lets the tree be searched with no read locks on the parent, which is the entire Lehman-Yao contribution.

Mechanical Walk-through — A Page Split, Made Crash-Safe

A search descends from a fixed root page (InnoDB stores the root’s location permanently in the data dictionary; PostgreSQL keeps a metapage). At each internal page the engine binary-searches the separator keys, picks the child page number, releases the current page, and reads the child — until it reaches a leaf. Nothing exotic; the interesting mechanics start on insert, when a leaf overflows.

The physical split. When a new record will not fit on its target leaf, the engine must split. Concretely it (1) allocates a fresh page from the index’s free-space map or by extending the file, (2) redistributes roughly half the records onto the new page, keeping the lower half on the original page, (3) fixes the sibling chain — the new page’s next becomes the old page’s old next, the old page’s next becomes the new page, and the old right neighbour’s prev is repointed — and (4) inserts a separator key and a downlink for the new page into the parent. If the parent is itself full, the split cascades upward; a split at the root creates a brand-new root and the tree grows one level taller. This is the standard B+tree split (pseudocode in [[B+ Tree]]); the storage engine’s contribution is making step (4) survive a crash that lands between the leaf-level change and the parent-level change.

Why that is hard. A split touches at least two pages at the leaf level (old + new) plus one page at the parent level, and these are separate disk blocks that cannot be written atomically. If the machine loses power after the new leaf is on disk but before the parent’s downlink is, recovery would find an orphaned page that no parent points to — a corrupt index.

PostgreSQL’s answer: the incomplete-split flag. Per the nbtree README, “when a page is split, the left page is flagged to indicate that the split is not yet complete (INCOMPLETE_SPLIT). When the downlink is inserted to the parent, the flag is cleared atomically with the insertion.” The two levels are logged as two write-ahead-log records: “an insertion that causes a page split is logged as a single WAL entry for the changes occurring on the insertion’s level — including update of the right sibling’s left-link — followed by a second WAL entry for the insertion on the parent level.” If a crash happens between them, recovery replays the first record (the leaf split, including the right-link) but not the second, leaving a flagged page whose downlink is missing. PostgreSQL then repairs this lazily: “our approach is to create any missing downlinks on-the-fly, when searching the tree for a new insertion.” Because the right-link already exists, searches remain correct in the meantime — they just walk right to find the orphan. This is the Write-Ahead Log discipline specialized to structural changes: log before you write data, and order the log records so any prefix leaves a searchable tree.

InnoDB’s answer: redo log plus doublewrite. InnoDB records B-tree page operations in its redo log, a “disk-based data structure used during crash recovery to correct data written by incomplete transactions … replayed automatically during initialization” (MySQL 8.4 redo log). Redo protects against lost changes, but a 16 KiB page write is not atomic at the hardware level — a crash can leave a torn page, half old and half new, which redo cannot fix because redo assumes it is patching a known-good page. InnoDB closes that hole with the doublewrite buffer: “the doublewrite buffer is a storage area where InnoDB writes pages flushed from the buffer pool before writing the pages to their proper positions … If there is an operating system, storage subsystem, or unexpected mysqld process exit in the middle of a page write, InnoDB can find a good copy of the page from the doublewrite buffer during crash recovery” (MySQL 8.4 doublewrite buffer). It is cheap because the pages go out “in a large sequential chunk, with a single fsync().” So InnoDB’s crash-safe split = doublewrite (torn-page protection) + redo (replay the logical page operations). Both engines lean on the LSN to decide which changes a recovered page already reflects.

Deletes and merges — deliberately lazy. The mirror image of a split is a merge, and here the two engines diverge sharply, because eager merging is expensive and rarely worth it. InnoDB governs merging with MERGE_THRESHOLD: “if the ‘page-full’ percentage for an index page falls below the MERGE_THRESHOLD value when a row is deleted or when a row is shortened by an UPDATE operation, InnoDB attempts to merge the index page with a neighboring index page” — and “the default MERGE_THRESHOLD value is 50, which is the previously hardcoded value” (MySQL 8.4 merge threshold). PostgreSQL refuses to merge partly-full pages at all: “we consider deleting an entire page from the btree only when it’s become completely empty of items. (Merging partly-full pages would allow better space reuse, but it seems impractical to move existing data items left or right to make this happen)” (nbtree README). Empty-page reclamation is deferred to VACUUM, done in two stages — the page is unlinked from its parent and “marked as half-dead, which causes any subsequent searches to ignore it and move right” — and, tellingly, the engine “never delete[s] the rightmost page on a tree level” because that would complicate the traversal invariants.

Fill Factor and Page Utilization — the Tuning Knobs

How full the engine packs a page directly trades space for future split cost. Both major engines expose this as a knob and both reserve slack on purpose.

PostgreSQL fillfactor. “B-trees use a default fillfactor of 90, but any integer value from 10 to 100 can be selected” (CREATE INDEX docs). It “controls how full the index method will try to pack index pages. For B-trees, leaf pages are filled to this percentage during initial index builds, and also when extending the index at the right (adding new largest key values).” The 10% slack exists to absorb a few in-place updates without an immediate split; the docs warn that “a fillfactor setting of 100 … risks harming performance: even a few updates or inserts will cause a sudden flood of page splits,” and that lowering fillfactor to the 50–90 range can “smooth out the rate of page splits during the early life of the B-tree index.”

InnoDB innodb_fill_factor and the 1/16 reserve. InnoDB’s innodb_fill_factor “defines the percentage of space on each B-tree page that is filled during a sorted index build, with the remaining space reserved for future index growth.” Crucially, InnoDB always keeps a floor of slack: “an innodb_fill_factor setting of 100 leaves 1/16 of the space in clustered index pages free” (MySQL 8.4 physical structure). The steady-state fill then depends entirely on insert order, which is the most consequential runtime fact in this whole note: “if index records are inserted in a sequential order (ascending or descending), the resulting index pages are about 15/16 full. If records are inserted in a random order, the pages are from 1/2 to 15/16 full.” Random inserts therefore leave InnoDB indexes far more bloated than sequential ones — the well-known steady-state average for random insert-and-split workloads is roughly 69% (the ln 2 result from Yao’s analysis; the derivation belongs to [[B-Tree]], not here). The engine-level takeaway is the opposite of naïve intuition: a sequential (auto-increment) primary key produces the densest, smallest clustered index, while a random key (a UUID v4) produces a 50–69%-full, fragmented one — but sequential keys extract a concurrency cost, discussed next.

Concurrency — Lehman-Yao, Crabbing, and Latches Versus Locks

A single-threaded B+tree is easy; a concurrent one is a research problem, because a reader can arrive at a page in the exact instant a writer is splitting it. Two mechanisms tame this, and they operate on two different kinds of exclusion that beginners routinely conflate.

Latches versus locks. A latch is a short-duration, physical mutual-exclusion primitive that protects the bytes of a page in memory while a single operation reads or edits them; it is held for microseconds and is invisible to the transaction. A lock is a logical, transaction-duration primitive that protects a row or key range to enforce isolation, held until commit and managed by the deadlock detector ([[Two-Phase Locking]], [[Multiversion Concurrency Control]]). The B-tree code is all about latches ([[Page Pinning and Latching]]); the transaction layer above it deals in locks. Confusing the two is the single most common source of muddled thinking about index concurrency.

Latch coupling / “crabbing.” The classic way to descend safely is latch coupling (nicknamed crabbing, after the way a crab moves one claw before releasing the other): acquire a latch on the child before releasing the latch on the parent, so no writer can restructure the subtree you are about to enter. A read descent takes shared latches; a write descent that might split takes exclusive latches on the path. Because taking exclusive latches all the way down would serialize every writer at the root, real engines descend optimistically — shared latches, betting the leaf will not split — and only if the leaf turns out to be full do they pessimistically restart the descent taking exclusive latches (the classic treatment is Petrov, Database Internals, ch. on B-tree concurrency). PostgreSQL adds a subtlety the README spells out: “in most cases we release our lock and pin on a page before attempting to acquire pin and lock on the page we are moving to … This is safe when moving right or up, but not when moving left or down (else we’d create the possibility of deadlocks).” Ordering latch acquisition consistently (down/left never grabs ahead of releasing) is what prevents latch-level deadlocks.

The Lehman-Yao B-link tree. Latch coupling still forces readers to touch the parent. Lehman and Yao’s 1981 algorithm (“Efficient Locking for Concurrent Operations on B-Trees,” ACM TODS 6(4):650–670) removes even that, and PostgreSQL implements it directly. It adds two things to every page: “a right-link pointer to each page, to the page’s right sibling” and “a ‘high key’ to each page, which is an upper bound on the keys that are allowed on that page.” The rule for a descending search is: “when a search follows a downlink to a child page, it compares the page’s high key with the search key. If the search key is greater than the high key, the page must’ve been split concurrently, and you must follow the right-link to find the new page containing the key range you’re looking for” (nbtree README). Because a split always creates the new right sibling and its right-link before it touches the parent, a reader that raced the split is never lost — worst case it takes one extra hop rightward. This is why PostgreSQL can search “without holding any read locks (except to keep a single page from being modified while reading it).” (PostgreSQL departs from the pure paper in one respect: L&Y “assume that in-memory copies of tree pages are unshared. Postgres shares in-memory buffers among backends. As a result, we do page-level read locking on btree pages.”) Deletion, which L&Y did not fully cover, follows Lanin & Shasha’s symmetric algorithm — hence the half-dead-page dance above.

The rightmost-page fastpath, and its dark side. Monotonically increasing keys (auto-increment primary keys, timestamps) always insert at the rightmost leaf, so both engines special-case it. PostgreSQL caches it: “we optimize for a common case of insertion of increasing index key values by caching the last page to which this backend inserted … if this page was the rightmost leaf page … [this] can avoid the cost of walking down the tree.” InnoDB’s sequential-insert path is what yields the 15/16-full pages quoted above. The optimization makes append-heavy inserts fast, but it concentrates all insert traffic on one hot page and its ancestors — the failure mode covered next.

Concrete Example — Suffix Truncation Shrinks the Downlink

Consider a PostgreSQL index on (last_name, first_name, employee_id). A leaf page fills and splits; the last tuple on the new left page is ('Miller', 'Zoe', 8123) and the first tuple on the new right page is ('Nguyen', 'Al', 12). The split must place a separator in the parent that routes searches left or right. A naïve engine copies the whole first-right key ('Nguyen', 'Al', 12) up as the downlink — 3 attributes, wide, especially if the names are long text. Suffix truncation (introduced in PostgreSQL 12; the technique dates to Bayer & Unterauer’s 1977 “Prefix B-Trees”) observes that only last_name is needed to distinguish the two pages: 'Miller' < 'Nguyen' already, so first_name and employee_id are redundant for routing. The engine truncates the separator to just ('Nguyen') — per the README, “we truncate away suffix key attributes that are not needed for a page high key … Since the high key is subsequently reused as the downlink in the parent page for the new right page, suffix truncation makes pivot tuples short.” Shorter separators mean more downlinks per internal page, higher fanout, a shallower tree — PostgreSQL 12’s release engineering measured meaningfully smaller multi-column indexes and better internal-page locality (CYBERTEC, PG 12 B-tree improvements). (The routing keys in internal pages are called pivot tuples; unlike leaf tuples they never point to a heap row.)

A complementary space optimization is deduplication, added in PostgreSQL 13. Where many leaf tuples share the same key value, the engine merges them into one posting-list tuple: “the column key value(s) only appear once … followed by a sorted array of TIDs [Tuple Identifiers] that point to rows in the table” (PostgreSQL btree docs). It runs “lazily, when a new item is inserted that cannot fit on an existing leaf page … [to] prevent (or at least delay) leaf page splits” (CYBERTEC, PG 13 deduplication), is ON by default via the deduplicate_items parameter, and can even help unique indexes “absorb extra version-churn duplicates.” A related family of tricks is prefix compression of keys in a page — storing each key as a delta from a shared prefix rather than in full — used by other engines (for example MyISAM’s PACK_KEYS and Oracle’s index key compression). All of these share one goal: cram more useful keys into each page so the tree stays short.

Uncertain

Verify: whether InnoDB performs B-tree key prefix compression on secondary-index pages. Reason: InnoDB’s documented compression is page-level (the COMPRESSED row format, zlib) rather than per-key prefix elision, and I did not find a primary MySQL doc describing key-prefix compression inside a B-tree page during this research. To resolve: check the MySQL 8.4 InnoDB row-format / index docs for any per-key prefix-compression statement, and the MyISAM PACK_KEYS docs. The only prefix/suffix fact fully verified against a primary source in this note is PostgreSQL’s suffix truncation (PG 12, per the nbtree README). uncertain

Failure Modes

Rightmost-page contention on monotonic keys. The very optimization that makes auto-increment inserts fast makes the rightmost leaf (and its ancestors) a write hot spot — every concurrent inserter wants an exclusive latch on the same page, serializing them and, on multi-socket hardware, causing latch cache-line bouncing. This is the classic argument against a globally-monotonic primary key in a high-write system; mitigations include hash/reverse-key indexing (at the cost of range-scan locality) or sharding the sequence. It is the counterweight to the “sequential keys give dense pages” benefit.
Index bloat. Random-key inserts leave pages 50–69% full; churn from updates/deletes under [[Multiversion Concurrency Control|MVCC]] leaves dead tuples that only VACUUM (PostgreSQL) or purge/merge (InnoDB) reclaims. Because PostgreSQL never merges partly-full pages, a table that grows then shrinks can leave a permanently half-empty, over-tall index until it is REINDEXed. Monitoring index size versus live tuples is the standard health check.
Page-split write amplification. A single logical insert that triggers a split rewrites two leaf pages plus a parent page, each of which must go through WAL/redo (and, in InnoDB, the doublewrite buffer — so the physical bytes are written twice). A cascading split up to a full root multiplies this. This is why B+tree engines are read-optimized but write-amplifying, and precisely the axis on which [[Log-Structured Merge Trees and Sorted String Tables|LSM engines]] compete — quantified in [[Compaction and the Amplification Trade-offs]].
Latch-ordering deadlocks. If the code ever acquires latches in an inconsistent order (e.g. moving left/down while still holding a latch it should have released), two operations can deadlock at the latch level — invisible to the transaction deadlock detector, so it manifests as a hang, not a rollback. The strict “release before descending; only couple when moving right or up” rule in the nbtree README exists precisely to make latch acquisition order total and deadlock-free.

Alternatives and When to Choose Them

The B+tree engine is the default for a reason: it gives O(log n) point lookups, ordered range scans over the linked leaves, and in-place updates with excellent read locality — the shape of most OLTP (Online Transaction Processing) workloads. Its weakness is write amplification: every update rewrites a whole page and logs it, and heavy random writes fragment the tree. The principal alternative is the Log-Structured Merge tree ([[Log-Structured Merge Trees and Sorted String Tables]]), which buffers writes in memory and flushes immutable sorted runs sequentially, trading read and space amplification for far cheaper writes — the right pick for write-heavy ingest (metrics, event logs, RocksDB/Cassandra-style stores). The decision reduces to your read/write mix and is analyzed as a three-way trade in [[Compaction and the Amplification Trade-offs]] and framed by workload in [[Online Transaction Processing versus Online Analytical Processing]]; do not re-derive LSM mechanics here. Within the B-tree family, latch-free variants (the Bw-tree behind SQL Server Hekaton) and buffered variants (fractal/Bε-trees behind TokuDB) sit at different points on the same curve — noted for completeness in [[B+ Tree]].

Version and as-of context

Verified against primary docs consulted 2026-07-02: PostgreSQL suffix truncation shipped in 12, deduplication in 13, bottom-up index deletion in 14 (nbtree README + release-note corroboration). PostgreSQL’s docs/current/ now serves version 18, so “current” means 18; the mechanisms above are stable across 12→18. InnoDB facts are pinned to MySQL 8.4 LTS (MERGE_THRESHOLD default 50, innodb_fill_factor reserving 1/16, doublewrite buffer). Jeremy Cole’s record-per-page numbers (468 leaf / 1,203 non-leaf) are from a 2013 measurement of a specific integer-PK schema and are illustrative of magnitude, not a universal constant.

vault

Explorer

B-Tree and B-Plus-Tree Storage Engines

B-Tree and B-Plus-Tree Storage Engines

Mental Model — Page Is Node, Fanout Is Everything

Mechanical Walk-through — A Page Split, Made Crash-Safe

Fill Factor and Page Utilization — the Tuning Knobs

Concurrency — Lehman-Yao, Crabbing, and Latches Versus Locks

Concrete Example — Suffix Truncation Shrinks the Downlink

Failure Modes

Alternatives and When to Choose Them

See Also

Graph View

Table of Contents

Backlinks