Database indexing: B-trees, LSM trees and secondary indexes
How database indexes work, B-tree versus LSM-tree storage engines, composite and covering indexes, secondary indexes on sharded data, and the trade-offs between read speed, write speed and space.
Reading is half of it. See this used in a real interview: walk through Design a Distributed Key-Value Store →
An index is a second copy of some of your data, sorted so a lookup does not have to scan everything. Every index makes some reads fast and every write slower, and the storage engine underneath decides how expensive that trade is. Interviewers ask about indexes when they want to see whether "use Postgres" or "use Cassandra" is a reasoned choice or a habit.
What an index buys
Without an index, finding WHERE email = 'a@b.com' in 100 M rows means reading all of them. With a B-tree index on email, it is about four page reads: the tree is only a few levels deep because each page holds hundreds of keys. That is the difference between seconds and a millisecond.
The cost: every insert, update or delete must also update every index on the table, and each index takes space. Five indexes on a write-heavy table can make writes several times slower than with one.
B-trees
A B-tree (in practice a B+tree) is a balanced tree of fixed-size pages, typically 8 or 16 KB. Internal pages hold keys and pointers; leaf pages hold the keys in order, linked to their neighbours. A lookup walks from the root to a leaf in O(log n) page reads, and a range scan walks along the leaves.
Writes update pages in place: find the leaf, change it, and split it if full. Each write may touch random pages on disk, and every change is also written to a write-ahead log for crash safety. This is the engine of Postgres, MySQL (InnoDB), SQL Server and most relational databases.
Good at: point reads, range scans, predictable read latency. Weaker at: very high write rates, because random page writes and page splits cost I/O.
LSM trees
A log-structured merge tree never updates in place. Writes go to a commit log (sequential) and an in-memory sorted table (the memtable). When the memtable fills, it is written to disk as an immutable sorted file (an SSTable). Background compaction merges files, keeps the newest version of each key and drops deleted ones.
Reads check the memtable, then the files from newest to oldest. A Bloom filter per file answers "definitely not here" for most of them (see probabilistic data structures), so a typical read touches one file.
This is the engine of Cassandra, RocksDB, LevelDB, ScyllaDB, HBase and many time-series stores.
Good at: very high write throughput (everything is sequential), compression, and gentle wear on SSDs. Weaker at: read latency when compaction falls behind, and amplification: data is rewritten several times as it is compacted.
The three amplifications
| B-tree | LSM tree | |
|---|---|---|
| Write amplification (bytes written per byte stored) | moderate: whole pages rewritten for small changes | higher in total, but sequential; depends on compaction strategy |
| Read amplification (places checked per read) | low: one path down the tree | higher: memtable plus files, reduced by Bloom filters |
| Space amplification (disk used per byte of data) | some fragmentation from half-full pages | old versions until compaction runs |
The interview-level summary: B-trees favour reads and predictability, LSM trees favour writes. Pick by the read/write ratio and the latency target. A 70 %-write metrics store wants LSM; a read-heavy product catalogue is happy on B-trees.
Index types worth naming
- Primary key (clustered) index. In InnoDB, the table itself is a B-tree ordered by the primary key, so rows with neighbouring keys are stored together. Random primary keys (UUIDv4) scatter inserts across the whole tree; time-ordered keys append at the end. See unique ids.
- Secondary index. A separate structure from the indexed column to the primary key. A lookup is an index read plus a fetch of the row.
- Composite index on
(a, b, c). Usable for queries filtering ona, ona and b, or on all three, in that order (the leftmost prefix rule). It does not help a query onbalone. Put equality columns first and the range or sort column last:(user_id, created_at)serves "this user's newest items" perfectly. - Covering index. Contains every column the query needs, so the database never reads the row.
CREATE INDEX ON orders (user_id, created_at) INCLUDE (status, total)turns a list page into an index-only scan. - Partial index on a subset of rows:
WHERE status = 'pending'indexes only the few rows a job queue polls. - Hash index. Equality only, no ranges; mostly in memory stores.
- Inverted index. Word to list of documents, for full-text search; see search and indexing.
- Spatial index (R-tree, geohash, S2); see geospatial indexing.
Secondary indexes on sharded data
Once data is sharded by one key, querying by another is the hard part. Two choices:
- Local indexes: each shard indexes its own rows. Writes stay on one shard, but a query by the secondary key must ask every shard (scatter-gather).
- Global indexes: the index itself is partitioned by the secondary key. Queries hit one index shard, but each write now updates two shards, usually asynchronously, so the index can lag.
DynamoDB offers both (local and global secondary indexes); Cassandra's built-in secondary indexes are local and are best avoided for high-cardinality columns. Often the better answer is a second table keyed by the other access pattern, written alongside the first, which is what data modelling for reads means in practice.
When an index does not help
- Low-selectivity columns. An index on a boolean that is true for half the rows is slower than a scan.
- Functions on the column.
WHERE lower(email) = …cannot use an index onemail; index the expression instead. - Leading wildcards.
LIKE '%term'cannot use a B-tree; use a trigram or inverted index. - Too many indexes. Each one is a write tax. Audit unused indexes regularly.
In the interview
When you name a table, name its key and its one or two indexes, tied to the queries: "Orders keyed by order id, with an index on (customer_id, created_at) for the order history page." When the write rate is high, say whether the store is B-tree or LSM and why. When data is sharded, say how queries by a second key are served.
Checklist
- Primary key choice and whether it is time-ordered.
- One index per real query pattern, composite in the right column order.
- Covering indexes for hot list pages.
- B-tree or LSM, chosen from the read/write mix.
- Secondary access patterns on sharded data: local index, global index, or a second table.
- What each extra index costs on writes.