B-Tree Depth and Fan-Out: Why an Index on 100 Million Rows Is Four Levels Deep
Because each B-tree node is a whole page holding hundreds of keys, the tree branches very widely, and that fan-out is what keeps it shallow: even an index over a hundred million rows is usually about four levels from root to leaf. So an index lookup costs roughly four page reads to reach the leaf, plus whatever it takes to fetch the row itself, and doubling the table adds a fraction of a level rather than doubling the work. This is the number that makes index lookups feel instant and makes 'the table got bigger' a poor explanation for a query that suddenly got slow.
Questions this Concept answers
Why does a B-tree stay so shallow as a table grows into the hundreds of millions of rows?
J
jeremy
Text
Understanding the mechanics of PostgreSQL B-Tree indexes
A PostgreSQL B-tree index is stored as 8 KB pages, and each page holds hundreds of keys, so the tree branches very widely and stays shallow. The article measures a real index with the pageinspect ext…