Storage Engines & Indexing

Why This Matters

Under "which database?" ([[SQL vs NoSQL]]) sits a deeper question senior interviewers push into: how does it store bytes on disk, and why is it fast for your access pattern? The answer is the storage engine — and it comes down to two families, B-trees (read-optimized, in-place) and LSM-trees (write-optimized, append + compact). This is the engine behind [[Distributed Key-Value Store]]'s single-node layer and the reason Postgres and Cassandra feel different.

The Problem an Index Solves

Without an index, a lookup is a full table scan — O(n), read every row. An index is a separate sorted/hashed structure mapping key → row location, turning O(n) into O(log n) or O(1). The cost: every index makes writes slower (each write must update every index) and uses more space. So indexing is the fundamental read-vs-write trade-off, made physical.

Interview one-liner: "An index trades write throughput and storage for read speed. You add one when reads on that column dominate — not by default on every column."

Family 1: Hash Index (the simplest)

Keep an in-memory hash map: key → byte offset in an append-only data file (Bitcask/Riak model).

• Write: append value to file, update hash map. Fast — sequential write.
• Read: hash map → offset → one disk seek. Fast.
• Fatal limits: all keys must fit in RAM; range queries impossible (hashing destroys order). Fine for a pure point-lookup KV store, useless for WHERE age BETWEEN.

Family 2: B-Tree (read-optimized, the RDBMS default)

Balanced tree of fixed-size pages (~4–16 KB), kept sorted by key. Postgres, MySQL/InnoDB, Oracle, and most relational engines.

• Structure: root → internal pages → leaf pages; each page holds keys + pointers to child pages. Depth ~3–4 covers billions of rows → a lookup is ~3–4 page reads.
• Read: O(log n), and range scans are cheap (leaves are sorted, often linked).
• Write: find the leaf, modify in place. If a page is full, split it. Writes are random I/O (seek to the page), and durability needs a WAL (write-ahead log) so a crash mid-split doesn't corrupt the tree — see [[ACID & Database Transactions]].
• Trade-off: great reads + range queries; writes do random I/O and cause write amplification (rewrite a whole page for a small change, plus the WAL entry).

Family 3: LSM-Tree (write-optimized)

Log-Structured Merge tree. Cassandra, RocksDB, LevelDB, ScyllaDB, HBase — the column-family / write-heavy world.

Write path:
  1. Append to WAL (durability)
  2. Insert into memtable (in-memory sorted structure, e.g. red-black tree / skiplist)
  3. When memtable is full → flush to disk as an immutable SSTable (Sorted String Table)

Read path:
  memtable → newest SSTable → ... → oldest SSTable   (stop at first hit)

Background: compaction merges SSTables, drops overwritten/deleted keys

• Write: everything is sequential (append to WAL + in-memory insert) → far higher write throughput than a B-tree's random-page writes. That's the whole point.
• Read: potentially slower — a key might be in the memtable or any SSTable, so a read may check several. Mitigated by:
  • Bloom filters per SSTable — a probabilistic "is this key definitely not here?" so reads skip SSTables that can't contain the key, avoiding useless disk seeks. (No false negatives; small false-positive rate.)
  • Sparse index + sorted SSTables → binary-search within a file.
• Deletes don't remove data immediately — they write a tombstone marker; the space is reclaimed during compaction.
• Trade-off: excellent write throughput + good compression (sorted, immutable files); reads amplified across levels; compaction consumes background CPU/IO and can cause latency spikes.

B-Tree vs LSM-Tree — the Comparison That Wins Points

The senior move: don't say "LSM is better." Say "write-heavy ingest (time-series, event logs, a Cassandra-style feed store) → LSM; read-heavy with range scans and transactions (a relational OLTP workload) → B-tree." Tie it to the access pattern, exactly like [[SQL vs NoSQL]].

Clustered vs Non-Clustered (Secondary) Indexes

• Clustered index — the table rows are physically stored in the index's leaf pages (the primary key IS the data layout). One per table. Lookup by PK = zero extra indirection. (InnoDB primary key.)
• Non-clustered / secondary index — a separate structure whose leaves hold the indexed column + a pointer (PK or row location) back to the row. A lookup does index → then fetch the row (a second hop). Multiple allowed.
• Covering index — if the index already contains every column the query needs, the second hop is skipped entirely (SELECT-covered) — a common query-tuning win.

Interview Drills

1. Cassandra takes writes far faster than Postgres — why, mechanically? — Cassandra is LSM-based: a write is a sequential WAL append + an in-memory memtable insert, no random disk seek. Postgres (B-tree) must locate and modify the actual leaf page in place (random I/O) plus WAL. Sequential beats random, so LSM ingests faster — at the cost of read amplification that Bloom filters partly claw back.
2. What does a Bloom filter do in an LSM engine, and what's its failure mode? — Per-SSTable probabilistic membership check so a read skips files that definitely don't hold the key, avoiding wasted seeks. It can produce false positives (says "maybe present" when absent → one wasted lookup) but never false negatives, so correctness is preserved.
3. You add a secondary index to speed up a query and writes get slower. Why, and when is it still worth it? — Every write must now also update that index structure (extra I/O). Worth it when the read pattern it accelerates dominates the workload; not worth it on a write-heavy column queried rarely.
4. Why can't a hash index answer WHERE created_at BETWEEN x AND y? — Hashing scatters keys with no order, so adjacent timestamps land in unrelated buckets; there's no way to scan a contiguous range. You need an order-preserving structure (B-tree, or sorted SSTables).

Cross-links

[[SQL vs NoSQL]] · [[ACID & Database Transactions]] · [[Bloom Filters]] · [[Database Replication & Sharding]] · [[Distributed Key-Value Store]] · [[Merkle Trees]] · [[Caching & Redis]]