Database Indexes

Without an index, finding a row that matches a condition means scanning every row in the table — a full table scan. An index is a separate, sorted data structure that maps a column's values to the location of the rows that hold them, so the database can jump straight to matching rows instead of reading the whole table. It's the same idea as a book's index: you don't scan every page for a term, you look it up in a sorted list that tells you exactly which page to turn to.

The structure: B-trees, briefly

Most general-purpose indexes are built on a B-tree (or a close variant), a balanced tree structure that keeps values sorted and lets the database find any value in O(log n) steps instead of O(n). Each lookup walks down the tree, comparing the target value at each node and following the branch that could contain it, until it reaches the row's location.

System Design Lab

That O(log n) vs. O(n) gap is the entire value proposition, and it's exactly why "add an index" is one of the single highest-leverage fixes for a slow query — turning a scan of millions of rows into a handful of tree traversals.

The tradeoff nobody skips for free: writes get slower

An index isn't free to maintain — every INSERT, UPDATE, or DELETE on an indexed column has to update the index's data structure too, not just the underlying table. More indexes on a table means more work on every write, which is why indexing isn't "just add indexes on everything": each one is a deliberate tradeoff of write throughput for read speed on that specific column.

This is worth stating explicitly in an interview: a table that's read constantly and written rarely (a product catalog) can afford many indexes; a table with heavy write volume and infrequent specific-column lookups (a raw event log) usually shouldn't be indexed aggressively, because the write cost isn't justified by the read benefit.

What to index — and what "selectivity" means

An index only helps if it actually narrows the search meaningfully. A column's selectivity is how much an index on it actually cuts down the candidate rows: an index on a boolean is_deleted column with only two possible values barely helps, since the database still has to scan roughly half the table either way; an index on email, where values are nearly unique, is highly selective and turns a scan into a near-instant lookup. The practical rule: index columns that appear often in WHERE clauses, JOIN conditions, or ORDER BY, and that have high selectivity — an index on a low-cardinality column is frequently wasted write overhead for little read benefit.

Composite indexes (an index across multiple columns together, e.g. (user_id, created_at)) matter too: an index is only usable left-to-right by the columns it was built on, so a composite index on (user_id, created_at) speeds up queries filtering by user_id alone or by both columns together, but does nothing for a query that filters by created_at alone.

Indexes and the rest of this module

An index is what makes a single machine's lookups fast; it doesn't do anything about how much data one machine can hold or how much write traffic it can absorb — those are the problems Database Sharding and Database Scaling solve. It's also worth distinguishing an index from a cache conceptually: an index is a structure inside the database that speeds up a query against the full, authoritative dataset, while a cache (covered in the Caching Fundamentals module) sits in front of the database entirely and serves a copy of already-computed results, skipping the database on a hit.

Why this matters in an interview

"Add an index" is a common instinct, but a strong answer names which column, why it's selective enough to help, and acknowledges the write-side cost. If a design has a write-heavy table, explicitly reasoning about which few columns actually justify an index — rather than indexing everything defensively — is a concrete signal of understanding the tradeoff, not just the existence of indexes.

Adding an index on a frequently-queried column: pros and cons

Pros

• ✓Turns an O(n) full table scan into an O(log n) lookup for matching queries
• ✓Speeds up JOINs and ORDER BY clauses that use the indexed column(s)
• ✓One of the highest-leverage, lowest-effort fixes for a slow query

Cons

• ✕Every write to the table now also updates the index — slower INSERT/UPDATE/DELETE
• ✕Consumes additional disk space proportional to the indexed column's data
• ✕A low-selectivity index adds write cost while barely improving read performance

Further Reading

• Use The Index, Luke! — a widely recommended, deep, database-agnostic guide to how indexes actually work and how to use them well.
• PostgreSQL Docs — Indexes — a concrete reference for index types (B-tree, hash, GIN, GiST) and when each applies.