Write-ahead logs, B-trees and LSM-trees

Durability needs a log

A database holds data in memory pages for speed, but memory is lost on a crash. To be durable it must put a record of every change on disk before it tells the client "committed". That record is the write-ahead log (WAL): an append-only file of changes.

100%

Figure SDA-ADS-02-1 · Write-ahead log flow · © forcsguy.com

The same idea appears everywhere: databases, file systems (journaling), message brokers (the log is the data) and replication (followers replay the primary's log).

Two ways to organise data on disk

B-trees: update in place

A B-tree keeps sorted keys in fixed-size pages arranged as a shallow tree. Finding a key takes a few page reads; changing a key updates a page in place (plus a WAL record for safety).

• Strengths: predictable reads, efficient range scans, mature, used by most relational databases.
• Costs: writes touch random pages (random I/O); page splits and fragmentation; every write is written twice (WAL and page).

LSM-trees: append and merge

A log-structured merge tree buffers writes in a sorted in-memory table (the memtable), also logged to a WAL. When full, it is flushed as an immutable sorted file (an SSTable). Background compaction merges files and discards overwritten and deleted values.

100%

Figure SDA-ADS-02-2 · LSM-tree write and read path · © forcsguy.com

• Strengths: very fast sequential writes, good compression, high write throughput.
• Costs: a read may check several files (helped by bloom filters and caches); background compaction creates write amplification and I/O spikes; deletes leave tombstones until compaction.

Choosing

Question	B-tree	LSM-tree
Write-heavy ingestion	Slower	Faster
Point reads and range scans	Steady	Good, depends on compaction
Predictable latency	Easier	Compaction can add tail latency
Space usage	Some fragmentation	Temporary extra during compaction
Typical users	PostgreSQL, MySQL (InnoDB)	Cassandra, RocksDB, HBase, many time-series stores

There is no winner: choose by workload, and measure. This lesson explains why a store behaves the way it does under load, which helps when diagnosing slow writes or sudden I/O spikes.

Related ideas

• Checkpoints and snapshots bound recovery time.
• Replication often ships the WAL to replicas.
• Fsync policy (flush every write, or every few milliseconds) is a durability versus speed knob.
• Bloom filters appear in the probabilistic-structures lesson of the core-concepts course.

Real-world reading