Engineering Atlas › System Design Fundamentals

B-trees and B+ trees on disk

12 min read · last reviewed 2026-10-17

Open in the interactive app: practice, quiz, mock interview →

In one minute

How it works

Pages, not nodes

Disks and SSDs read in blocks, and the database buffer pool caches fixed-size pages (8 KB in PostgreSQL, 16 KB in InnoDB). A B-tree maps one node to one page. With 16-byte keys plus 6-byte child pointers, an internal page holds around 500 entries, so the fan-out is about 500. Three levels index 500 × 500 × 500 = 125 million leaf entries, and the top two levels (about 250,000 pages, roughly 4 GB) usually sit in memory. A point lookup therefore costs about one physical read.

B-tree versus B+ tree

In a classic B-tree any node can hold a key with its value. In a B+ tree, internal nodes hold only separator keys, every key with its payload lives in a leaf, and leaves point to their right sibling. Three effects follow:

Almost every database "B-tree" is a B+ tree. InnoDB goes further: the table itself is a B+ tree clustered on the primary key, and secondary indexes store the primary key as their pointer.

Search, insert, split

Search binary-searches the keys inside each page and follows the child pointer until it reaches a leaf. Insert finds the target leaf and places the key in sorted position. If the page overflows, it splits: half the entries move to a new page, and the first key of the new page becomes a separator inserted into the parent. If the parent overflows, it splits too. When the root splits, a new root is created, which is the only way the tree gets taller.

Deletes remove the leaf entry. Textbook B-trees merge underfull pages, and engines differ here. InnoDB tries to merge a page once it drops below MERGE_THRESHOLD, 50% by default (MySQL docs). PostgreSQL never merges half-empty pages; VACUUM only removes pages that become completely empty, so space otherwise comes back through rebuilds.

Concurrency and crash safety

A split touches several pages, so it is WAL-logged and protected by short page latches taken while descending ("latch crabbing"). PostgreSQL uses the Lehman-Yao design from 1981: a reader that lands on a page that just split follows its right link instead of locking the parent (nbtree README).

Write and space behaviour

Changing one 100-byte row rewrites a whole 8 to 16 KB page eventually, which is write amplification of 80 to 160 times at the page level, before WAL and full-page images. Pages split at 50% full, so random inserts leave the tree around 67 to 70% full on average. Sequential keys (auto-increment ids, timestamps) fill pages much fuller because engines detect right-edge appends and split unevenly, but not to 100%: they deliberately leave room for later updates. PostgreSQL fills right-edge leaves to the index fillfactor, 90 by default (PostgreSQL CREATE INDEX), and InnoDB leaves 1/16 of each page free, so sequential inserts give pages about 15/16 full while random ones land anywhere from 1/2 to 15/16 (MySQL docs).

Down the stack

Layer 1The contract

A B+ tree index promises an ordered map: point lookups, ordered range scans in either direction, and uniqueness checks, each costing O(log_F N) page reads where F is the fan-out, so the cost grows by one page only when the data grows by a factor of several hundred. Concurrent readers never see a half-split page, and after a crash the tree is structurally valid because every split is WAL-logged as one atomic action. It does not promise space efficiency or physical order: after heavy churn, pages may be half empty and leaves scattered on disk.

Layer 2The mechanism

A PostgreSQL B-tree page (nbtree) is an ordinary 8 KB heap-style page. It starts with a 24-byte PageHeaderData, followed by an array of 4-byte line pointers that grows forward, while index tuples are packed from the end of the page backward. Line pointers are kept in key order, so binary search runs over them. At the end sits a special area (BTPageOpaqueData) with left and right sibling block numbers, the tree level, and flags. Every page except the rightmost on its level stores a high key, the upper bound of keys it may hold. High key plus right link is the Lehman-Yao trick: a reader that arrives after a concurrent split sees its key exceeds the high key and moves right. Since version 13, leaves deduplicate equal keys into posting-list tuples (PostgreSQL 13 release notes), and since version 14 bottom-up deletion removes dead versions from a leaf that is about to split because of non-HOT updates, delaying the split (PostgreSQL B-tree docs).

InnoDB uses 16 KB pages. Records form a singly linked list in key order between two sentinel records, infimum and supremum, and a sparse page directory at the end of the page holds a slot for every 4 to 8 records. Search binary-searches the directory, then walks a few links.

Layer 3The machine

A page read costs on the order of 100 microseconds on NVMe and several milliseconds on a spinning disk. Inside memory, the cost moves to the CPU cache. An 8 KB page is 128 cache lines of 64 bytes. Binary search over a few hundred keys needs about 8 or 9 probes, each touching a line pointer and then a tuple elsewhere in the page, so a search inside one page costs a handful of cache misses. That is one reason PostgreSQL truncates unneeded suffix columns from separator keys: shorter keys mean more per page and fewer lines touched.

Writes meet two size mismatches. First, devices typically guarantee atomic writes of 4 KiB at most, so a 16 KB InnoDB page can tear in a power cut; InnoDB writes pages to the doublewrite buffer first, and PostgreSQL logs a full-page image after each checkpoint. Second, flash cannot overwrite in place. NAND is programmed in pages of several KiB and erased in blocks of several megabytes, so the SSD's flash translation layer redirects each rewrite to a fresh location and later garbage-collects. Scattered in-place page updates therefore add device-level write amplification on top of the engine's own.

Why it's built this way

  1. Storage reads in blocks and random reads are expensive, so each node is a page and high fan-out keeps the tree 3 to 4 levels deep.
  2. Upper levels are small and hot, so they stay cached and a lookup costs about one physical read.
  3. Ranges must be cheap, so data lives only in linked leaves and a scan becomes a sibling walk.
  4. Pages are larger than the atomic write unit, so the engine needs WAL plus full-page images or doublewrite to survive torn writes.
  5. Splits must not block readers, so high keys and right links let readers recover without locking the parent.

Diagram

flowchart TD
    R["Root: 40 | 80"] --> I1["Internal: 10 | 25"]
    R --> I2["Internal: 55 | 70"]
    R --> I3["Internal: 90"]
    I1 --> L1["Leaf 1-9"]
    I1 --> L2["Leaf 10-24"]
    I1 --> L3["Leaf 25-39"]
    I2 --> L4["Leaf 40-54"]
    I2 --> L5["Leaf 55-69"]
    I2 --> L6["Leaf 70-79"]
    I3 --> L7["Leaf 80-89"]
    I3 --> L8["Leaf 90+"]
    L1 --> L2 --> L3 --> L4 --> L5 --> L6 --> L7 --> L8

Worked example

An events table has 2 billion rows. The primary key is a 16-byte UUID; a secondary index covers (user_id, created_at) at 16 bytes per key.

With 8 KB pages and about 24 bytes per internal entry, fan-out is roughly 300. Leaves hold about 200 entries at 70% fill. Two billion entries need 10 million leaf pages (80 GB), 33,000 level-two pages, 110 level-one pages, and one root. That is a four-level tree. The upper three levels total about 260 MB and stay cached, so a point lookup costs one leaf read: around 100 microseconds on NVMe if not cached.

With random UUIDv4 keys at 20,000 inserts per second, each insert lands on a random leaf. The working set is the whole 80 GB leaf level, so with a 32 GB buffer pool most inserts miss cache, read a page, and later write it back. Switching to time-ordered keys (UUIDv7 or a sequence) makes inserts hit the rightmost few leaves, which stay hot in memory. UUIDv7 is now standard: RFC 9562 (May 2024) replaced RFC 4122, puts a 48-bit Unix millisecond timestamp in the top bits, and says outright that random UUIDs have poor index locality (RFC 9562). PostgreSQL 18 generates them natively with uuidv7() (PostgreSQL docs). Write I/O for that index drops by an order of magnitude, and pages fill to around 90%, shrinking the index by roughly a quarter.

In the wild

Trade-offs

OptionStrengthsWeaknessesChoose when
B+ tree indexPredictable point and range reads, in-place updatesRandom write I/O, page-level write amplificationRead-heavy or mixed OLTP
Clustered B+ tree (InnoDB)Primary key range scans read contiguous rowsWide PK bloats every secondary index; random PK fragments tableAccess mostly by primary key
Heap plus B+ tree indexes (PostgreSQL)Cheap secondary indexes, stable row addressesIndex lookups need an extra heap fetchMany secondary access paths
LSM treeSequential writes, better compressionRead and space amplification, compaction debtWrite-heavy ingestion
Hash indexO(1) point lookupsNo range scans or orderingPure key-value equality lookups

Pitfalls in production

Leadership lens

Check yourself

  1. Why does a B+ tree usually have higher fan-out than a classic B-tree with the same page size?

    Show answer

    Internal nodes hold only keys and child pointers, not values, so more entries fit per page.

  2. Why do sequential inserts produce a smaller index than random inserts?

    Show answer

    Engines detect right-edge appends and leave full pages behind, while random inserts split pages at 50% and leave them partly filled.

  3. A point lookup on a 4-level tree costs about one disk read. Why not four?

    Show answer

    The upper levels are small and hot, so they stay in the buffer pool; only the leaf is usually read from disk.

  4. What problem do right-link pointers solve for concurrent readers?

    Show answer

    A reader that reaches a page just after it split can follow the right link to the new sibling instead of restarting or locking the parent.

Sources and further study

Primary

Systems docs

Books

Other curricula

Watch

Free resources

Open in the interactive app: practice, quiz, mock interview →