Back to System design
Database Indexing: B-Tree vs LSM, Composite, Covering
mediumIndexing questions look like trivia and are really about read/write trade-offs. The candidates who do well explain why an index helps this query, and what it costs on every write.
ScaleB-tree O(log N) lookup; LSM amortized O(log N) reads, O(1) writes
StorageIndex 10-30% of table; LSM may temporarily double during compaction
Key Concepts
1
B-trees are read-optimised and update in place. Balanced, sorted, typically three or four levels deep
for a large table, so a lookup is a handful of page reads and a range scan walks the leaves. Because updates
modify pages where they sit, writes are random I/O — fine on SSD, historically painful on disk, and the
reason page splits and fragmentation matter.
B-trees are read-optimised and update in place.
2
LSM-trees are write-optimised and never update in place. Writes land in an in-memory table plus a
write-ahead log, are flushed as immutable sorted files, and are merged by background compaction. Every
write is sequential. The cost is read amplification: a key may live in any of several files, so reads check
a Bloom filter per file to avoid pointless disk reads, and compaction consumes I/O in the background
forever. This is the engine behind Cassandra, RocksDB and LevelDB, and it is chosen when writes dominate.
LSM-trees are write-optimised and never update in place.
3
Composite index order is the thing candidates most often get wrong. An index on
(a, b, c) can serve
queries filtering on a, on a, b, or on a, b, c — the leftmost prefix. It cannot serve a query
filtering only on b. So the column order should follow the queries, with equality predicates before range
predicates: for WHERE status = ? AND created_at > ?, the index wants (status, created_at), because a
range on the first column stops the second from narrowing anything.Composite index order is the thing candidates most often get wrong.(a, b, c)aa, ba, b, c
4
A covering index removes the table from the query entirely. If every column the query needs is in the
index, the engine answers from the index alone — an index-only scan — skipping the row lookups that usually
dominate. This is the single biggest win available on a hot read path, and it costs write throughput and
disk, because the index now carries the data too.
A covering index removes the table from the query entirely.
5
Selectivity decides whether an index is used at all. An index on a boolean column matching half the
table is worse than a sequential scan, and the planner knows it, which is why "I added an index and nothing
changed" usually means low cardinality, a function applied to the column (
WHERE lower(email) = ? cannot
use a plain index on email), or a type mismatch forcing a cast.Selectivity decides whether an index is used at all.WHERE lower(email) = ?email
6
Every index is a tax on writes. An insert into a table with six indexes is seven structures updated.
Unused indexes are pure cost, and production databases expose usage statistics precisely so you can find
and drop them.
Every index is a tax on writes.
7
What the interviewer is probing.
What the interviewer is probing.
8
1. "This query is slow. What do you do?" Probing: method, not guesses. Stalls: "Add an index."
Moves up: read the execution plan first, find where rows are being read and discarded, then index for
that predicate — and check the index is actually used afterwards.
1. "This query is slow. What do you do?"
9
2. "Index on (a, b) — does it help
WHERE b = ?" Probing: leftmost prefix. Stalls: "Yes."
Moves up: no; it serves a, or a and b. A query on b alone needs its own index.2. "Index on (a, b) — does it help `WHERE b = ?`"WHERE b = ?ab
10
3. "B-tree or LSM?" Probing: matching the engine to the workload. Stalls: naming one as faster.
Moves up: reads and updates in place versus sequential writes with compaction; write-heavy ingest picks
LSM, read-heavy transactional work picks B-tree.
3. "B-tree or LSM?"
11
4. "What is a covering index?" Probing: whether you know the biggest available win. Stalls: "An
index with many columns." Moves up: one containing every column the query touches, so the engine never
reads the table — with the write and storage cost named.
4. "What is a covering index?"
12
5. "You added an index and it is not used." Probing: diagnosis. Stalls: "The planner is wrong."
Moves up: low selectivity, a function or cast on the column, stale statistics, or a query shape that
cannot use the prefix.
5. "You added an index and it is not used."
Components
- Query planner / cost estimator (uses table statistics).
- ANALYZE / table statistics refresh.
- WAL / binlog for durable updates.
- Compaction (LSM) — leveled, size-tiered, universal.
- Bloom filters (LSM) — skip SSTables for absent keys.
- Index-only scans / covering indexes.
- Online index creation (CREATE INDEX CONCURRENTLY in Postgres).
B-tree vs LSM
B-tree LSM-tree
----------------------------------------------------------------
Write path modify page in place append to memtable
(random I/O) + WAL, flush later
(sequential I/O)
Read path ~3-4 page reads check memtable, then
N sorted files
(Bloom filters cut
the misses)
Write amplification moderate (page high (compaction
rewrites, splits) rewrites data
repeatedly)
Read amplification low higher, bounded by
compaction strategy
Space amplification fragmentation obsolete versions
until compaction
Range scans excellent (leaf good (merge across
traversal) sorted files)
Background work vacuum / rebuild continuous
compaction
Used by PostgreSQL, MySQL Cassandra, RocksDB,
InnoDB, most OLTP LevelDB, ScyllaDB Choosing
Write-heavy ingest, time series, event logs -> LSM
Transactional reads and updates, ad-hoc queries -> B-tree
And note the compaction tax: an LSM store under
sustained write load spends real I/O rewriting data,
which shows up as latency spikes if it is not tuned.Composite and covering, worked
Table: orders(id, customer_id, status, created_at, total, ...)
Query: SELECT id, total FROM orders
WHERE customer_id = ? AND status = 'shipped'
ORDER BY created_at DESC LIMIT 20; No index
Sequential scan of 50,000,000 rows ~seconds Index on (customer_id)
Rows for one customer ~200
Then filter status + sort in memory
Work: 200 index entries + 200 row lookups ~milliseconds Index on (customer_id, status, created_at DESC)
Equality, equality, then ordered range
-> the engine walks straight to the matching range in
created_at order and stops after 20 rows.
Work: ~20 index entries + 20 row lookups Covering: (customer_id, status, created_at DESC) INCLUDE (id, total)
Every column the query needs is in the index.
Work: ~20 index entries, ZERO row lookups
-> index-only scan; typically 2-5x faster again on a hot path. Column order rule
Equality predicates first, range/sort last. Putting
created_at first would force a scan of every recent order
regardless of customer.Why an index is ignored
Low selectivity
WHERE is_active = true matching 80% of rows.
A scan is cheaper than index + row lookups, and the planner
knows it. Partial index is the fix:
CREATE INDEX ... ON t (created_at) WHERE is_active = false; Function or cast on the column
WHERE lower(email) = 'a@b.com' -- plain index on email unused
Fix: expression index on lower(email), or normalise on write.
WHERE user_id = '123' -- text compared to bigint
Fix: correct the parameter type; a cast can disable the index. Leading column missing
Index (a, b); query filters only on b. Unusable as a prefix. Stale statistics
The planner estimates row counts from samples. After a bulk
load, run ANALYZE or the estimates -- and the plan -- are wrong. Too many indexes (the opposite problem)
Every write updates every index:
6 indexes -> 7 structures written per insert
Find unused ones: pg_stat_user_indexes.idx_scan = 0 over a
representative period, then drop them. Unused indexes cost
write throughput, disk and backup time, and buy nothing.