How does a B-tree index speed up a query, and what does it cost? When would you not add an index?
Key points
- A B-tree keeps keys sorted in a balanced tree so lookups and range scans are O(log n) page reads instead of a full table scanIn plain words: An index is a sorted lookup tree, like the index of a book, so finding rows takes a few hops instead of reading every page
- Every index must be updated on insert, update and delete, so writes slow down and storage growsIn plain words: Every change to the table must also update each index, so writes get slower and more space is used
- Covering indexes include all needed columns so the query never touches the tableIn plain words: If the index already holds every column the query wants, the table itself is never opened
- Low-selectivity columns, tiny tables and write-heavy tables with rare reads often do not justify an indexIn plain words: An index is not worth it when most rows match, when the table is tiny, or when the table is written constantly and rarely read
- Hash indexes give O(1) equality lookups but no range or ordering supportIn plain words: A hash index finds exact matches in one step but cannot do ranges or sorted output
Model answer
Without an index, WHERE email = ? reads every row of the table. An index is a separate structure that stores the indexed column values in sorted order along with pointers to the rows.
B-tree mechanics. Keys live in fixed-size pages arranged as a balanced tree with a very high fan-out (hundreds of children per node), so even a billion rows is only three or four levels deep. A lookup descends from the root to a leaf in a handful of page reads, and because leaves are linked in order, BETWEEN, ORDER BY and prefix queries can walk the leaf chain without visiting the tree again.
What it costs
- Every write updates the table and each index; page splits can cascade.
- Storage: an index on a wide column can rival the table in size.
- Planner complexity: more indexes means more candidate plans and stale statistics hurt more.
When not to index
- A column with few distinct values (
is_active) where the index would return half the table anyway; a sequential scan is cheaper. - Tables small enough to fit in a few pages.
- Columns written constantly but queried rarely.
Variants worth naming. A composite index on (user_id, created_at) serves queries that filter on user_id and sort by time. A covering index also stores the columns the query selects, so the table is never touched (index-only scan). Partial indexes cover only rows matching a predicate. Hash indexes answer equality in O(1) but cannot do ranges. LSM trees trade read amplification for sequential writes and are the engine behind Cassandra, RocksDB and LevelDB.
The crisp version: "an index turns a scan into a tree walk, costs you on every write, and should mirror your hottest WHERE and ORDER BY clauses."
Likely follow-ups
- Why can a query planner choose a full scan even when an index exists?
- How does an LSM tree differ from a B-tree for write-heavy workloads?