Indexing & Storage Engines | System Design Interview Handbook

🌳

B-Tree Indexes

the default, and why lookups are O(log n)

Without an index, finding a row means scanning the whole table. A B-tree index is a balanced, sorted tree that turns that scan into a walk down a handful of levels. Each node holds many keys and points to children; you descend, narrowing the range at each step, until you land on the row. Because the tree stays balanced and wide, even a billion rows sit only three or four levels deep — that's the O(log n).

  Looking up key = 42:

              [ 30 | 60 ]                 root
             /     |      \
       [10|20]  [40|50]  [70|80]          descend into the 30–60 child
                  │
              → 42 found                  ~3–4 levels even for billions of rows

  Keys are kept SORTED, so range scans are cheap too:
  "everything between 40 and 55" = land on 40, walk right.

Sorted order is the second gift: range queries (BETWEEN, ORDER BY, prefix matches) walk the leaves in order instead of jumping around. The cost lands on writes — every insert, update, and delete must keep the tree sorted and balanced, so each additional index is more work on every write (Tradeoffs).

🪜

LSM Trees

why write-heavy stores are built differently

A B-tree writes in place, which means random disk I/O on every write. An LSM tree (log-structured merge tree) flips this: buffer writes in memory, then flush them to disk in big sequential batches. Sequential I/O is far faster than random, so writes fly. This is why Cassandra, RocksDB, and LevelDB exist (wide-column stores).

  WRITE PATH                             READ PATH
  write ─▶ memtable (in RAM, sorted)     check memtable ─▶ hit? done
             │  when full, flush         miss ─▶ check SSTables newest→oldest
             ▼  (sequential write)                │  a read may touch many files
        SSTable  SSTable  SSTable                 ▼
        (immutable, on disk)              Bloom filter per SSTable says
             │                            "definitely not here" — skip the file,
             ▼  compaction merges         avoid a useless disk read
        fewer, bigger SSTables

The tax is on reads. Since data is spread across many immutable SSTables, a read may check several of them. Two things blunt that: compaction periodically merges SSTables into fewer, larger ones, and a Bloom filter per SSTable answers "is this key definitely not here?" so reads skip files that can't contain the key. Bloom filters can say "maybe present" falsely but never "absent" falsely, which is exactly what you need to avoid pointless disk reads.

⚖️

B-Tree vs LSM

read-optimized vs write-optimized

The choice is a trio of amplifications — the same write shows up as extra I/O, extra reads, or extra space, and you can't minimize all three at once.

	B-tree	LSM tree
Writes	Random I/O, in place — slower	Sequential, buffered — fast
Reads	One path down the tree — predictable	May check several SSTables
Write amplification	Update the page each write	Rewritten repeatedly by compaction
Read amplification	Low	Higher (mitigated by Bloom filters)
Space	Fragmentation, some slack	Better compression; stale copies until compaction
Optimized for	Read-heavy, range queries	Write-heavy ingest
Found in	Postgres, MySQL (InnoDB)	Cassandra, RocksDB, LevelDB

💡

Tie the engine to the workload out loud. "This is write-heavy ingest with mostly key lookups, so an LSM-based store fits — sequential writes, Bloom filters keeping reads cheap. If it were read-heavy with range scans and joins, I'd want a B-tree engine." That one sentence shows you know what's under the database, not just its name.

🧭

Index Strategy

composite, covering, and when the planner ignores you

Beyond single-column indexes, a few patterns solve most real query problems — and a few mistakes make the planner skip your index entirely.

Composite indexes column order matters

An index on (a, b, c) is sorted by a, then b, then c — like a phone book by last then first name. It serves queries on a, a+b, and a+b+c, but not on b alone. Put the column you always filter on first, the range column last.

Covering indexes index-only reads

If the index already contains every column a query needs, the database answers from the index alone and never touches the table. A huge win for hot queries — you're reading one structure instead of two.

⚠️

The planner silently ignores an index when it can't use it: a leading wildcard (LIKE '%term' can't seek a sorted tree), a function on the column (WHERE lower(email)=… unless you indexed that expression), or low selectivity (a boolean flag where a full scan is cheaper than the index round trips). "I added an index" isn't enough — it has to be one the query can actually use.

✍️

The Write Cost of Indexes

every index is a second copy to maintain

An index is not free storage that only helps. It's a separate sorted structure the database must update on every write to the indexed column. Five indexes on a table means one INSERT becomes six writes: the row, plus each index. Indexes speed reads and slow writes, always.

ℹ️

"Index everything" is a write-heavy anti-pattern. On an ingest-heavy table, each extra index drags throughput down measurably. Index the columns your real queries filter and sort on, drop the ones nothing uses, and remember the read/write trade is the same one running through the whole system — you're moving work from read time to write time (Tradeoffs).

📋

Quick Reference

engines and index types on one card

	B-tree	LSM tree
Best at	Reads, range scans	Write-heavy ingest
Writes	Random, in place	Sequential, buffered
Read cost	Low, predictable	Multiple SSTables + Bloom filters
Engines	Postgres, InnoDB	Cassandra, RocksDB

Index type	Speeds up	Costs
Single-column	Lookups and sorts on one field	Write overhead per index
Composite (a,b,c)	Queries on left-prefix of the columns	Useless for non-prefix columns
Covering	Index-only reads, no table hit	Larger index, more write cost
Partial	Queries over a subset of rows	Only helps matching predicates

ℹ️

The one-liners to keep ready. B-tree for read-heavy and ranges; LSM for write-heavy ingest, with Bloom filters and compaction paying down the read tax. Composite index order follows the query's left-to-right filters; covering indexes dodge the table entirely. Every index is a second copy maintained on every write — index what queries use, not everything.