Database Internals & Storage Engines — What Actually Happens to a Read/Write on DiskB-tree vs LSM, WAL & Crash Recovery, MVCC, Query Optimizer

Problem Scenario + Constraints

You're choosing the storage engine under a transactional/ledger system: order-table write peak 100K QPS, point lookups (by order id) 50K QPS, a single table growing past 10 TB, and after a crash you must recover with zero data loss (RPO=0), while heavy concurrent reads and writes must not block each other. The real question isn't "MySQL or Postgres" — it's: how do these engines guarantee that one UPDATE is fast, durable, and simultaneously readable as a consistent snapshot by another transaction?

Answering that means opening the database black box and seeing four things clearly: how data is laid out on disk (B-tree vs LSM), how nothing is lost on crash (WAL), how concurrent reads/writes avoid fighting (MVCC), and how one SQL statement becomes an optimal on-disk access path (the optimizer). This is also the dividing line between building storage-intensive systems and merely using them.

High-Level Architecture (Storage Engine Cross-Section)

graph TD
    SQL["SQL query"] --> PARSE["Parser + Planner
cost-based optimizer"]
    PARSE --> EXEC["Executor
Access Method API"]
    EXEC --> AM{"Storage engine"}
    AM -->|read-heavy| BT["B+Tree
InnoDB / Postgres"]
    AM -->|write-heavy| LSM["LSM-Tree
RocksDB / Cassandra"]

    BT --> BP["Buffer Pool
page cache · dirty pages"]
    LSM --> MEM["MemTable
in-memory sorted table"]

    WRITE["write path"] -.first write.-> WAL[("WAL / redo log
sequential append")]
    BP -->|checkpoint flushes dirty| DISK[("data files
heap / SSTable")]
    MEM -->|flush + compaction| DISK
    WAL -.crash recovery redo/undo.-> BP

    classDef q fill:#1a2530,stroke:#64c8ff,color:#e8eef5
    classDef eng fill:#1a1a30,stroke:#ffb450,color:#e8eef5
    classDef dur fill:#2a1530,stroke:#ff7ab6,color:#e8eef5
    class SQL,PARSE,EXEC q
    class BT,LSM,BP,MEM eng
    class WAL,DISK dur

The core invariant: before any data lands, write the WAL first (sequential IO); the data structure itself dictates the read/write/space amplification trade-off

Key Technical Points

1. B-tree vs LSM-tree — you can't have low read AND write amplification

Principle: on disk (HDD and even SSD) sequential writes far outrun random writes. A B+Tree organizes data in place into sorted pages: lookups are O(log n) and a point query reads one leaf page — read-friendly; but updating a row means reading its page in, modifying, and writing it back — a random write, and changing a few bytes still flushes a whole page (write amplification). An LSM-Tree flips this: writes only append to an in-memory MemTable, which when full is flushed sequentially into immutable SSTables, later merged by background compaction — turning random writes into sequential ones, giving huge write throughput; the cost is that a key may be scattered across multiple SSTable levels, so a point query probes several levels (read amplification), mitigated by Bloom Filters.

# LSM point read: newest to oldest levels, Bloom Filter skips absent levels
def lsm_get(key):
    if v := memtable.get(key):           # (1) memory, newest
        return None if v is TOMBSTONE else v
    for sst in sstables_newest_to_oldest():   # (2) L0->Ln, level by level
        if not sst.bloom.might_contain(key):  # ~1% false positive rate
            continue                          # most levels skipped
        if v := sst.get(key):                 # hit (delete = tombstone)
            return None if v is TOMBSTONE else v
    return None
# write: append only; delete also "writes a tombstone", real reclaim at compaction

2. WAL & Crash Recovery — log first, only then touch data

Principle: a data page is modified in the in-memory buffer pool into a "dirty page"; if the machine crashes before that dirty page reaches disk, the change is lost. The iron rule of WAL (Write-Ahead Logging): the redo log for any page modification must be sequentially written and fsync'd to disk before the dirty page is allowed to flush. Then, after a crash, replaying the WAL rebuilds the lost in-memory changes. Sequential WAL writes also amortize "many random writes" into "one sequential write + async dirty flush", which actually speeds things up. The industry standard is ARIES: three-phase recovery — Analysis (find dirty pages and active transactions at crash time), Redo (replay to the exact crash-instant state, including uncommitted transactions), Undo (roll back uncommitted transactions) — with LSN, checkpoints, and CLRs making it idempotent and restartable.

# WAL ordering at commit (simplified)
def commit(txn):
    lsn = wal.append(txn.redo_records)   # (1) append redo sequentially (incl. undo info)
    wal.fsync_up_to(lsn)                 # (2) force to disk -- only after this is it "committed"
    mark_committed(txn)                  # (3) only now reply OK to the client
    # dirty pages flushed later by checkpoint; a crash is repaired by redo replay

3. MVCC — reads don't block writes, writes don't block reads

Principle: if reads and writes mutually exclude via locks, one long-running read blocks all writes. MVCC (Multi-Version Concurrency Control) makes each update not overwrite the old row but produce a new version, each row tagged with the creating/deleting transaction timestamps (xmin/xmax). A transaction takes a snapshot at start and, when reading, only sees versions "visible to me" — so reads never take locks, see a consistent snapshot, and writes never wait on reads. This is the basis of REPEATABLE READ / Snapshot Isolation. The cost is that old versions pile up and must be reclaimed: Postgres uses VACUUM to clean dead tuples, InnoDB uses a purge thread to clean undo.

# Visibility check (Postgres-style, simplified)
def visible(tuple, snapshot):
    # the tx that created this version committed, and before my snapshot
    if not committed_before(tuple.xmin, snapshot):
        return False
    # this version isn't deleted, or the deleting tx is invisible to me
    if tuple.xmax and committed_before(tuple.xmax, snapshot):
        return False
    return True
# a read just scans the version chain and picks the "visible" one -- no locks

4. Index Internals & Query Optimizer — a SQL's optimal on-disk path

Principle: the same SELECT ... WHERE a=? AND b>? can execute several ways: full scan, use a's index then filter, or use composite index (a,b) to locate directly. A cost-based optimizer (CBO) uses statistics (histograms, distinct counts, row counts) to estimate how many pages each plan reads and how big the result is, and picks the cheapest. The index itself is a B+Tree: a clustered index leaf stores the whole row, a secondary index leaf stores the PK (needs a back-lookup), and a covering index puts all queried columns in the index to skip the back-lookup. Selectivity is key — indexing a low-selectivity column (like gender) can be slower than a scan.

-- Use EXPLAIN to see what the optimizer actually does
EXPLAIN ANALYZE
SELECT order_id, amount FROM orders
WHERE user_id = 42 AND created_at > '2026-01-01';
-- Expect: Index Scan using idx_user_created (user_id, created_at)
-- If you see Seq Scan + Filter -> stale stats or bad selectivity, run ANALYZE orders;
-- Composite index (user_id, created_at): equality user_id first, range column last

Scaling & Optimization

• Writes can't keep up: read-heavy -> stay on B-tree + add read replicas; write-throughput bottleneck -> switch to an LSM engine (MyRocks / TiKV), trading random for sequential writes.
• Single node past 10 TB: shard (see Day 4); each shard is still an independent storage engine, cross-shard queries handled by the layer above.
• Compaction jitter: rate-limit LSM compaction, separate hot/cold tiers, use universal compaction to lower write amp (at the cost of higher space amp).
• VACUUM / purge falling behind: break up long transactions, make autovacuum more aggressive, monitor bloat ratio and undo-chain length.
• WAL is the bottleneck: group commit + a faster WAL disk (dedicated NVMe); cross-region DR via streaming WAL replication (physical replication / CDC).

Common Pitfalls + Interview Follow-ups

Frequent interview follow-ups: (1) "Why are sequential writes faster than random — does it still hold on SSD?" (2) "The WAL holds both redo and undo — what does each do? The ARIES three phases?" (3) "Under MVCC, what happens when two transactions update the same row (write-write conflict / first-committer-wins)?" (4) "Clustered vs secondary index, what's a back-lookup, how does a covering index avoid it?" (5) "What anomalies does Snapshot Isolation prevent, and what does it NOT (write skew)?"

Deep Resources

• Designing Data-Intensive Applications, Ch. 3 (Kleppmann): the best intro to B-tree vs LSM, WAL, and storage engine trade-offs.
• Database Internals (Alex Petrov): a systematic deep dive into B+Tree, LSM, ARIES, and concurrency control.
• Mark Callaghan · Small Datum: the authoritative analysis of "pick 2 of read/write/space amplification".
• RocksDB Wiki: engineering detail on the LSM engine, compaction strategies, and Bloom Filters.
• Uber Engineering: Postgres→MySQL: a real case on MVCC write amplification and index-architecture differences.

Food for Thought (click to expand)