System Design · Core

Storage Engines

How databases actually store bytes: B-trees vs LSM-trees, WAL, SSTables, compaction, and which engine fits which workload.

1. Why interviewers ask this

“Why is Cassandra write-heavy friendly?” and “Why do updates hurt InnoDB?” both bottom out in storage engine design. You do not need to implement RocksDB, but you must compare read/write amplification and latency shapes.

2. Write-Ahead Log (WAL)

Client write | v Append to WAL (sequential disk) --durable point-- | v Update in-memory structure (page cache / memtable) | v Later: flush pages / SSTables to disk

Durability comes from the sequential WAL append, not from immediately rewriting a random tree page. On crash, replay WAL to rebuild memory. Group commit batches many transactions into one fsync for throughput.

3. B-tree engines (classic OLTP)

Used by InnoDB (MySQL), Postgres heap+B-tree indexes, many relational stores. Data (or index) lives in fixed-size pages in a balanced tree.

[ root ] / \ [ internal ] [ internal ] / \ / \ [leaf] [leaf] [leaf] [leaf] <-- sorted keys + pointers/rows

Point lookup: O(log N) page reads; excellent with cache.
Range scan: walk sibling leaves — great for ORDER BY / BETWEEN.
Write: find leaf, maybe split page → random I/O + write amplification.
Update in place: modify page; WAL still records change.

Strength: predictable reads, rich indexes, mature MVCC. Weakness: random writes under heavy update/insert churn; page splits and fragmentation.

4. LSM-tree engines (write-optimized)

Log-Structured Merge trees (LevelDB, RocksDB, Cassandra, Scylla, some HBase paths). Writes go to an in-memory memtable; when full, flush to an immutable sorted file on disk (SSTable).

Writes --> Memtable (RAM) | flush v SSTable L0 \ SSTable L0 +-- compaction --> fewer, larger SSTables at lower levels SSTable L1 / ... Reads --> check memtable, then bloom filters + SSTables (newest first)

SSTables

Sorted String Tables: immutable files of sorted key-value pairs plus indexes. Immutability makes concurrency simple and turns random writes into sequential flushes.

Compaction

Background process merges overlapping SSTables, drops tombstones (deletes), and keeps levels organized. Without compaction, reads slow down and disk fills. Compaction burns CPU and disk bandwidth — a major ops concern.

Tombstone: delete key K → write marker; older values removed on compact Space amp: old versions live until compaction finishes Read amp: may touch several SSTables per get (blooms help) Write amp: same key rewritten across compaction levels

5. Head-to-head

	B-tree	LSM
Write pattern	In-place page updates (random-ish)	Sequential flush + compaction
Read pattern	Stable, few I/Os if cached	May merge several files; blooms help
Range scans	Excellent	Good if compacted; can be costly
Space	Page fill factor / fragmentation	Temporary space amplification
Sweet spot	OLTP, mixed read/write, strong indexes	High ingest, write-heavy, time-series-ish

6. Primary vs secondary indexes

Primary index: organizes the main row storage (or clustered index). Lookup by PK is the fast path.
Secondary index: extra structure mapping non-PK fields → row pointers/PKs. Speeds filters; costs write amplification on every insert/update.
In LSM/NoSQL, secondary indexes are often local per partition — global secondary indexes need careful design (eventual consistency, extra fan-out).

Write cost ≈ base row write + update each secondary index touched Read by non-PK without index → full scan (avoid on hot paths)

7. Column stores (analytics)

Columnar engines (Parquet/ORC files, ClickHouse, BigQuery, Redshift) store values of each column together. Scans that touch few columns read far less data; compression is excellent. Poor fit for point updates and high-QPS OLTP — use for analytics / OLAP, not checkout paths.

8. In-memory databases

Redis-style stores keep the working set in RAM for microsecond–sub-ms ops. Durability is optional: AOF/RDB snapshots, or treat as pure cache. Interview line: “in-memory for speed; if it is source of truth, enable persistence + replication and accept fsync trade-offs.”

9. Engine type summary

Engine type	Sweet spot	Avoid for
B-tree row store	OLTP, transactions, point/range	Extreme write ingest
LSM	Write-heavy KV, time-series-ish	Heavy update-in-place + complex joins
Columnar	Analytics, wide scans, BI	Single-row OLTP updates
In-memory	Ultra-low latency, sessions, hot state	Huge cold datasets without tiering

10. When each fits (interview answers)

Payments / inventory OLTP: B-tree SQL (Postgres/InnoDB) — transactions + point/range lookups.
Metrics ingest, write-heavy KV: LSM (Cassandra/RocksDB) — absorb writes, tune compaction.
Full-text search: inverted indexes (Lucene) — different structure; mention separately.
Analytics warehouse: columnar formats (Parquet/ClickHouse) — not row B-tree/LSM.
Session / leaderboard: in-memory (Redis) with durability story if needed.

11. Practical knobs to name

Buffer pool / page cache size (B-tree).
Memtable size, level count, compaction strategy (size-tiered vs leveled).
Bloom filters to skip SSTables on point gets.
fsync / group commit policy for durability vs latency.

12. One-liner summary

B-trees optimize for balanced reads and in-place updates; LSMs optimize for sequential writes and pay later with compaction and read/space amplification. Columnar wins analytics; in-memory wins latency.

Quick revision

WAL makes writes durable via sequential append + crash replay.
B-tree: page-oriented, great point/range reads, costlier random writes.
LSM: memtable → SSTable flushes; immutable files + compaction.
Primary vs secondary indexes: secondary speeds filters, costs writes.
Columnar for OLAP; in-memory (Redis-style) for ultra-low latency.
OLTP → B-tree SQL; heavy ingest KV → LSM.
Bloom filters cut LSM point-lookup I/O.