Skip to content
learn
  1. Learn
  2. High Level System Design
  3. Databases and Storage Fundamentals

System Design HLD-06.06

Storage engines: B-tree vs LSM-tree

Updating pages in place versus appending and merging: memtables, SSTables, compaction, bloom filters, and read, write and space amplification.

Advanced 15 min Last reviewed

The big idea

Underneath every database is a storage engineThe part of a database that decides how data is laid out on disk and how reads and writes reach it. that decides how bytes are laid out on disk. There are two dominant designs, and they make opposite bets. A B-tree keeps data in sorted pages and updates them in place: reads are fast and predictable, but each small write may rewrite a whole page somewhere random on disk. An LSM-treeLog-structured merge tree: a storage engine that buffers writes in memory, flushes them as sorted immutable files, and merges those files in the background. never updates in place: it collects writes in memory, writes them out as new sorted files, and merges files in the background. Writes become fast sequential appends, but a read may have to look in several files.

Neither is better in general. PostgreSQL and MySQL InnoDB use B-trees; Cassandra, ScyllaDB, RocksDB and the systems built on it use LSM trees. Knowing the difference tells you why one database shrugs off a million writes per second while another serves point reads with lower, steadier latency.

Think of a filing cabinet versus an inbox tray. The cabinet (B-tree) keeps every folder in order, so finding one is quick, but filing each new sheet means opening the right drawer. The inbox (LSM) takes new sheets instantly; once in a while you sort the inbox and merge it into the archive boxes.

How it works

Step 1: The LSM write path

LSM-tree write path: memtable, flush, and compaction levels Writes are appended to a write-ahead log and inserted into an in-memory sorted memtable. When the memtable fills, it is flushed to disk as an immutable sorted file called an SSTable in level 0. Background compaction merges files from level 0 into level 1 and from level 1 into level 2, discarding overwritten values and deletion markers. flush merge down writes WAL durability Memtable sorted, in memory L0 SSTables recent flushes L1 ~10x larger L2 ~100x larger Compaction merge, drop old versions Figure 1. Writes land in memory (and the WAL), flush as sorted immutable SSTables, and are merged down the levels by background compaction, which drops overwritten values and deleted keys. Each level is roughly ten times larger than the one above.
  1. A write is appended to the WAL and inserted into the memtableAn in-memory sorted structure that collects recent writes in an LSM-tree before they are flushed to disk..
  2. When the memtable fills (tens of megabytes), it is written out as an SSTableSorted String Table: an immutable on-disk file of key-value pairs sorted by key, with an index and often a bloom filter.: a sorted, immutable file. This is one big sequential write.
  3. Background compaction merges SSTables, keeping only the newest version of each key and discarding deleted ones, into larger files in deeper levels.

Deletes are writes too: a tombstoneA marker written to record that a key was deleted; the old value is removed later when compaction merges past it. marks the key as deleted until compaction removes it.

lsm.pyruns with python3 (standard library)
TOMBSTONE = None

class TinyLSM:
    def __init__(self, memtable_limit=3):
        self.memtable, self.sstables, self.limit = {}, [], memtable_limit   # sstables: newest first

    def put(self, key, value):
        self.memtable[key] = value                   # writes only touch memory (plus a WAL in real life)
        if len(self.memtable) >= self.limit:
            self.flush()

    def delete(self, key):
        self.put(key, TOMBSTONE)                     # deletes are writes of a marker

    def flush(self):
        run = dict(sorted(self.memtable.items()))    # sorted, immutable file
        self.sstables.insert(0, run)
        self.memtable = {}
        print(f"  flush -> sstable {list(run)}")

    def get(self, key):
        files_checked = 0
        for table in [self.memtable] + self.sstables:  # newest data wins
            files_checked += 1
            if key in table:
                return table[key], files_checked
        return TOMBSTONE, files_checked

    def compact(self):
        if self.memtable:
            self.flush()                             # compaction works on flushed files only
        merged = {}
        for table in reversed(self.sstables):        # oldest first, newer overwrite
            merged.update(table)
        merged = {k: v for k, v in sorted(merged.items()) if v is not TOMBSTONE}
        self.sstables = [merged]
        print(f"  compact -> 1 sstable {merged}")

db = TinyLSM()
for k, v in [("a", 1), ("b", 2), ("c", 3), ("a", 10), ("d", 4), ("e", 5)]:
    db.put(k, v)
db.delete("b")
db.put("f", 6)
print("get a ->", db.get("a"), "(value, structures checked)")
print("get b ->", db.get("b"))
print("get c ->", db.get("c"))
db.compact()
print("get c ->", db.get("c"), "after compaction")

Output

  flush -> sstable ['a', 'b', 'c']
  flush -> sstable ['a', 'd', 'e']
get a -> (10, 2) (value, structures checked)
get b -> (None, 1)
get c -> (3, 3)
  flush -> sstable ['b', 'f']
  compact -> 1 sstable {'a': 10, 'c': 3, 'd': 4, 'e': 5, 'f': 6}
get c -> (3, 2) after compaction

Reading c before compaction checks the memtable and two files; the newest version always wins, and b's tombstone hides its older value. After compaction there is one file and the tombstone and overwritten values are gone.

Step 2: Reads and bloom filters

A point read checks the memtable, then each level from newest to oldest, until it finds the key. To avoid reading files that cannot contain the key, each SSTable carries a bloom filterA compact probabilistic structure that answers 'definitely not present' or 'possibly present' for a key, with no false negatives.: a small in-memory bit array that says "definitely not here" or "maybe here". With a 1 percent false-positive rate, almost every unnecessary file read is skipped. Bloom filters are covered in Probabilistic data structures .

Step 3: The three amplifications

Storage engines are compared by how much extra work they do:

  • Write amplification: bytes written to disk per byte of data. LSMs rewrite data during each compaction; B-trees rewrite whole pages for small changes.
  • Read amplification: disk reads per lookup. B-trees need about one; LSMs may check several files, mitigated by bloom filters and caches.
  • Space amplification: disk used per byte of live data. LSMs hold old versions until compaction; B-tree pages are partly empty.

Try it

This interactive needs JavaScript. The diagrams and text above cover the same idea.

Try this:

  1. With small 200-byte rows, compare write amplification: rewriting an 8 KB page for each small row costs the B-tree heavily.
  2. Switch to size-tiered compaction: LSM writes get cheaper, but lookups check more files and space use rises. Leveled versus tiered is a tuning trade-off inside LSMs.
  3. Raise the row size to 4,000 bytes. The B-tree's write disadvantage shrinks, because each row now fills most of a page.

These are simplified models meant to show direction and rough size; real numbers depend heavily on workload, caching and tuning.

Going deeper

Why SSDs care

SSDs cannot overwrite in place; they erase and rewrite blocks internally, and they wear out after a limited number of writes. Sequential, large writes are friendlier to them than small random ones, which is one reason LSM engines became popular. But compaction itself can saturate disk bandwidth, so LSM systems must throttle it carefully or tail latency suffers.

Trade-offs

OptionWins whenLoses when
B-tree (in place) Read-heavy workloads, predictable point reads and range scans, transactional databases Very high volumes of small random writes
LSM leveled compaction Write-heavy workloads that still need good reads and tight space Extra compaction writes and occasional latency spikes
LSM size-tiered compaction Write-dominated workloads like logging and metrics Read amplification and temporary space during merges

Common mistakes

  • Choosing an LSM store for a read-heavy, update-in-place workload where a B-tree shines.
  • Ignoring compaction: an LSM database that falls behind on compaction slows down sharply.
  • Deleting huge numbers of keys in an LSM store and being surprised that space is not freed until tombstones compact away.
  • Comparing engines on write throughput alone while ignoring read latency and disk usage.

Check yourself

  1. Why are LSM-tree writes fast?

    Show answer

    B. Writes go to memory and are flushed as large sequential files, never updated in place Appending sequentially is much cheaper than rewriting random pages.

  2. What does compaction do?

    Show answer

    B. Merges SSTables, keeping the newest versions and dropping deleted keys It merges files into larger sorted runs and removes overwritten values and tombstones.

  3. What role do bloom filters play in an LSM read?

    Show answer

    B. They let reads skip files that definitely do not contain the key A 'definitely not here' answer avoids a disk read for that file.

  4. Which workload most favors an LSM-tree?

    Show answer

    B. Huge streams of small writes, such as metrics or messages LSMs turn many small writes into efficient sequential writes.

Recap

  • B-trees update sorted pages in place: fast, steady reads; costly small random writes.
  • LSM-trees buffer writes in a memtable, flush sorted SSTables and compact in the background.
  • Deletes are tombstones until compaction; bloom filters keep reads from checking every file.
  • Compare engines by write, read and space amplification.
  • Read-heavy and transactional: B-tree. Write-heavy at scale: LSM.

Get new lessons by email

Get new posts on backend and AI internals. No spam, unsubscribe anytime.

Your email is only used to send new posts. Privacy