Module 07 · Databases · Lesson 4 of 13
B-trees and B+ trees
The structure behind almost every relational index: a shallow, wide tree of disk pages that finds any key in a few reads and scans ranges in order. Splits, clustered and covering indexes, and the write amplification you pay.
The video walkthrough is part of Pro.
See what Pro includesWhy it matters
When you add an index and a query goes from 30 seconds to 3 milliseconds, a B-tree did that. It is the data structure under nearly every relational index, most document database indexes and many key-value stores, and understanding its shape explains index behaviour that otherwise looks like folklore: why range queries are fast, why random inserts hurt, why composite index column order matters, and why a table with ten indexes writes slowly.
The idea
Disks and SSDs read in pages (typically 4 to 16 KB), and a round trip to storage costs far more than any amount of in-memory work. A B-tree is a search tree designed around that fact: each node is one page holding hundreds of keys, so the tree is very wide and very shallow. A table with a billion rows needs a tree only three or four levels deep, and the top levels stay cached in memory, so a lookup costs one or two actual disk reads.
B-tree versus B+ tree
In a classic B-tree, keys and values live in every node. In a B+ tree, internal nodes hold only keys for routing and all values live in the leaves, which are linked left to right. Databases almost universally use B+ trees: internal pages pack more keys (higher fan-out, shallower tree), and the linked leaves make WHERE id BETWEEN 100 AND 200 or ORDER BY created_at a single descent followed by a sequential walk. When people say "B-tree index" they nearly always mean B+ tree.
Keeping it balanced
Inserting into a full leaf splits it into two half-full pages and pushes a separator key up; if the parent is full it splits too, and in the rare case the root splits, the tree grows one level. Deletes that empty a page below a threshold merge or rebalance with a sibling. Every leaf is always at the same depth, which is what guarantees the predictable lookup cost. Inserting keys in order (an auto-increment id, a timestamp) always appends to the rightmost leaf and splits are cheap; inserting random keys (a UUIDv4) splits pages all over the tree, fragments them to about 70 percent full and dirties far more pages per insert, which is why ordered ids and time-sortable UUIDs (v7) are preferred as primary keys.
Clustered and secondary indexes
A clustered index stores the table rows themselves in the leaves, in key order; InnoDB's primary key and SQL Server's clustered index work this way, so a primary key lookup is one tree descent to the row. Secondary indexes store the indexed columns plus a pointer to the row (the primary key in InnoDB, a physical location in Postgres), so a lookup is a descent in the secondary tree followed by a fetch of the row, two trees for one query. A covering index that includes every column the query needs skips the second step entirely, which is why INCLUDE columns exist.
Composite keys and column order
A composite index on (tenant_id, created_at) sorts by tenant first and time within tenant. It serves "all rows for tenant 7 in June" with one descent and a scan, and it is useless for "all rows in June across tenants", because June rows are scattered through every tenant's section. The leftmost prefix rule follows directly from the tree being sorted by the concatenated key.
Write amplification
A single row insert touches the clustered tree and every secondary index tree: ten indexes means roughly eleven page writes plus the write-ahead log. Reads are cheap because writes did the work in advance. This read-optimised bias is exactly what the next lesson's LSM trees invert.