The cheapest 1000× performance improvement available anywhere in computing — and the thing most slow systems are missing.
Prerequisites: Computer Fundamentals, Databases Overview Time to read: ~24 minutes
A table with 10 million users. You run:
SELECT * FROM users WHERE email = 'bilal@example.com';
Without an index, the database reads every row — a full table scan — comparing each email until it finds a match (or reaches the end).
📐 10 million rows × ~200 bytes = 2 GB to read. From SSD at ~1 GB/s that’s 2 seconds. And that’s per query. At 100 QPS you need 200 seconds of disk time per second. It’s not slow; it’s impossible.
With an index: ~4 disk reads, under 1 millisecond. A 2,000× improvement from one line of DDL.
A 900-page textbook. You want everything about “quicksort.”
Without an index: start at page 1, read every page. Ten hours.
With the index at the back: flip to Q, find “quicksort … 412, 587,” turn to those pages. Thirty seconds.
The index is a separate, sorted structure that maps values to locations. It costs extra pages (storage), and it must be updated whenever the book changes (write cost). That’s the entire trade-off, and it’s exactly the database’s trade-off too.
Almost every relational index is a B+ tree: a balanced tree where all values live in the leaves, and leaves are linked together in sorted order.
[ 50 | 100 ] ← root (in memory)
/ | \
[10|30] [60|80] [150|200] ← internal nodes
/ | \ / | \ / | \
[..] [..] [..] ... [..] [..] ← leaves: value → row pointer
↕ ↕ ↕ ↕
(leaves are linked, so range scans walk sideways)
Why it’s fast: each node holds hundreds of keys (a node is one disk page, ~8 KB), so the tree is extremely wide and therefore shallow.
📐 With a fanout of ~500, a 3-level tree indexes 500³ = 125 million rows. A 4-level tree indexes 62 billion. So any lookup in a realistic table is 3–4 page reads — and the top levels are almost always cached in RAM, so it’s typically one actual disk read.
What B-trees give you beyond equality:
| Query type | Works? |
|---|---|
WHERE email = 'x' |
✅ Equality |
WHERE age > 30 |
✅ Range — find the start, walk the linked leaves |
WHERE name LIKE 'Bil%' |
✅ Prefix — it’s a range |
WHERE name LIKE '%lal' |
❌ Suffix — no. Can’t find a starting point |
ORDER BY created_at |
✅ Leaves are already sorted; no sort step needed |
WHERE LOWER(email) = 'x' |
❌ Function on the column kills the index (unless you index the expression) |
🚨 That last row is one of the most common real-world index failures. WHERE DATE(created_at) =
'2026-07-22' cannot use an index on created_at. Rewrite as a range:
WHERE created_at >= '2026-07-22' AND created_at < '2026-07-23'.
Clustered index — the index is the table. Rows are physically stored in the leaves, in index order. You get one per table (data can only be sorted one way).
Secondary index — a separate structure whose leaves hold a pointer to the row.
🚨 The consequence in InnoDB: a secondary index lookup requires two traversals — walk the secondary index to find the primary key, then walk the clustered index to find the row. This is why a large primary key (a UUID string) makes every secondary index bigger and slower, and it’s part of the argument for small, sequential primary keys. → Unique ID Generation
An index on multiple columns:
CREATE INDEX idx_user_status_date ON orders (user_id, status, created_at);
The index is sorted by user_id, then status, then created_at — like sorting a phone book by
last name, then first name, then middle name.
This one index serves these queries:
WHERE user_id = 42 ✅ leftmost column
WHERE user_id = 42 AND status = 'shipped' ✅ leftmost two
WHERE user_id = 42 AND status = 'shipped'
AND created_at > '2026-01-01' ✅ all three
WHERE user_id = 42 ORDER BY status, created_at ✅ order matches
And cannot serve these:
WHERE status = 'shipped' ❌ skips user_id
WHERE created_at > '2026-01-01' ❌ skips the first two
WHERE status = 'shipped' AND created_at > '2026-01-01' ❌ skips user_id
🚨 This is the leftmost-prefix rule, and it’s the most commonly tested indexing concept in interviews. You can use a contiguous prefix starting from the left. You cannot skip a column.
Column order rules:
(user_id, created_at) works for
user_id = 42 AND created_at > X; (created_at, user_id) does not.ORDER BY so the database skips the sort entirely.Covering indexes are the payoff of composites. If the index contains every column the query needs, the database never touches the table at all:
CREATE INDEX idx_covering ON orders (user_id, status) INCLUDE (total);
SELECT status, total FROM orders WHERE user_id = 42; -- index-only scan
📐 An index-only scan can be several times faster than an index scan plus table lookups, because it
skips the random I/O of fetching rows. Look for “Index Only Scan” in EXPLAIN.
| Type | What it’s for | Notes |
|---|---|---|
| B-tree | Everything by default | Equality, ranges, prefixes, sorting |
| Hash | Exact equality only | Slightly faster for =, but no ranges, no sorting. Rarely worth it |
| GIN (inverted) | Arrays, JSONB, full-text | The index that makes Postgres JSONB and text search viable |
| GiST / SP-GiST | Geometric, geospatial, ranges | “Find points within this box” → Geospatial |
| BRIN | Huge tables with naturally ordered data | Stores min/max per block. Tiny — megabytes for a billion rows. Perfect for time-series appended in time order |
| Bitmap | Low-cardinality columns in analytics | Common in data warehouses |
| Full-text / inverted | Search by words | → Search Systems |
Partial indexes are underused and excellent:
CREATE INDEX idx_pending ON orders (created_at) WHERE status = 'pending';
If 99% of orders are completed and you only ever query pending ones, this index is 1% of the size, stays in memory, and is far faster to maintain. Very common in job-queue tables.
Indexes are not free, and the cost lands on writes.
1. Storage. An index on a column typically costs 10–30% of the table size. Ten indexes can make your indexes larger than your data.
2. Write amplification. Every INSERT, UPDATE (of an indexed column), and DELETE must update
every affected index.
📐 A table with 8 indexes: one insert becomes 9 writes (the row plus 8 index updates), each potentially causing a B-tree page split. This is why bulk-loading advice is always “drop the indexes, load, rebuild.”
3. Memory pressure. Indexes compete with data for the buffer pool. Too many indexes means less room for hot data, and your cache hit rate drops.
4. Optimizer confusion. With many overlapping indexes, the planner may choose badly.
⚖️ The trade in one line: indexes make reads fast and writes slow. A read-heavy table wants many indexes. A write-heavy one wants few.
🎙️ “This table is write-heavy — 20,000 inserts per second — so I’d keep indexes to the minimum the queries actually require. Each additional index is another B-tree to maintain on every write.”
The skill that separates people who guess from people who know.
EXPLAIN ANALYZE
SELECT * FROM orders WHERE user_id = 42 AND status = 'shipped';
What to look for:
| You see | Means |
|---|---|
Seq Scan on a large table |
❌ No usable index. The main thing you’re hunting for. |
Index Scan |
✅ Using an index, then fetching rows |
Index Only Scan |
✅✅ Covering index — never touched the table |
Bitmap Heap Scan |
Combining multiple indexes, or fetching many rows |
rows=1000 vs actual rows=500000 |
🚨 Bad statistics. The planner’s estimate is wildly wrong, so its plan choice is too. Run ANALYZE. |
Nested Loop with a big outer side |
Often a missing index on the join column |
Sort with high cost |
An index matching your ORDER BY would eliminate it |
🚨 The estimate-vs-actual mismatch is the single most valuable thing to check. The planner makes decisions from statistics; if the statistics are stale, it picks a plan that made sense for last month’s data. This is the classic cause of “the query was fast yesterday and is slow today with no code change.”
-- PostgreSQL: which queries are slowest overall?
SELECT query, calls, mean_exec_time, total_exec_time
FROM pg_stat_statements ORDER BY total_exec_time DESC LIMIT 20;
-- Which tables are getting sequential scans?
SELECT relname, seq_scan, seq_tup_read, idx_scan
FROM pg_stat_user_tables WHERE seq_scan > 0 ORDER BY seq_tup_read DESC;
-- Which indexes are never used? (drop these — they're pure write cost)
SELECT relname, indexrelname, idx_scan
FROM pg_stat_user_indexes WHERE idx_scan = 0;
🚨 Sort by total time, not mean. A query taking 5 ms called a million times costs far more than a 2-second query called twice — and it’s the one worth fixing.
That last query is worth running on any real system. Unused indexes are common, and every one is pure write overhead with zero benefit.
The concept doesn’t disappear.
🚨 The Cassandra point is a good interview detail: in wide-column stores you don’t add an index, you denormalize into another table. That’s the trade-off of “design around access patterns.”
| Decision | Gain | Cost |
|---|---|---|
| Add an index | Orders of magnitude faster reads | Slower writes, more storage, more memory pressure |
| Composite index | Serves several query shapes; enables covering | Only works left-to-right; column order matters a lot |
| Covering index | Index-only scans, no table access | Larger index; more write cost |
| Partial index | Tiny and fast for a filtered subset | Only helps queries with the matching predicate |
| Many indexes | Every query is fast | Writes slow down proportionally; buffer pool thrashes |
| No indexes | Fastest writes | Reads become table scans |
pg_stat_statements and the query
plans. A missing index on a foreign key is close to a universal experience.1. See the difference. Load a million rows into Postgres and measure:
CREATE TABLE users (id BIGSERIAL PRIMARY KEY, email TEXT, city TEXT, created_at TIMESTAMPTZ);
INSERT INTO users (email, city, created_at)
SELECT 'user' || i || '@example.com',
(ARRAY['Lahore','Karachi','Dubai','Berlin'])[1 + i % 4],
now() - (i || ' minutes')::interval
FROM generate_series(1, 1000000) i;
EXPLAIN ANALYZE SELECT * FROM users WHERE email = 'user500000@example.com';
-- Seq Scan, ~200 ms
CREATE INDEX idx_email ON users (email);
EXPLAIN ANALYZE SELECT * FROM users WHERE email = 'user500000@example.com';
-- Index Scan, ~0.1 ms
2. Prove the leftmost-prefix rule.
CREATE INDEX idx_city_created ON users (city, created_at);
EXPLAIN SELECT * FROM users WHERE city = 'Lahore'; -- uses it
EXPLAIN SELECT * FROM users WHERE created_at > now() - interval '1 day'; -- does NOT
3. Measure the write cost. Time inserting 100,000 rows into the table with 0 indexes, then 1, then 5. Plot it. That curve is why “index everything” is wrong.
4. Break an index with a function.
EXPLAIN SELECT * FROM users WHERE LOWER(email) = 'user1@example.com'; -- Seq Scan!
CREATE INDEX idx_email_lower ON users (LOWER(email)); -- now it works
WHERE DATE(created_at) = '2026-07-22' not use an index on created_at?