Why it matters

Every SQL database uses B-trees for most indexes. Understanding them explains why certain queries are fast, why others aren't, and how to design schemas for performance.

Advertisement

The architecture

Structure: balanced tree; each node holds many keys (~100-1000). Leaves hold data or pointers.

Height: log_b(n) where b is branching factor. Even billions of rows fit in 3-4 levels.

B-tree structureRoot nodeup to root fanoutInternal nodesroute to childrenLeaf nodesdata or pointer3-4 levels handle billions of rows; each level = one disk seek in worst case
B-tree layers.
Advertisement

How it works end to end

Lookup: walk from root, using key comparisons to pick child at each level. O(log n) comparisons and disk reads.

Range scan: find lower bound, iterate leaves sequentially (leaves linked in most implementations).

Insert/delete: maintain balance via node splits and merges.

Clustered vs secondary: clustered index stores table data in tree; secondary points to primary key.