Cruxly › System design › Foundations of Data Systems
How Indexes Actually Work
the data structure decides what your database is fast at
Open the interactive lesson"Add an index" is not one action — a B-tree index and an LSM-tree index solve different problems, and picking blind means picking wrong for either your read pattern or your write pattern. For storage engines in depth, see "Storage engines: B-trees, LSM-trees, row vs column" in the topic Databases: Choosing One.
What a B-tree actually looks like, and why it costs what it costs
A B-tree keeps sorted keys in a wide, shallow tree of fixed-size pages (8KB in Postgres, 16KB in InnoDB). Each internal node holds many keys and pointers to child pages — "wide" means a tree over a billion rows is still only 3-4 levels deep, so a point lookup or range scan touches a small, bounded number of pages regardless of table size.
Every write is in-place. Inserting a row means finding its correct sorted position and writing it there — which, on a full page, forces a page split: the page divides in two, and the split can cascade up the tree if the parent page is also full.
This in-place, sorted-order write is exactly why B-trees are read-optimised: a lookup or range scan is fast because everything is already where a sorted search expects it, but every write does random I/O to whatever page the key sorts into, which could be anywhere on disk.
This is the mechanism behind "why do range queries need an index on the range column specifically." WHERE created_at BETWEEN ... on an unindexed column means the rows matching that range are scattered across every page in the table in storage order, not sorted-by-date order — the database has no way to jump directly to the start of the range and walk sequentially, so it falls back to scanning everything.
LSM-trees: trading read cost for write throughput
A log-structured merge-tree takes the opposite trade. Writes never touch data in place — they append to an in-memory table (a memtable, usually a sorted structure) and a durable write-ahead log. When the memtable fills, it flushes to disk as an immutable, sorted file (an SSTable). Over time, many small SSTables accumulate and get merged (compaction) into fewer, larger ones.
A single write is now a sequential append, orders of magnitude cheaper than the B-tree's random-access page write — this is the entire reason write-heavy systems (Cassandra, RocksDB, most time-series databases) default to LSM-trees.
The cost lands on reads. A key might exist in the memtable, or in any of several SSTables (the newest write wins if it appears in more than one, since older ones haven't been compacted away yet) — so a read may need to check multiple structures. Two standard mitigations: a Bloom filter per SSTable (the same probabilistic-set structure used for URL dedup in the web crawler exercise elsewhere in this track) to skip SSTables that provably don't contain the key, and compaction itself, which reduces how many SSTables a read has to consult by merging them down over time.
Compaction is not free housekeeping — it competes with live traffic for I/O and CPU. A compaction storm during peak load is a real, named operational failure mode, and "compaction is running" is a legitimate answer to "why did p99 latency spike" on an LSM-backed store.
Choosing between them, and the follow-up questions this invites
The one-sentence test: is the workload read-heavy with point lookups and range scans (B-tree), or write-heavy with occasional reads (LSM-tree)? Most relational databases (Postgres, MySQL's InnoDB) default to B-trees. Most wide-column and embedded key-value stores (Cassandra, RocksDB, LevelDB) default to LSM-trees. Knowing which family a named product uses, and why that follows from its target workload, is a stronger answer than knowing the product names alone.
Secondary indexes cost a write, always, on either structure. An index on a non-primary-key column is a second data structure that must stay in sync with the table — every insert or update to an indexed column means writing to the base table's structure and the index's. This is why "just add an index" is not free: each additional index adds write amplification, and a table with ten indexes pays that cost ten times per write, on top of whatever throughput was already spent on the base table.
Covering indexes trade index size for avoiding a second lookup. If an index includes every column a query needs (not just the column it's sorted by), the query never has to jump from the index back to the base table to fetch additional columns — this is the mechanism behind "why did adding extra columns to my index make this query faster," and it is a genuine, specific technique worth naming rather than a vague "indexes make things faster."
How to say it in the interview
"The question I actually answer before choosing an index structure is whether the workload is read-heavy with point lookups and range scans, or write-heavy with a stream of inserts — because B-trees and LSM-trees are optimised for opposite ends of that spectrum, and most databases only give you one of them."
Checklist
- Chose B-tree versus LSM-tree from the read/write balance of the workload, not by habit
- Explained why a B-tree stays shallow regardless of table size
- Named page splits as the cost of a B-tree's in-place, sorted writes
- Explained why an LSM-tree write is a cheap sequential append instead of a random write
- Named the read-side cost an LSM-tree defers: checking multiple SSTables per lookup
- Identified compaction as a real operational cost competing with live traffic
- Stated that every secondary index adds write cost, always
- Used a covering index to avoid a second lookup back to the base table