LSM Trees vs B-Trees

Storage engines organise data on disk in one of two main ways.

For a broader system-design view see storage engines.

Example 1: B-tree structure

A B-tree is a shallow tree of pages (typically 8 KB in PostgreSQL, 16 KB in InnoDB). Internal pages hold keys and child pointers; leaf pages hold keys and row locations (or the rows themselves in a clustered index).

flowchart TD
    R["Root: 40 | 80"] --> A["Internal: 10 | 25"]
    R --> B["Internal: 50 | 65"]
    R --> C["Internal: 90 | 110"]
    A --> L1["Leaf: 1..9"]
    A --> L2["Leaf: 10..24"]
    A --> L3["Leaf: 25..39"]
    B --> L4["Leaf: 40..49"]
    B --> L5["Leaf: 50..64"]

A lookup reads one page per level. With a fan-out of several hundred keys per page, 3 to 4 levels hold hundreds of millions of rows.

Example 2: B-tree in-place update and page splits

An insert or update finds the leaf page and modifies it in place. When the page is full, it splits into two pages and the parent gets a new key.

flowchart LR
    subgraph Before
        P["Leaf (full): 10 12 14 16 18 20"]
    end
    subgraph After["After inserting 15"]
        P1["Leaf: 10 12 14 15"]
        P2["Leaf: 16 18 20"]
    end
    P --> P1
    P --> P2

Consequences:

• Writes go to random pages, so they cause random I/O.
• A split touches three pages (two leaves and the parent), which is why a WAL is required for crash safety (see WAL and crash recovery).
• Sequential keys fill pages almost completely. Random keys leave pages about 70% full after splits.

Example 3: page splits visible in index size (PostgreSQL)

Two tables hold 100000 keys each, with the index created before the load. One is loaded in key order, the other in pseudo-random order (md5 of the number).

CREATE TABLE idx_seq (k text);
CREATE TABLE idx_rnd (k text);
CREATE INDEX idx_seq_k ON idx_seq (k);
INSERT INTO idx_seq SELECT lpad(g::text, 32, '0') FROM generate_series(1, 100000) g;
CREATE INDEX idx_rnd_k ON idx_rnd (k);
INSERT INTO idx_rnd SELECT md5(g::text) FROM generate_series(1, 100000) g;
SELECT 'sequential' AS load_order,
       pg_size_pretty(pg_relation_size('idx_seq_k')) AS index_size
UNION ALL
SELECT 'random', pg_size_pretty(pg_relation_size('idx_rnd_k'));

 load_order | index_size 
------------+------------
 sequential | 5792 kB
 random     | 7632 kB
(2 rows)

The random-order index is larger because splits leave pages partly empty. Sequential inserts always split the rightmost page, which keeps the other leaves packed to the fill factor (90%).

Example 4: update in place vs new version (PostgreSQL)

PostgreSQL writes a new heap tuple version on every UPDATE (see MVCC and vacuum), so ctid changes. InnoDB updates the clustered-index row in place and keeps old versions in the undo log.

CREATE TABLE kv (id int PRIMARY KEY, v text);
INSERT INTO kv VALUES (1, 'a');
SELECT ctid, id, v FROM kv;
UPDATE kv SET v = 'b' WHERE id = 1;
SELECT ctid, id, v FROM kv;

 ctid  | id | v 
-------+----+---
 (0,1) |  1 | a
(1 row)

 ctid  | id | v 
-------+----+---
 (0,2) |  1 | b
(1 row)

Example 5: LSM write path

An LSM engine never modifies a file after it is written.

flowchart LR
    W["Write"] --> WAL["WAL append (sequential, durable)"]
    W --> M["Memtable (sorted, in memory)"]
    M -->|"full"| F["Flush"]
    F --> S0["SSTable L0 (immutable, sorted)"]
    S0 -->|"compaction"| S1["SSTables L1..Ln (merged, sorted)"]

Every write is one sequential log append plus one memory insert, which makes LSM writes fast.

Example 6: LSM read path and bloom filters

A read checks the memtable, then SSTables from newest to oldest until the key is found. A key that does not exist would touch every file. A bloom filter per SSTable answers "definitely not here" or "maybe here" from a small in-memory bit array.

With 10 bits per key the false-positive rate is about 1%. Bloom filters never give false negatives.

Example 7: compaction strategies

Cassandra offers both (SizeTieredCompactionStrategy, LeveledCompactionStrategy). RocksDB defaults to leveled compaction.

Example 8: amplification worked numbers

Write amplification (WA) is bytes written to disk divided by bytes written by the application.

Read amplification example: a leveled LSM with L0 holding 4 files and 4 more levels needs up to 4 + 4 = 8 SSTable probes for a miss without bloom filters. With a 1% false-positive filter the expected disk reads drop to about 0.08.

Example 9: comparison table

Example 10: which to choose

LSM engines also sit inside SQL systems: MyRocks (MySQL), CockroachDB and TiKV (RocksDB or Pebble) use LSM storage under a SQL layer.

Interview points

• The RUM conjecture: an engine cannot minimise Read, Update, and Memory (space) overhead at the same time.
• B-tree updates are in place, so they need a WAL. LSM writes are appends, and the log is the durability mechanism.
• Bloom filters remove most disk reads for missing keys in LSM trees.
• Leveled compaction favours reads and space, tiered compaction favours writes.
• Deletes in an LSM tree write tombstones, so heavy deletes can slow reads until compaction runs.

Summary

• B-trees update fixed-size pages in place, split full pages, and give predictable point and range reads.
• LSM trees write to a WAL and memtable, flush immutable SSTables, and merge them by compaction.
• Bloom filters cut disk reads for missing keys; compaction strategy trades write against read and space amplification.
• PostgreSQL and InnoDB use B-trees; RocksDB, LevelDB, and Cassandra use LSM trees.
• Choose B-trees for general OLTP and LSM trees for write-heavy ingestion.