Database Indexing

An index is a separate, sorted data structure the database keeps alongside a table so it can find rows without reading every one — the same way a book's index lets you jump to a topic instead of scanning every page. It's the difference between a query that returns in a millisecond and one that crawls through millions of rows.

A missing index looks exactly like a scaling problem: high database CPU, slow queries. It usually isn't. Check for a missing index before you reach for replicas or shards — it's free and often the whole fix.

Why a scan is slow and an index is fast

Without an index, WHERE email = ? forces the database to check every row — an O(n) sequential scan. On a 5-million-row table that's 5 million comparisons.

An index stores the column sorted in a B-tree (a balanced tree), where each step eliminates half the remaining rows — an O(log n) lookup. Finding one email among 5 million now takes about 23 comparisons instead of 5 million. That's the entire reason indexes exist.

-- Create an index
CREATE INDEX idx_users_email ON users (email);
 
-- Confirm the DB uses it: look for "Index Scan", not "Seq Scan"
EXPLAIN ANALYZE SELECT * FROM users WHERE email = 'a@b.com';

Composite indexes: order matters

An index can cover multiple columns, e.g. (status, created_at). The columns are stored in that exact order, so the index only helps when your query filters left-to-right in that order.

An index on (status, created_at) makes WHERE status = 'open' ORDER BY created_at fast — it narrows to open rows, already sorted by date. But a query filtering only on created_at can't use it well, because the index is sorted by status first. The rule: put the most-filtered (most selective) column first, matching your query's shape.

When to add an index — and when not to

✅ Index: primary keys (automatic), foreign keys (Postgres does not index these for you), columns often used in WHERE / JOIN / ORDER BY, and high-cardinality columns (many distinct values, like email).

❌ Don't index: tiny tables (a scan is already instant), columns with very few distinct values (a boolean index barely helps), columns written far more than read, or "every column just in case."

The cost is real: every index slows down writes (each INSERT/UPDATE must update the indexes too) and uses disk. Indexes are a read-speed-for-write-speed trade — add them deliberately.

Don't forget N+1

A query being slow isn't always a missing index — it's often an N+1 query: fetch 100 posts (1 query), then loop and fetch each author separately (100 queries). That's 101 round trips that should be one join or one batched follow-up. Fix it with a join or an eager-load before you reach for indexes.

Specialised indexes worth a mention

• Full-text (GIN / tsvector in Postgres): ranked text search instead of slow LIKE '%term%'.
• Geospatial (GiST / R-tree): "points near this location" queries.
• Hash: exact-match-only lookups (no range queries).

Knowing these exist lets you answer "how would search work?" with "a full-text index, or a dedicated search engine like Elasticsearch if it's the core feature" instead of hand-waving.

What to say in an interview

Reach for an index before heavier machinery, and name the exact one:

"The login query filters by email on a large users table, so I'd add a B-tree index on email — that turns a full scan into a log-n lookup. For the 'open tickets, newest first' screen I'd use a composite index on (status, created_at) so the filter and the sort both come from the index. I'd confirm with EXPLAIN ANALYZE that it's an index scan, not a seq scan, before assuming I need replicas."

Next up: Numbers to Know — the figures that make back-of-the-envelope estimates fast.