Storage engines: B-tree vs LSM

Key points

• Both start with a write-ahead log: append the change, fsync it, then update the structure. That is what survives a crash.
• A B-tree updates pages in place. A read is one page per level, but a random write dirties a random 8 KB page on disk.
• An LSM tree buffers writes in a sorted memtable and flushes whole files. Every disk write is sequential, so ingest is far faster.
• The bill arrives at read time: a key may live in the memtable or in any SSTable, so LSM engines put a Bloom filter on each file.
• Compaction merges files, discards overwritten values and applies tombstones. It costs background I/O and gives back the space.
• B-tree for read-heavy transactional work, LSM for write-heavy ingest. Postgres is a B-tree; Cassandra and RocksDB are LSM.

Example

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

public class Main {

    static final String DELETED = "(tombstone)";

    // Newest file first: the first hit wins, and a tombstone means "gone".
    static String get(List<TreeMap<String, String>> files, String key) {
        for (TreeMap<String, String> f : files) {
            String v = f.get(key);
            if (v != null) return v.equals(DELETED) ? null : v;
        }
        return null;
    }

    public static void main(String[] args) {
        List<TreeMap<String, String>> files = new ArrayList<>();   // newest at index 0
        TreeMap<String, String> memtable = new TreeMap<>();

        // Every write is an append: to the WAL, then into the sorted memtable.
        String[][] writes = {
            {"a", "1"}, {"b", "2"}, {"c", "3"},
            {"a", "9"},                       // an overwrite is just another write
            {"b", DELETED}                    // and so is a delete
        };
        for (String[] w : writes) {
            memtable.put(w[0], w[1]);
            if (memtable.size() >= 3) {                            // flush one sorted file
                files.add(0, new TreeMap<>(memtable));
                memtable.clear();
            }
        }
        files.add(0, new TreeMap<>(memtable));

        System.out.println("files, newest first : " + files);
        System.out.println("get(a) = " + get(files, "a") + "   <- the newest file wins");
        System.out.println("get(b) = " + get(files, "b") + "   <- the tombstone hides 2");
        System.out.println("get(c) = " + get(files, "c") + "   <- found in the older file");

        // Compaction: merge old into new, keep the latest value, drop the tombstones.
        TreeMap<String, String> merged = new TreeMap<>();
        for (int i = files.size() - 1; i >= 0; i--) merged.putAll(files.get(i));
        merged.values().removeIf(DELETED::equals);
        System.out.println("after compaction    : " + merged);
    }
}

B-trees pay on write and win on read; LSM trees pay on read and compaction and win on ingest.