A B-tree updates data in place, paying a random disk write per change. The log-structured merge-tree makes a different bet: never update in place. Writes land instantly in a small in-memory memtable; when it fills, it’s flushed to disk as an immutable, sorted SSTable and a fresh memtable takes over. Reads consult the memtable first, then SSTables newest-to-oldest. Old versions pile up until compaction merges files and discards the shadowed ones. Write some keys, watch them flush, then read and compact.
A small sorted in-memory buffer where every write lands first — no disk seek.
SSTable
A Sorted String Table: an immutable, sorted file flushed from a full memtable.
read path
Check the memtable, then SSTables newest-first; the first hit wins.
compaction
Merge SSTables into fewer, dropping keys shadowed by a newer version.
lsm.js — memtable, SSTables, compaction
Ready
Every write lands in the sorted memtable in memory. When it reaches 4 keys it flushes to an immutable SSTable on disk. Write keys and watch it fill.
0/4
memtable
0
SSTables
–
last read cost
How it works
The trade the LSM-tree makes is write amplification down, read amplification up. Because writes only ever append to a memtable and later flush sequentially, they avoid the random in-place disk writes a B-tree pays — great for write-heavy workloads. The cost is that one key’s history can be spread across several SSTables, so a read may have to check several files (newest first) before it finds the current value. Compaction is what keeps that number bounded: it merges SSTables and throws away every version shadowed by a newer one.
1
Write → memtable
Each write updates the in-memory memtable, kept sorted by key. No disk seek, so writes are fast and cheap. Updating an existing key just overwrites it in the memtable.
2
Full → flush to an SSTable
When the memtable reaches its size limit, it’s written out sequentially as a new immutable, sorted SSTable, and an empty memtable takes over. Old SSTables are never modified.
3
Read → newest-first
A read checks the memtable, then each SSTable from newest to oldest, stopping at the first match. The newest occurrence of a key is its current value; older copies are stale.
✓
Compaction → merge and prune
Over time, stale versions accumulate across SSTables. Compaction merges SSTables into fewer files, keeping only the newest value per key — reclaiming space and shortening the read path.
Writes
sequential, fast
Read amplification
multiple files
SSTables
immutable, sorted
Used in
RocksDB, Cassandra
The code
# simplified LSM write / read / compactdef put(k, v):
memtable[k] = v # fast: in-memory, sortedif len(memtable) >= LIMIT:
sstables.insert(0, flush(memtable)) # immutable sorted file
memtable = SortedDict()
def get(k):
if k in memtable: return memtable[k]
for sst in sstables: # newest -> oldestif k in sst: return sst[k] # first hit is currentreturnNonedef compact(): # merge, keep newest per key
sstables = [merge_keeping_newest(sstables)]
Quick check
1. Why are writes to an LSM-tree fast?
Writes only touch the in-memory memtable, and full memtables are flushed to disk sequentially as immutable SSTables. Avoiding random in-place disk writes is exactly what makes LSM-trees write-optimized.
2. A key was written three times over its lifetime. Where is its current value?
Reads go newest-first: memtable, then SSTables from newest to oldest. The first occurrence found is the current value; older copies in older files are stale and ignored.
3. What does compaction accomplish?
Compaction merges multiple SSTables into fewer, keeping only the newest value of each key. That reclaims the space held by stale versions and reduces how many files a read must check.
FAQ
What is an LSM-tree?
A write-optimized storage structure. Writes go into an in-memory sorted buffer (memtable); when full it flushes to an immutable sorted file (SSTable). Reads check the memtable then SSTables newest-to-oldest, and compaction merges files while discarding shadowed old versions.
How does an LSM-tree differ from a B-tree?
A B-tree updates in place (a random disk write per update), favoring reads. An LSM-tree never updates in place — it appends to a memtable and flushes sequentially, favoring writes. The trade: LSM reads may check several files (higher read amplification) vs a B-tree’s single path.
What is read amplification in an LSM-tree?
Because a key’s versions spread across the memtable and multiple SSTables, one read may check several places before finding the current value — that extra work is read amplification. Per-SSTable bloom filters (skip files that definitely lack the key) and compaction both reduce it.
Which databases use LSM-trees?
Write-heavy and large-scale stores: RocksDB and LevelDB, Cassandra and ScyllaDB, HBase and Bigtable, and RocksDB-based systems like CockroachDB and TiKV — chosen when write throughput and sequential I/O matter more than the lowest possible read latency.
SOLVE IT YOURSELF
Solve it: build an LSM-tree
A B-tree updates a record where it already lives — a random disk write per update. An LSM-tree refuses to: every write is an append to memory, flushed later as an immutable sorted file. Writes get fast; reads and deletes get interesting. Python or TypeScript.
YOUR TASK
Implement LSMTree with put(key, value), get(key), delete(key) and compact(). The memtable flushes to a new segment once it holds threshold entries. get returns None/null for a missing or deleted key.
HINTS — 9 IDEAS
Writes land in the memtable, an in-memory sorted map. No disk seek, no read-before-write — this is the whole reason LSM-trees are write-optimised.
When the memtable fills, freeze it into an immutable sorted segment and start an empty one. Segments are never edited afterwards, only created and discarded.
Because segments are immutable, an overwrite does not replace anything — it just writes a newer copy elsewhere. Both versions exist on disk at once.
So get must search newest-first: memtable, then segments in reverse creation order. The first hit wins; anything older is a stale version.
Delete cannot erase a key from an immutable file, so it writes a tombstone — a marker meaning "deleted here". A read that hits a tombstone first must report absence, not keep looking.
Without tombstones, deleting a key would silently resurrect its older value from an earlier segment. That is the bug this design exists to prevent.
Compaction merges segments oldest-to-newest into one, keeping only the newest version of each key and dropping tombstoned keys entirely. That is where the space actually comes back.
Flush the memtable before merging. A tombstone still sitting in memory would be missed, and the compacted segment would carry the key's old value straight back onto disk.
The cost of all this is read amplification: a miss touches every segment. Real engines add a Bloom filter per segment to skip most of them.