Indexes & Query Performance
The problem
Without help, finding rows matching a condition means scanning every row in a table — fine for a hundred rows, unusable for a hundred million. Indexes give the database a fast lookup structure so common queries don't pay a full-table-scan cost every time.
Why now
Trees and hash tables already built the two data structures that make fast lookup possible; an index is simply one of those structures, built and maintained by the database over a column, so that a query's WHERE clause can use structured lookup instead of brute-force scanning.
Mental model
An index is a separate, ordered lookup structure — usually a B-tree, occasionally a hash table — mapping column values to row locations, exactly like a book's index maps terms to page numbers instead of forcing a page-by-page read-through. It costs extra storage and slows down writes (the index must be updated too), which is why indexing every column is not automatically a good idea.
Requires
- TreesComputer Science Fundamentals
The default relational database index (a B-tree) is directly the balanced tree structure already covered, exploited specifically for its O(log n) search and its ability to also support range queries.
- Hash TablesComputer Science Fundamentals
Some indexes are hash-based rather than tree-based, trading range-query support for even faster exact-match lookup — the same hash table tradeoffs already covered, applied to database rows.
Unlocks
Used in
- Every production database's performance tuning work
- Primary keys and unique constraints, almost always backed by an index automatically
- Composite indexes over multiple columns for multi-condition queries
- Understanding why an unindexed WHERE clause on a large table is slow, and why adding the right index fixes it
Projects
- Run the same query against a large unindexed table and then against the same table with an appropriate index, comparing execution time directly
- Design a composite index for a query filtering on two columns, and explain why column order in the index matters
Examples
- SELECT * FROM users WHERE email = 'x@y.com' on an unindexed 10-million-row table scans every row; an index on email turns it into a near-instant lookup
- A B-tree index supports both exact-match and range queries (WHERE age > 30), while a hash index only supports exact-match
Resources
- PostgreSQL — Indexesdocs
- Use the index, Lukearticle
Mastery checklist
- I can explain why an index speeds up lookups and slows down writes
- I can choose an appropriate column (or columns) to index for a given query pattern
- I can explain the difference between a B-tree index and a hash index
- I can measure a query's performance improvement after adding an appropriate index