Under the Hood: The B+ Tree Storage Architecture
Relational databases almost exclusively use B+ Trees rather than traditional binary search trees (BST or Red-Black trees). A binary tree has a fanout of 2, requiring 20 to 30 pointer hops across disk to locate a record in a million rows. A B+ Tree has a massive fanout (typically 100 to 1,000 keys per page), ensuring the tree depth remains 3 or 4 levels even for hundreds of millions of rows.
Physical Page Layout of a B+ Tree
B+ Tree Structural Invariants
- High Fanout: A single 8KB page can store roughly 200 key-pointer pairs for moderately wide keys (300-500 for narrow integer keys, as the worked example below shows). A 3-level tree indexes 2003 = 8,000,000 rows with only 3 disk page reads.
- Data Resides Solely in Leaves: Unlike standard B-trees, internal B+ Tree nodes contain only separator keys and child pointers; actual tuple data (or tuple pointers) resides exclusively in leaf pages. This maximizes internal page fanout.
- Doubly-Linked Leaves: All leaf pages are connected via forward and backward pointers. Executing a range query (
WHERE age BETWEEN 25 AND 35) locates the first leaf in O(log N) time and walks the linked list linearly with zero tree traversals.
Worked example: how tall is the tree?
Suppose we index a BIGINT key in PostgreSQL. Each index tuple is about 16 bytes (8-byte key, 6-byte TID, header and alignment), so an 8 KB page holds about 400 entries at typical fill.
| Levels | Max leaf entries (fanout about 400) | Memory for internal levels |
|---|---|---|
| 1 (root only) | 400 | 8 KB |
| 2 | 160,000 | 8 KB |
| 3 | 64,000,000 | about 3.2 MB |
| 4 | 25,600,000,000 | about 1.3 GB |
A 64M-row table needs only 3 levels. The root and all 400 internal pages (about 3.2 MB) fit in cache trivially, so a point lookup costs one leaf read plus one heap read. This is why B+ trees dominate OLTP.
Insert and split, step by step
The tree grows at the root, not the leaves, so all leaves always stay at the same depth. That is the "balanced" guarantee.
Sequential vs random keys
- Sequential (BIGSERIAL, UUIDv7, Snowflake): inserts always hit the rightmost leaf. PostgreSQL and InnoDB detect this and split unevenly (for example 90/10), leaving pages nearly full. The working set is just the right edge of the tree.
- Random (UUIDv4): each insert lands on a random leaf. With a 20 GB index and 4 GB of cache, most inserts miss cache and cause a random read, and 50/50 splits leave pages about 70% full on average.
How real systems vary
- InnoDB: the table itself is a B+ tree clustered on the primary key (16 KB pages). Secondary indexes store the primary key value.
- PostgreSQL nbtree: the Lehman-Yao variant with right-links, so readers do not block during splits. Deduplication (v13+) compresses repeated keys.
- LSM engines (RocksDB, Cassandra): trade B-tree in-place updates for sequential writes plus compaction. The Storage Engines module covers this.