B-Trees and LSM-Trees under the hood

At the bottom of every relational database, key-value store, and search index sits an immutable law of storage hardware: random writes to persistent media are significantly more expensive than sequential writes.

The two dominant storage architectures—B-Trees and Log-Structured Merge-Trees (LSM-Trees)—approach this constraint from opposite philosophical angles, choosing whether to optimize for read amplification or write throughput.

B-Trees: In-place updates and predictable reads

B-Trees (and their modern \(B^+\)-Tree variants used in Postgres, MySQL InnoDB, and SQLite) organise data into fixed-size pages (typically 4KB to 16KB). When you insert or update a row, the database finds the target leaf page and overwrites it in place.

Because internal nodes have wide fan-out (often 100 to 500 child pointers per page), a tree holding hundreds of millions of keys has a depth of only 3 or 4. Point reads require exactly 3–4 page lookups, most of which reside in the operating system page cache.

// Rust: Simplified in-memory SSTable Flush to Disk
use std::fs::File;
use std::io::{BufWriter, Write};

pub struct MemTableEntry {
    pub key: Vec<u8>,
    pub value: Option<Vec<u8>>, // None represents a deletion tombstone
}

pub fn flush_memtable_to_sstable(entries: &[MemTableEntry], path: &str) -> std::io::Result<()> {
    let mut writer = BufWriter::new(File::create(path)?);
    for entry in entries {
        writer.write_all(&(entry.key.len() as u32).to_le_bytes())?;
        writer.write_all(&entry.key)?;
        match &entry.value {
            Some(v) => {
                writer.write_all(&(v.len() as u32).to_le_bytes())?;
                writer.write_all(v)?;
            }
            None => writer.write_all(&0u32.to_le_bytes())?, // Tombstone marker
        }
    }
    writer.flush()
}

The fundamental trade-off: B-Trees trade write amplification (rewriting 8KB pages for 50-byte updates) for O(1) point-read guarantees. LSM-Trees trade read amplification (probing multiple levels) for maximum sequential write throughput.

LSM-Trees: Append-only memtables and tiered compaction

LSM-Trees (used in RocksDB, CockroachDB, and Cassandra) never update data on disk in place. Ingestion follows a three-phase pipeline:

1. Write-Ahead Log (WAL) & Memtable: Writes append sequentially to an on-disk WAL for crash recovery and insert into an in-memory sorted skip-list (Memtable).
2. SSTable Flushing: When the Memtable reaches threshold capacity (e.g., 64MB), it is flushed sequentially to disk as an immutable Sorted String Table (SSTable) at Level 0.
3. Background Compaction: Leveled compaction merges overlapping SSTables across hierarchical tiers (\(L_0 \rightarrow L_1 \rightarrow L_2\)), removing deleted records (tombstones) and deduplicating old revisions.

Mitigating read amplification with Bloom filters

Because a key might reside in any SSTable across multiple levels, point lookups in an LSM-tree could theoretically require probing dozens of files. Production engines place an in-memory Bloom filter alongside each SSTable header.

A Bloom filter with 10 bits per key delivers a 1% false positive rate, ensuring that 99% of non-existent key lookups skip disk I/O entirely.

Tuning RocksDB compaction strategies or diagnosing write stalls? Get in touch.