Understanding the LSM tree

Start with the write path

An LSM tree makes a practical trade: buffer writes in memory, then flush sorted data to disk. The foreground write path becomes simpler, while background work becomes more important.

这篇示例笔记从写入路径出发：先理解数据如何落盘，再理解读取和压缩为什么会带来额外成本。

1. Append the update to a write-ahead log.
2. Insert it into the mutable memtable.
3. Flush an immutable memtable into a sorted table.

A small mental model

use std::collections::BTreeMap;

fn main() {
    let mut memtable = BTreeMap::new();
    memtable.insert("garden", "growing");
    println!("{:?}", memtable.get("garden"));
}

This is only an in-memory sketch. It does not implement durability, deletion, or concurrent access.

The trade-offs

Concern	Where the cost appears
Write amplification	Rewriting data during compaction
Read amplification	Checking several sorted runs
Space amplification	Retaining overlapping versions

The right balance depends on the workload. RocksDB is a useful place to explore how compaction policy affects that balance.

A fast foreground write is not the same thing as a cheap write overall.

Questions to keep open

• Trace the basic write path
• Compare leveled and universal compaction on a real workload
• Connect local durability to replication with Raft

The broader series is a set of small models, not a production storage engine.¹

Footnotes

1. Measure real workloads before choosing a compaction strategy. ↩