Storage Engines: B-Tree vs LSM-Tree

A storage engine is the component of a database that writes data to disk and reads it back. Two designs dominate: B-tree engines update fixed-size pages in place, and LSM-tree (log-structured merge-tree) engines append data sequentially and merge it in the background. The designs make opposite trade-offs between write cost and read cost.

Page-oriented B-tree engines

Data lives in fixed-size pages (commonly 4 to 16 KB) organized as a B+tree (see database indexing). A write finds the leaf page for the key and modifies it in place. If the page is full, it splits.

Update-in-place raises a crash-safety problem: a split modifies several pages, and a crash midway leaves the tree inconsistent. Engines solve it with a write-ahead log (WAL), an append-only file to which every change is written and flushed before the pages are modified. After a crash, the engine replays the WAL to restore a consistent state. Some B-tree engines (LMDB, BoltDB) avoid the WAL by never overwriting pages: a change writes new copies of the modified pages (copy-on-write) and then atomically switches the root pointer.

sequenceDiagram
    participant C as Client
    participant E as B-tree engine
    participant W as WAL (disk, sequential)
    participant B as Buffer pool (memory)
    participant D as Data pages (disk)
    C->>E: write key
    E->>W: append record and fsync
    E->>B: modify page in memory
    E-->>C: acknowledge
    B->>D: flush dirty pages later (checkpoint)

Properties:

• Point reads and range scans are efficient: O(log n) page reads, and leaves are ordered.
• A logical write causes a WAL write and later a page write. A small change rewrites a whole page.
• Free space inside pages and fragmentation from splits increase space use.
• Each key exists in one place, which makes locking and transactional semantics straightforward.
• Examples: PostgreSQL, MySQL InnoDB, SQL Server, Oracle, LMDB, BoltDB.

LSM-tree engines

An LSM-tree turns random writes into sequential writes.

1. Write path. A write is appended to a WAL and inserted into the memtable, a sorted in-memory structure such as a skip list or balanced tree. The WAL exists so that a crash does not lose the memtable: on restart, the engine replays it to rebuild the memtable.
2. Flush. When the memtable reaches a size limit, it is written to disk as an immutable, sorted file called an SSTable (sorted string table), and a new memtable starts.
3. Read path. A read checks the memtable, then SSTables from newest to oldest, and returns the first match.
4. Deletes. A delete writes a tombstone marker. The key is removed physically during compaction.
5. Compaction. Background jobs merge SSTables, discarding overwritten values and tombstones, and produce larger sorted files.

flowchart TB
    W["write"] --> WAL["WAL (append)"]
    W --> M["Memtable (sorted, memory)"]
    M -->|"flush when full"| L0["Level 0 SSTables"]
    L0 -->|"compaction"| L1["Level 1 SSTables"]
    L1 -->|"compaction"| L2["Level 2 SSTables"]
    R["read"] --> M
    R --> L0
    R --> L1
    R --> L2

Each SSTable stores keys in sorted order with a sparse index, so a lookup within a file needs one index search and one block read. Blocks are usually compressed.

Bloom filters

A read for a missing key would otherwise check every SSTable. Each SSTable therefore has a bloom filter, a compact probabilistic set. It never gives false negatives, so a "no" answer lets the engine skip the file. A "yes" can be a false positive, in which case the file is searched and nothing is found. See probabilistic data structures.

Compaction strategies

Examples of LSM engines: LevelDB, RocksDB, Apache Cassandra, HBase, ScyllaDB. RocksDB is embedded in many systems as the local storage layer.

A minimal memtable, flush, and read path

The following sketch keeps a memtable in a BTreeMap, flushes it to an immutable sorted run, and reads newest-first, with tombstones represented by a Tombstone record. A sealed Cell type separates a stored value from a tombstone, so no null marks a deleted key:

import java.util.ArrayList;
import java.util.List;
import java.util.Optional;
import java.util.TreeMap;

public class Main {
    sealed interface Cell permits Put, Tombstone {}

    record Put(String value) implements Cell {}

    record Tombstone() implements Cell {}

    static class Lsm {
        private TreeMap<String, Cell> memtable = new TreeMap<>();
        private final List<TreeMap<String, Cell>> runs = new ArrayList<>(); // newest last
        private final int limit;

        Lsm(int limit) {
            this.limit = limit;
        }

        void put(String k, String v) {
            memtable.put(k, new Put(v));
            maybeFlush();
        }

        void delete(String k) {
            memtable.put(k, new Tombstone());
            maybeFlush();
        }

        private void maybeFlush() {
            if (memtable.size() >= limit) {
                runs.add(memtable); // becomes an immutable sorted run
                memtable = new TreeMap<>();
            }
        }

        Optional<String> get(String k) {
            Cell cell = memtable.get(k);
            if (cell == null) {
                for (var run : runs.reversed()) {
                    cell = run.get(k);
                    if (cell != null) {
                        break; // the newest cell for the key decides, a tombstone included
                    }
                }
            }
            return switch (cell) {
                case Put p -> Optional.of(p.value());
                case Tombstone t -> Optional.empty();
                case null -> Optional.empty();
            };
        }

        void compact() {
            var merged = new TreeMap<String, Cell>();
            for (var run : runs) {
                merged.putAll(run); // newer runs overwrite older ones
            }
            merged.values().removeIf(c -> c instanceof Tombstone); // drop tombstones
            runs.clear();
            runs.add(merged);
        }

        int runCount() {
            return runs.size();
        }
    }

    public static void main(String[] args) {
        var db = new Lsm(2);
        db.put("a", "1");
        db.put("b", "2"); // flush
        db.put("a", "3");
        db.delete("b"); // flush
        System.out.println("runs before compaction: " + db.runCount());
        System.out.println("a = " + db.get("a") + ", b = " + db.get("b"));
        db.compact();
        System.out.println("runs after compaction: " + db.runCount());
        System.out.println("a = " + db.get("a") + ", b = " + db.get("b"));
    }
}

runs before compaction: 2
a = Optional[3], b = Optional.empty
runs after compaction: 1
a = Optional[3], b = Optional.empty

The sketch omits the WAL, on-disk files, bloom filters, and partial compaction.

Amplification

Three metrics compare engines.

• Write amplification: bytes written to disk divided by bytes the application wrote. B-trees rewrite whole pages plus the WAL. LSM-trees rewrite data each time compaction moves it to a new level, so leveled compaction can have high write amplification.
• Read amplification: disk reads per logical read. B-trees read one path of pages. LSM-trees may check several files; bloom filters and leveling limit this.
• Space amplification: bytes on disk divided by logical data size. B-trees waste space in partially filled pages. LSM-trees hold obsolete versions until compaction, and size-tiered compaction needs temporary space.

Comparison

SSDs make write amplification relevant to device wear as well as throughput, which favors designs with lower total bytes written.

Choosing

Choose a B-tree engine when reads and range scans dominate, transactional semantics are central, and predictable latency matters. Choose an LSM engine when the write rate is high, data is large and compressible, and eventual compaction work is acceptable. Both are tunable, so measure with the real workload.

Interview questions

• Why is an LSM-tree write fast? It appends to a WAL and inserts into an in-memory structure. No random disk I/O occurs on the write path. Sorting and merging are deferred to background flushes and compaction.
• Why does an LSM-tree need bloom filters? A read may have to consult several SSTables. A bloom filter per file tells the engine, with no false negatives, that a key is definitely absent, so most files are skipped.
• What is a tombstone and why is it needed? A marker written on delete. Since SSTables are immutable, the older value still exists in older files, and the tombstone hides it until compaction removes both.
• Why does a B-tree need a WAL? Updating in place can leave pages half-written or a split incomplete after a crash. Logging the change first allows recovery to redo or undo it.
• What causes latency spikes in an LSM engine? Compaction and flushes consume disk bandwidth and CPU. If writes outpace compaction, files accumulate and the engine may throttle writers.