Most relational databases store indexes as B-trees. The shape below is the mental model you need: a short, wide, balanced tree where every lookup costs only a few hops.
Why B-Trees?
B-trees are balanced and shallow. Each node holds many keys (the root above holds 25 and 50), so a tree with millions of rows is still only 3–4 levels deep. Finding a key means walking down from the root, choosing a branch at each level — O(log n) in the worst case, and typically a handful of disk reads.
How a Lookup Works
To find 40: start at the root, see that 40 is between 25 and 50, and descend the middle branch straight to the leaf that holds 30 and 40. Two hops, done. A full scan would have checked every row.
Why Leaves Matter
The leaf nodes point to the actual table rows. Because they’re sorted and linked, a range query like WHERE id BETWEEN 30 AND 60 becomes a single leaf scan — no random hopping. That’s why an index turns both point lookups and range scans into cheap operations.