The Shape
A B tree index, the default in most relational databases, is a balanced tree of nodes that keep keys in sorted order. Internal nodes hold key boundaries and pointers to child nodes, while leaf nodes hold the indexed keys and pointers back to the table rows.
Why It Is Fast
Each node holds many keys, so the tree is wide and shallow. A lookup starts at the root and follows one pointer per level:
- At each node, compare the search key to the boundaries.
- Descend into the matching child.
- Repeat until a leaf, then read the row pointer.
Because the tree stays balanced, even a billion rows sit only a handful of levels deep, so a lookup costs a few page reads instead of a full scan.
What It Is Good At
The sorted structure helps more than equality lookups:
- Range scans like dates between two values, by walking leaves in order.
- Prefix and ordering queries, since leaves are already sorted.
- Returning rows already sorted without an extra sort step.
Key idea
A B tree keeps keys sorted in a balanced wide shallow tree, so equality, range, and ordered queries cost a few page reads down to a leaf instead of scanning the whole table.