How do database indexes work and what are the trade-offs of adding them?
Take a moment.
Say your answer out loud or write it down first — retrieval is what makes it stick. Reveal when you're ready.
Short answer
An index is a data structure (typically a B-tree or LSM-tree) that maps column values to row locations, turning O(n) full-table scans into O(log n) lookups. Indexes speed up reads and WHERE/JOIN/ORDER BY operations but slow down writes (every insert/update must maintain the index) and consume storage. Add indexes for frequently queried columns; remove unused ones that only tax writes.
Detailed explanation
Without an index, a database scans every row to satisfy a query (full table scan, O(n)). An index creates a sorted auxiliary structure — most relational databases use B-trees (or B+ trees), LSM-trees in systems like Cassandra and RocksDB — that lets the engine jump directly to matching rows. A B-tree index keeps data balanced and sorted, supporting equality and range queries in O(log n). Composite indexes (multiple columns) follow leftmost-prefix rules: an index on (last_name, first_name) supports queries on last_name alone but not first_name alone. Indexes accelerate SELECT, JOIN, ORDER BY, and GROUP BY. Costs: every INSERT, UPDATE, and DELETE must update every affected index, adding write latency and lock contention; indexes consume disk and memory (the buffer pool holds index pages); and too many indexes on a write-heavy table creates a bottleneck. The query planner chooses whether to use an index (a scan may still win for high-selectivity queries). Maintenance matters: fragmented indexes need REINDEX/REBUILD; stale statistics lead to bad plan choices. Best practice: index columns in WHERE clauses, JOIN conditions, and sort orders; use covering indexes (include all selected columns) to avoid table lookups; and audit periodically to drop unused indexes. The core trade-off is read speed versus write cost and storage.
Example
A users table with 10M rows:
- Query: SELECT email FROM users WHERE last_name = 'Chen'
- Without index: full scan of 10M rows.
- With B-tree index on last_name: O(log n) traversal to find 'Chen' entries.
Composite index (last_name, first_name):
- Speeds up WHERE last_name = 'Chen'
- Also speeds up WHERE last_name = 'Chen' AND first_name = 'Wei'
- Does NOT speed up WHERE first_name = 'Wei' (not leftmost).Interview tip
Explain what an index does (avoid full scans), name the structure (B-tree), and immediately state the trade-off: faster reads, slower writes and extra storage. Mentioning the leftmost-prefix rule for composite indexes is the detail that elevates the answer.
Common mistakes
- Saying indexes always help — they slow writes and consume space.
- Not knowing the read-versus-write trade-off.
- Forgetting the leftmost-prefix rule for composite indexes.