About 400 entries per page, so 500 million rows need four levels
A lookup reads one page per level, then the table page. Five reads, where the scan needed 10 million.
Five page reads sounds like five trips to disk.
The quiet reason
The three upper levels total about 25 MB and stay cached. A cold lookup usually costs two real reads, leaf and row.
One sorted tree, four kinds of query
- Point: descend once, fetch the row
- Range: descend once, walk the linked leaves
- ORDER BY … LIMIT 20: no sort step
- Prefix
LIKE 'Ban%': a range scan
Look up by email: InnoDB walks two trees, PostgreSQL one
InnoDB keeps rows inside the primary-key tree, so the email index stores the PK. PostgreSQL’s points straight at a heap page.
3×
the page writes, with four secondary indexes
A food-delivery orders table at 2,000 inserts a second makes 12,000 page changes a second, against 4,000 with only the primary key.
B-tree is the default. Four queries want something else.
Each trades something: hash loses ranges, GIN updates are heavy, BRIN is useless if values are scattered.
Index status. Does status = 'delivered' get faster?
Bad: Yes, it’s indexed
92% match: 460 million pointers, each a table page.
Good: Selectivity decides
A straight scan is cheaper. Index predicates that match few rows.
Remember
Three or four levels find any row. Every index taxes every write, so index only the hot paths.