B Tree

The workhorse structure behind most indexes

A B-Tree (balanced tree) is the classic data structure most database indexes are conceptually built on. It is not a binary tree — each node can hold many sorted keys and have many children, which is exactly what makes it efficient for disk-backed databases.

The shape

A B-Tree has three kinds of nodes:

• Root node: the single entry point at the top.
• Internal nodes: hold sorted keys that act as signposts, directing a search toward the correct child subtree.
• Leaf nodes: the bottom level, where the actual keys (and, in a plain B-Tree, their associated data or pointers) live.

Imagine indexing students.gpa (values 0.0–4.0) conceptually. The root might hold a key like 2.5: anything less goes left, anything greater-or-equal goes right. Each of those children further splits its range with its own sorted keys, and so on, until you reach a leaf node holding the specific GPA value you're searching for along with a pointer to the matching row(s).

Why log(n) depth matters at scale

Because each node holds many keys (not just one, like a binary tree), a B-Tree stays very "flat" (shallow) even for huge tables. If each node can hold, say, 100 keys/children, then a B-Tree over 1,000,000 rows needs only about log₁₀₀(1,000,000) ≈ 3 levels to reach any leaf. Compare that to a full table scan needing up to 1,000,000 comparisons — a B-Tree lookup on the same data needs only a handful of node reads (traversing 3 levels), each of which is a fast comparison against sorted keys.

This shallow depth is precisely why B-Trees scale so well: doubling the table size barely increases the tree's depth (logarithmic growth), so lookup time grows extremely slowly compared to the data size.

Balance

"Balanced" means every path from the root to a leaf has the same length — the tree doesn't become lopsided as data is inserted and deleted. The structure automatically splits and merges nodes to maintain this balance, which is what guarantees consistent, predictable lookup performance regardless of insertion order.

Edge cases

• A B-Tree built on a column with very few distinct values (e.g., a boolean flag) still works correctly, but is a poor index candidate in practice — see Selectivity (20.12).
• As rows are inserted, nodes can fill up and must split, and as rows are deleted, nodes can become underfull and may merge — these rebalancing operations are the source of the "index maintenance" overhead discussed in 20.14.
• A plain B-Tree (as opposed to the B+ Tree variant covered next in 20.3) can store data pointers in internal nodes too, which actually makes range scans less efficient — this is the key motivation for the B+ Tree refinement.

Interview-style Q&A

Q: Why is a B-Tree preferred over a plain binary search tree for database indexes? A: A B-Tree's wide, shallow shape means far fewer node reads are needed to reach a leaf, which matters enormously when each node read is a disk I/O operation — minimizing I/O is critical for performance.

Q: What does "balanced" mean in B-Tree? A: Every leaf is at the same depth from the root; the tree rebalances itself (via node splits/merges) as data changes, so lookup cost stays predictable.

Key takeaway: the B-Tree's wide/shallow shape is what turns a linear, million-row search into a handful of comparisons — the foundational reason indexes are fast.