The problem: find one row among billions, fast#
TL;DRthe 30-second version
- Every node is one disk page. Internal nodes hold only keys and child pointers, so they route. Leaf nodes hold the real data, sorted.
- Hundreds of keys per page make the tree wide and shallow. With a fanout of about 500, a 4-level tree indexes about 62 billion entries, and a lookup reads 3 or 4 pages. The top levels stay in RAM.
- Leaves are chained in a linked list, so a range scan finds the first leaf and walks the chain.
- A full leaf splits and pushes a separator key up. Every leaf stays at the same depth.
- Reads and ranges are fast. Random inserts cause page splits and random writes, which is the weakness LSM trees attack.
Say a table has a billion rows. They sit on disk in pages. A page is the unit the database reads and writes, usually 4 KB to 16 KB. Reading one byte costs about the same as reading the whole page, so the database thinks in pages. The cost of an index is the number of pages it has to fetch.
The obvious idea is a balanced binary search tree. It gives O(log n) lookups, but the log is base 2. For a billion keys that is about 30 levels. If each node is a disk page, one lookup is about 30 random disk reads. Disk seeks are the bottleneck, not comparisons, and 30 seeks per lookup is far too many.
How it works: route at the top, store at the bottom#
A B+ tree has two kinds of node. Each one is a disk page.
- Internal nodes hold only keys and child pointers. Each key is a separator: keys smaller than it go to the left child, keys equal or larger go right. They exist only to route you to the right leaf.
- Leaf nodes hold the actual key-value pairs in sorted order. Each leaf also points to the next leaf, so all the leaves form one sorted chain.
Internal nodes hold separators only. Leaves hold the real key-value data.
- [30]separator
- [10 · 20]< 30
- [5 8]
- [10 15]
- [20 25]
- [40 · 50]≥ 30
- [30 35]
- [40 45]
- [50 60]
- [10 · 20]< 30
To find a key, start at the root. Compare the key with the separators and follow the matching child pointer. Repeat at each level until you reach a leaf. Then scan the leaf's handful of keys. If the key is not there, it does not exist.
PredictA B+ tree index has 4 levels: the root, two internal levels, and the leaves. How many of those 4 pages are actually read from disk on a typical point lookup?
Hint: Which pages get touched on every single query, whatever the key?
Usually just one, the leaf. The root is read on every query, so it stays in the buffer pool (the database's page cache). The internal levels below it are read so often they almost always stay cached too. Only the leaf page, which holds the specific key, is likely to cost a real disk read. That is why a shallow, high-fanout tree works so well: the small upper levels live in RAM and absorb most of the work.
A range query like 'all orders from January to March' is where the leaf chain pays off. Descend once to the leaf holding the start of the range. Then follow the chain from leaf to leaf until you pass the end. You never climb back up. That is O(log n + k) for k results, and it is why ORDER BY and BETWEEN are cheap in SQL databases.
Inserts split, deletes merge#
An insert goes to a leaf. Walk down the same path a search would, and add the key in sorted position. But a page has a fixed size. When a leaf gets one key too many, it splits.
- Split the full leaf in two. The left half keeps the lower keys, the right half gets the upper keys.
- Push the first key of the right half up into the parent as a new separator.
- If the parent is now too full, split it too, and keep going up.
- If the root splits, create a new root above it. This is the only way the tree gets taller.
A delete removes the key from its leaf. If the leaf drops below half full, that is called underflow, and there are two fixes. Borrow: if a neighbouring leaf has spare keys, move one over and update the parent's separator. Merge: if the neighbour is at the minimum too, join the two leaves into one and remove the separator from the parent. The parent may underflow in turn, so repeat upward. If the root ends up with one child, drop it and the tree gets one level shorter.
Complexity: why a 4-level tree indexes billions#
Let f be the fanout, the number of children per internal node. A tree of n entries has height about log base f of n. Every operation walks one root-to-leaf path, so search, insert, and delete each cost O(log_f n) page reads. A range scan that returns k rows costs O(log_f n + k/b): one descent, then k/b leaf pages, with b entries per page.
| Operation | Cost | Disk reads (typical) |
|---|---|---|
| Point lookup | O(log_f n) | 1–2 (upper levels cached) |
| Insert / update | O(log_f n) | 1 read + 1 write, more on a split |
| Delete | O(log_f n) | 1 read + 1 write, more on a merge |
| Range scan (k rows) | O(log_f n + k/b) | 1 descent + ⌈k/b⌉ leaf pages |
How big is f? Take a 16 KB page, the MySQL InnoDB default, and an internal entry of about 16 bytes: an 8-byte key plus a child pointer. That is about 1000 children per node at best. With larger keys and partly filled pages, a realistic fanout is 300 to 500.
| Fanout f | Height 3 (f³) | Height 4 (f⁴) |
|---|---|---|
| 100 | 1,000,000 | 100,000,000 |
| 300 | 27,000,000 | 8,100,000,000 |
| 500 | 125,000,000 | 62,500,000,000 |
So a tree four levels deep with a fanout of 500 addresses about 62 billion entries. The root and the next one or two levels are tiny next to the data and are hit on every query, so the database keeps them in its buffer pool. A point lookup costs one or two disk reads no matter how large the table grows.
Strengths and limits
- Predictable reads. A search always takes O(log_f n) pages, with no bloom filter and no level probing. Latency is tight and uniform, which OLTP (interactive transactional) workloads need.
- Cheap range scans. The leaf chain makes ORDER BY, BETWEEN, and prefix scans fast once the start leaf is found.
- In-place updates. Overwriting a value changes one leaf page. No tombstones, no background compaction, low space amplification.
- Write amplification on inserts. One insert can split a page and cascade splits upward, and each dirty page is written back in full. Random-key inserts scatter those writes across the whole tree. That is slow on spinning disks and wears SSDs.
- Hot-page contention. A workload that hammers one key range, like sequential inserts at the right edge or a counter row, concentrates locking on a few pages and their shared ancestors. That caps write concurrency even though the tree is huge.
- Wide rows in the leaves. In a clustered index (InnoDB), the whole row lives in the leaf. Wide rows mean fewer rows per leaf, a taller tree, and more I/O, so large columns are pushed off-page to keep the fanout up.
Many threads share one tree, so pages take short-term locks called latches. Descending, you latch the child before releasing the parent. This is called latch coupling, or crabbing. The root is the hot spot, since every operation passes through it. The Blink-tree (Lehman and Yao, 1981) gives each node a right-link to its successor, so a reader that arrives during a split just follows the link instead of holding latches up the whole path. PostgreSQL's nbtree is a Blink-tree.
B+ tree vs LSM, hash index, and skip list
| B+ tree | LSM tree | Hash index | Skip list | |
|---|---|---|---|---|
| Point read | O(log_f n), 1–2 reads | O(log n), may probe levels | O(1) average | O(log n) |
| Write | In-place; splits on insert | Sequential, batched (fastest) | O(1), in-place | O(log n), in-memory |
| Range scan | Excellent (linked leaves) | OK (merge across SSTables) | None (unordered) | Good (sorted links) |
| Space | Compact; some page slack | Bloat until compaction | Compact + load factor | Pointer overhead |
| Lives on | Disk | Disk | Memory or disk | Memory (e.g. memtables) |
A hash index beats a B+ tree on point lookups but cannot do ranges or ordered scans at all. That is fatal for ORDER BY and BETWEEN, so in SQL databases it is a niche add-on. A skip list has the same O(log n) bounds and far simpler concurrent code, but its scattered pointers suit memory, not paged disk. It shows up in Redis sorted sets and LSM memtables.
Against the LSM tree the trade is symmetric. The B+ tree wins reads, range scans, and space. The LSM tree wins write throughput by turning random writes into sequential ones. CockroachDB, TiKV, and MyRocks put an LSM (RocksDB) under a sorted, range-scannable key-value interface for that reason.
Where B+ trees run in the wild
When a database says it has a "B-tree index", it is almost always a B+ tree.
- PostgreSQL. The default index type (nbtree) is a Blink-tree. Table rows live in a separate heap, so an index entry points to a heap tuple.
- MySQL / InnoDB. The table itself is a B+ tree: the clustered index stores full rows in the leaves, ordered by primary key. Secondary indexes are separate B+ trees whose leaves hold the primary key, so a secondary lookup does two descents.
- SQLite. Every table and index is a B-tree. The file format is literally a set of B-tree pages.
- Oracle, SQL Server, Db2. All default to B+ tree indexes. SQL Server's clustered and nonclustered indexes mirror InnoDB's clustered and secondary split.
- MongoDB / WiredTiger. The row store is a B+ tree with per-page in-memory update structures. An LSM option exists, but B+ tree is the default.
- Filesystems. NTFS, HFS+ and APFS, ext4's HTree directories, XFS, and ReFS index file metadata and extents with B+ tree or B-tree structures.
Common misconceptions and gotchas
B-tree vs B+ tree: what is the actual difference?
In a B-tree (Bayer and McCreight, 1972), every node stores keys together with their values, and there is no leaf chain. A lookup can stop early at an internal node, but the values lower the fanout and range scans have to walk up and down the tree. In a B+ tree, values live only in the leaves, internal nodes hold keys purely as separators, and the leaves are chained. That gives a shallower tree and O(k) range scans. Nearly every production database labelled "B-tree" is really a B+ tree.
Why not just use a binary search tree on disk?
A BST has fanout 2, so its height is about 30 for a billion keys. If each node is a disk page, that is about 30 random disk reads per lookup, and seeks dominate the cost. A B+ tree packs hundreds of keys per page, so the height drops to 3 or 4.
Why are random inserts slow on a B+ tree?
An in-place update reads the target leaf, changes it, and writes it back. Random keys, like a UUIDv4 primary key, scatter those targets across the whole tree, which means random I/O. Worse, a full leaf must split: allocate a new page, update the parent, and sometimes cascade upward. One logical insert becomes several page writes. A time-ordered key (auto-increment, or UUIDv7) always appends to the rightmost leaf, so pages fill in order with few splits. This is a classic InnoDB clustered-index gotcha.
Does deleting a row shrink the index file?
Usually not right away. Most engines do not merge underfull pages on every delete. They leave the slack for future inserts and only reclaim a page once it is fully empty. A delete-heavy table can leave the index bloated until you REINDEX or VACUUM (Postgres) or OPTIMIZE TABLE (MySQL).
In an interview
Lead with the purpose. A B+ tree keeps data sorted across disk pages, giving O(log_f n) point lookups and O(log_f n + k) range scans, and the guarantee holds for every query, not just the average one. The crux is fanout: a node is a page holding hundreds of keys, so the tree is only 3 or 4 levels deep and the upper levels stay cached. Contrast it with the LSM tree: the B+ tree wins reads and range scans, the LSM wins write throughput.
Know the parts. Internal nodes route, leaf nodes store, and the leaf chain enables range scans. Know what a split looks like: a root split is the only way the tree grows taller, and repeated merges can shrink it. Be ready for the B-tree vs B+ tree distinction, why a BST loses on disk, and why random-key inserts are slow. Name real systems: PostgreSQL nbtree, MySQL InnoDB's clustered index, SQLite, WiredTiger, and most filesystems.
References and further reading
- Bayer & McCreight — Organization and Maintenance of Large Ordered Indexes (1972) — the original B-tree paper, Acta Informatica 1
- Douglas Comer — The Ubiquitous B-Tree (ACM Computing Surveys, 1979) — the classic survey; defines B-tree vs B+ tree vs B*-tree
- Lehman & Yao — Efficient Locking for Concurrent Operations on B-Trees (1981) — the Blink-tree right-link design PostgreSQL uses
- PostgreSQL Documentation — B-Tree Indexes — the nbtree access method: structure, deduplication, behavior
Ready to try it?
The simulator is a real, deterministic implementation — pick a scenario and step through it, scrubbing the timeline forward and backward through every change.