How do database indexes work and what are their trade-offs?
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 sorted auxiliary structure (usually a B-tree) mapping column values to row locations, turning O(n) full scans into O(log n) lookups. Indexes accelerate WHERE, JOIN, and ORDER BY but tax every write and consume storage — index the columns you filter and join on, drop the ones you don't use.
Detailed explanation
Without an index the engine scans every row (sequential scan, O(n)). A B-tree index keeps entries sorted and balanced so equality and range queries descend to matches in O(log n), and can return rows pre-sorted for ORDER BY without a separate sort step. Composite indexes on (a, b) follow the leftmost-prefix rule: they serve queries on a alone and on a+b, but not on b alone — column order should follow query patterns (equality columns first, then range). Covering indexes go further by INCLUDE-ing selected columns so the query is answered from the index without touching the table (index-only scan). Costs are real: each INSERT/UPDATE/DELETE must maintain every index on the table (write amplification and lock contention), indexes consume disk and precious buffer-pool memory, and the planner may ignore them for low-selectivity predicates where a scan is genuinely cheaper. Practice: index foreign keys and JOIN columns, WHERE predicates, and sort keys; EXPLAIN to confirm usage; audit with pg_stat_user_indexes for zero-scan indexes and drop them; and on write-heavy tables prefer fewer, narrower indexes.
Example
-- O(log n) lookup instead of scanning 10M rows
CREATE INDEX idx_orders_customer ON orders(customer_id);
-- Composite: serves (last_name) and (last_name, first_name), NOT (first_name) alone
CREATE INDEX idx_users_name ON users(last_name, first_name);
-- Covering: answers the query from the index alone
CREATE INDEX idx_orders_cover
ON orders(customer_id) INCLUDE (total_cents, placed_at);
-- SELECT total_cents FROM orders WHERE customer_id = 7; -- index-only scanInterview tip
State the mechanism (B-tree, O(log n)), the trade-off (faster reads, slower writes + storage), and one pro detail — leftmost-prefix or covering indexes. That trio is the complete interview answer.
Common mistakes
- Indexing everything and wondering why writes slowed down.
- Building (a, b) and expecting it to speed up queries on b alone.
- Never verifying with EXPLAIN whether the index is actually used.