codequest / system design
Core concept 18 of 21

Database indexes

Find rows without scanning the whole table, and why every index makes writes a little slower.

Why indexes matter

Without an index, finding rows that match a condition means reading the whole table (a full scan). An index is a separate sorted structure, usually a B-tree, that maps column values to row locations, the way a book's index maps words to pages.

Try it

Grow the table and compare a full scan with an indexed lookup. Then add indexes and see what it costs writes.

Query: SELECT * FROM users WHERE email = 'priya@example.com'

No index: full scan
1M rows
~50 ms
Index on email: B-tree
3 pages
~0.3 ms, 3 levels deep

A B-tree with ~200 keys per page finds one row among 1M in 3 steps. Grow the table 1,000× and it costs one or two more steps; the scan costs 1,000× more.

Every insert writes the row plus 2 index entries: about 3× the write work, and more storage.

Kinds of index

  • B-tree (the default): equality and range queries (>, BETWEEN, ORDER BY).
  • Hash: equality only, very fast.
  • Composite (several columns): an index on (user_id, created_at) answers "this user's latest posts" directly. Column order matters: it helps queries that filter on user_id first.
  • Covering: includes every column the query needs, so the table itself is never read.
  • Full-text and geospatial indexes for search and "nearby" queries (or a separate search engine).

The trade-off

  • Every insert, update and delete must also update every index on the table.
  • Indexes take storage and memory; an index that doesn't fit in memory is much slower.
  • Index the columns you filter, join and sort on in hot queries, and nothing else. Check with EXPLAIN.

In the interview

  • When you write a schema, say which columns are indexed and why: "index on (conversation_id, sent_at) to page through messages".
  • For write-heavy tables, keep indexes few.
  • Mention composite indexes and that column order follows the query.