Read-Heavy Indexing: B-Trees

The B-tree is the index structure behind almost every relational database, and it's the reason reads stay fast as tables grow to billions of rows. It is a balanced, sorted tree in which each node holds many keys and is sized to match one disk page (typically 4–16 KB). One disk read loads a whole node with hundreds of keys, so even a huge table is only three or four levels deep.

Structure#

A B-tree has a root, a few layers of internal nodes, and a bottom row of leaf nodes that hold the row pointers.

Keys inside each node are sorted, and they act as signposts: each gap between two keys has a pointer to the child covering that range. Unlike a binary search tree, which splits two ways at each step, a B-tree node splits the search hundreds of ways, which is why the tree stays so shallow.

Databases actually use a variant called the B+ tree: row data (or row pointers) live only in the leaves, and the leaves are linked to each other in order. That link is what makes range scans cheap. Find the first key, then walk sideways along the leaves.

Reading: find key 45#

Follow the highlighted path in the diagram above, one node per level. Each step costs 1 disk read.

That's about 3 disk reads to find 1 row among millions.

At each level you read one node, see which range your key falls into, and follow that pointer down.

Writing: insert key 55#

An insert starts like a read, then changes the leaf and may rebalance the tree.

1. Find where 55 belongs, exactly as in a read: root, then [40 | 50], then 55 > 50 so the rightmost leaf. (2–3 reads)

2. Insert 55 into that leaf. (1 write)

   	Leaf contents
   Before	[51 | 53 | 57 | 58]
   After	[51 | 53 | 55 | 57 | 58]

3. Check whether the leaf is now over capacity.

   • No: done.
   • Yes: split it into two half-full nodes, [51 | 53] and [57 | 58], and push the middle key (55) up into the parent. If the parent overflows too, it splits as well, and this can cascade up to the root. (extra writes)

Splits are what keep the tree balanced: every leaf stays at the same depth, so every lookup costs the same.

Deleting a key#

A delete mirrors an insert, with merging in place of splitting:

1. Find the key (same as a read).
2. Remove it from its node.
3. Check whether the node is now too empty (below the minimum number of keys).
   • No: done.
   • Yes: borrow a key from a sibling, or merge with a sibling. This can cascade up to the parent.

Why writes cost more than reads#

A read walks down the tree and it's done: 3–4 reads, nothing modified.

A write does much more:

1. Walk down the tree (same as a read).
2. Modify the node (a disk write).
3. Maybe split or merge nodes (more writes).
4. Maybe update parent nodes (more writes).
5. Repeat all of this for every index on the table.

That last step is the important one. Every index is its own B-tree, so every INSERT updates the table and every index:

Side by side:

When B-trees fit#

B-trees are the right default in these cases:

• Read-heavy workloads with a mix of exact lookups, range queries and sorting: the typical OLTP database.
• When you need both WHERE id = ? and WHERE created_at BETWEEN ? AND ? on the same data.
• When write volume is moderate. For very write-heavy workloads, see LSM trees.

Key takeaways#

• A B-tree is a shallow, balanced, sorted tree. Each node fills a disk page and holds hundreds of keys.
• A lookup reads one node per level, typically 3–4 disk reads even for billions of rows.
• Databases use B+ trees, with data only in linked leaves, so range scans are cheap.
• Inserts can split nodes and deletes can merge them. That keeps the tree balanced but costs extra writes.
• Every index is another B-tree to update, so over-indexing slows writes (see Indexing Trade-offs).