The height of a tree with n keys is about log base fan-out of n. A B-tree page holds hundreds of keys, so millions of rows need only a few levels.
Fan-out
The number of children a tree node can have; a larger fan-out makes the tree shallower.
The height of a tree with n keys is about log base fan-out of n. A B-tree page holds hundreds of keys, so millions of rows need only a few levels.