Database Indexes: What They Cost You for the Speed They Buy

A B+tree index is a sorted pointer structure built on top of your table. Each interior node holds a range of keys and a pointer to the next level down. Each leaf node holds keys in sort order, with pointers to the underlying rows on the heap. A lookup descends from the root through a handful of levels, comparing your search key at each step. For a table of a billion rows, that is roughly four to five page reads instead of a billion. The cost is O(log n), and the constant factor is tiny because each page holds hundreds of keys.

The structure has a few rules that surprise people. Composite indexes are direction sensitive. An index on (user_id, created_at) can serve a query that filters on user_id alone, or on both user_id and created_at, because the tree is first sorted by user_id and then by created_at within each group. It cannot serve a query that filters only on created_at. The tree has no way to find recent rows without first picking a user. This is the leftmost prefix rule, and getting the column order wrong is the most common reason an index "exists but is not used."

Covering indexes are the next trick worth knowing. If your query selects only columns that appear in the index, the database never has to visit the heap. The index leaf has everything it needs. This is the difference between an index only scan and an index plus heap fetch, and on a wide table with cold pages, it can be a 10x speedup. Postgres calls this INCLUDE columns. MySQL gets it for free if all selected columns are in the index.

Hash indexes serve equality lookups in O(1) but cannot answer range queries at all. You almost always want B+tree unless you have a very specific workload.

The production failure I keep seeing is the silent write tax. A team added an index on (user_id, created_at) to speed up a feed query. The reads got faster. A week later, p99 write latency on the table doubled, throughput dropped 40 percent, and the nightly backup ran past its window. Each INSERT now had to update two indexes, the primary key plus the new one. The index also nearly doubled the table's disk footprint. The fix was to check pg_stat_user_indexes.idx_scan for every index on the table. Three of the four existing indexes had zero scans in 30 days. Dropping them paid for the new one and gave back the write headroom.

Index design is a budget exercise, not a free win.