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.
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
- 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..
- 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.
- 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.
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
Try this:
- With small 200-byte rows, compare write amplification: rewriting an 8 KB page for each small row costs the B-tree heavily.
- 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.
- 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
| Option | Wins when | Loses 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
-
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.
-
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.
-
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.
-
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.