B-Trees: Trees Shaped for Disks

Storage never reads one key. It reads a page, 4 to 16 KiB at a time, and every page read costs a rung of the ladder far below RAM. A binary tree spends one page read per level and uses a single key from each page it reads. A B-tree fills each node with hundreds of keys, so one page read chooses among hundreds of children, and any key among millions is three or four reads away.

That trade, wide nodes and few levels, is why almost every relational database and many file systems keep their indexes in B-trees. It is the answer to "how does a database find one row among millions without reading them all", and it is where this book hands the database over to PostgreSQL Deep Dive.

Why Binary Trees Fail on Disk

A balanced binary tree over 2 million keys is about 21 levels deep. In memory, 21 levels cost 21 pointer hops, a couple of microseconds. Put each node on its own page on storage and every level becomes a random read: at up to 100 microseconds for an SSD read, 21 levels take up to 2 milliseconds per lookup, and at 5 to 10 milliseconds for a spinning disk they take 100 to 200 milliseconds.

Worse, each of those reads fetches a whole page, 8 KiB in PostgreSQL, and delivers one useful key of perhaps 20 bytes. The binary tree reads 8 KiB to make one yes-or-no decision. The comparisons were never the cost. The cost the structure has to cut is page reads.

Fan-Out

A B-tree node is one page. It holds a sorted run of keys with a child pointer between each pair and at both ends, so a node with k keys has k plus one children, and one comparison-driven step through it picks the child whose range holds the target. With 8 KiB pages and entries of about 20 bytes, a key and a pointer, a node holds about 400 entries.

The height is then the logarithm to base 400 instead of base 2. One level holds 400 keys, two hold 160,000, three hold 64 million and four about 25 billion. Every table most engineers will ever index fits in three or four levels. The search inside a node is a binary search over a sorted array already in memory, the subject of Chapter 7, and at about nine comparisons among 400 keys it is nearly free next to the page read that fetched the node.

The same trade applies one level up the hierarchy. A cache line is to RAM what a page is to disk, which is why Rust's standard ordered map, BTreeMap, is an in-memory B-tree rather than a red-black tree: fewer, wider nodes mean fewer cache misses per lookup.

Staying Balanced by Splitting

A new key goes into the leaf where a search for it ends. When that leaf is already full, it splits into two half-full pages and passes a separating key up to its parent, which gains one key and one child. If the parent is full too, it splits in turn and passes a key up again. A split of the root creates a new root above it, and that is the only way the tree ever grows taller.

Because the tree grows only at the top, every leaf is always at the same depth. No insert order can unbalance it: sorted keys, reversed keys and random keys all produce a tree with every leaf at the same depth. The sorted-input disaster of Binary Search Trees disappears without a single rotation. Rudolf Bayer and Edward McCreight described the structure in 1970 and published it in 1972, and by 1979 Douglas Comer could title his survey of it "The Ubiquitous B-Tree".

B+ Trees and Linked Leaves

The variant databases use, the B+ tree, keeps every entry in the leaves and only separator keys in the inner nodes. Inner nodes then carry no row data or record pointers at all, so more separators fit in a page, the fan-out rises, and the tree gets shorter still. Each leaf also links to the next leaf in key order.

Those links make range queries cheap. A range query descends once to its first key and then walks from leaf to leaf, reading pages in key order, until it passes the end of the range. "Every term from le to lf" or "every row with a year above 1970" is one descent plus a sequential walk, and sequential reads are the cheapest reads on every rung of the ladder in Chapter 4.

Lantern's On-Disk Index

Chapter 5 drew Lantern's index as a hash table, and each worker does keep one in memory, for the terms it has already looked up. The index file itself is kept in term order: Lantern's term dictionary on disk is a B+ tree keyed by term, and each leaf entry points at that term's postings list. Assume, for the arithmetic, 8 KiB pages and a few hundred terms per leaf page. About 1.5 million terms then need about 5,000 leaves. The level above needs one entry per leaf, and at about 400 entries per page that is 13 inner pages. One root page sits over those.

So the whole top of the tree is a root and 13 inner pages, about 112 KiB, which stays in memory after the first few searches. A term the worker has not yet looked up costs at most one page read through the tree, the leaf itself, and none at all once the page cache holds the 1.8 GB index file, which Chapter 10 describes. A prefix question, the job Lantern's radix tree does in memory in Tries and Radix Trees, is also a range walk along these leaves: descend to the first term starting with the prefix and read forward.

B-Trees in the Databases You Run

PostgreSQL's default index type is a B-tree. InnoDB, MySQL's default storage engine, stores every table as a B+ tree clustered on its primary key. Every SQLite table and index is a B-tree. File systems such as NTFS, APFS and Btrfs keep their metadata in B-trees. They all share its bill. An insert rewrites at least a whole page to change 20 bytes of it, and every index on a table is another tree to update on every insert, delete and change to an indexed column.

The order keys arrive in decides how the tree fills. Keys that arrive in order, an auto-increment id or a time-ordered UUID such as the version 7 UUIDs standardized in 2024, all land in the rightmost leaf, which stays in memory; engines recognize the pattern and split that page unevenly, so full pages are left nearly full behind it. Random keys, such as random UUIDs, land on a different leaf every time, pull pages from all over the tree into memory, and split pages everywhere. Measured on a B+ tree of 300,000 random keys in Python, leaves averaged 70 percent full, the textbook figure of about 69 percent. The same data takes more pages, and every insert touches a page that may not be in memory.

The engine around the tree, from the query planner to write-ahead logging, concurrency control and the other index types, is the subject of PostgreSQL Deep Dive. This book stops at the structure.