LSM Tree: How Cassandra, RocksDB, and LevelDB Write Fast

The Memtable: Writes Never Touch Disk First

When an LSM tree receives a write, it does not go looking for the right place on disk to put it. Instead, the write is inserted into the memtable, an in-memory sorted structure, typically a skip list or a balanced tree, that holds the most recent writes. Because the memtable lives in RAM, inserting into it is extremely fast, and because it is kept sorted by key, later operations like range scans or flushes can walk it in order with no extra work.Every write also gets appended to a write-ahead log on disk before or alongside the memtable insert. This log is a safety net: if the process crashes before the memtable is flushed, the log can be replayed to rebuild the memtable's contents. The log itself is written purely sequentially, so it is cheap even though it touches disk on every write.The memtable has a fixed capacity, often measured in tens of megabytes. Once it fills up, the storage engine freezes it, starts a fresh empty memtable to absorb new writes, and schedules the frozen one to be flushed to disk. This handoff is what lets writes keep flowing without ever blocking on disk I/O in the common case.Updates and deletes are handled the same way as new writes: an update is just a new value written under an existing key, and a delete is a special marker called a tombstone. Neither operation searches for or modifies the old copy of the key. The old copy simply sits, stale, somewhere on disk, until compaction eventually notices and discards it. This is the core simplification that makes LSM writes so fast: append now, clean up later.Because reads need to see the freshest data, the memtable is always checked first before consulting anything on disk, since it holds the most recent state of any key that has been written recently.

SSTables: Immutable, Sorted, Flushed Sequentially

When a memtable is flushed, its sorted contents are written to disk as an SSTable, a sorted string table. The defining property of an SSTable is that it is immutable: once written, its bytes never change. This single design choice eliminates an entire category of problems that plague in-place storage. There is no need for locks to protect a file during a write, no risk of a crash leaving a page half-updated, and caching becomes trivial because a cached block can never go stale.Because the memtable was already sorted, writing it out as an SSTable is a single linear pass: the engine streams key-value pairs to disk in ascending key order, in one long sequential write. Sequential writes are dramatically faster than random writes on spinning disks, since there is no seek time between operations, and they are also friendlier to flash storage, which suffers wear and write amplification from small random updates.Each SSTable typically stores more than just the raw data. It usually includes a sparse index mapping keys to byte offsets, so a lookup does not have to scan the whole file, and often a small footer summarizing the key range covered by the file. Some engines also store per-block checksums to detect corruption.Over the life of a database, many SSTables accumulate on disk, one for every memtable flush plus every compaction output. A single key might technically exist in several SSTables at once, if it was written, then later updated. Only the copy in the newest SSTable, or in the memtable if it has not been flushed yet, is the current value; the rest are obsolete but still physically present until compaction removes them.

Reads: Checking the Memtable, Then SSTables Newest to Oldest

Writes in an LSM tree are cheap precisely because reads carry the cost instead. To answer a lookup for a given key, the engine cannot simply check one location; it must potentially search the memtable and every SSTable on disk. It always starts with the memtable, since that holds the freshest, unflushed writes. If the key is found there, the search stops immediately.If the key is not in the memtable, the engine moves to the SSTables, checking them in order from newest to oldest. This ordering matters because a key may have been written multiple times across different SSTables, and only the most recent version is correct. As soon as a matching key is found in an SSTable, the search can stop, since any older SSTable's copy of that key is stale by definition. If the found entry is a tombstone, the engine reports the key as deleted rather than continuing to search for an older, now-irrelevant value.In the worst case, a key that was never written recently and does not exist at all forces the engine to check the memtable and every single SSTable before concluding it is absent. This is read amplification: one logical read turning into many physical file lookups. As more SSTables pile up between compactions, read latency and worst-case cost both grow, which is the central price an LSM tree pays for its fast writes.Range queries, which ask for all keys between two bounds, face a similar challenge: the engine must merge results from the memtable and every relevant SSTable, taking the newest version of any key that appears more than once, which is more work than a B-tree's single ordered traversal of one structure.

Bloom Filters: Skipping Files That Can't Have the Key

Checking every SSTable for every read would make lookups unbearably slow once dozens of files accumulate. The standard fix is a bloom filter, a small, cheap probabilistic data structure built alongside each SSTable at write time. A bloom filter can answer one question extremely fast and with almost no memory: is it possible this key exists in this file?A bloom filter works by hashing a key with several independent hash functions and setting the corresponding bits in a bit array to one. To test whether a key might be present, the same hash functions are applied and the engine checks whether all the corresponding bits are set. If even one bit is zero, the key is definitely not in the file, and the SSTable can be skipped entirely without ever touching disk. If all the bits happen to be set, the key might be present, so the engine has to actually read the file's index to confirm, which occasionally means a wasted lookup called a false positive. Crucially, a bloom filter never produces a false negative: it will never claim a key is absent when it is actually there.Because bloom filters are compact, often just a handful of bits per key, they can be kept resident in memory even when the underlying SSTables are far too large to cache. This lets a database skip the vast majority of irrelevant files on disk with a single fast in-memory check, dramatically cutting the read amplification described earlier without giving up any of the write-side benefits of the LSM design.The false-positive rate is tunable: allocating more bits per key produces fewer wasted lookups at the cost of more memory, so operators can trade memory for read latency depending on their workload.

Compaction: Merging SSTables and the B-Tree Tradeoff

Compaction is the background process that keeps an LSM tree healthy over time. It periodically selects a set of SSTables, merges them into new, larger SSTables, and deletes the originals. During the merge, whenever the same key appears in multiple input files, only the newest version is kept, and tombstones can finally be dropped once the engine is sure no older SSTable still holds the data they were meant to shadow. This reclaims disk space and shrinks the number of files a future read must consult, directly reducing read amplification.Compaction is not free. It consumes disk I/O and CPU to rewrite data that was already written once, a cost known as write amplification: a single logical write may eventually be rewritten several times as it migrates through successive rounds of compaction. Different engines schedule compaction differently, for example size-tiered strategies that merge similarly sized files together, or leveled strategies that organize SSTables into levels of increasing size, but all of them are managing the same fundamental balance between how many files pile up and how much rewriting happens to keep that number down.This is where the comparison to a B-tree becomes concrete. A B+ tree index updates data in place: a write means finding the correct leaf page and modifying it directly, which keeps read cost predictable and low, typically one traversal to a single up-to-date location, but makes random writes expensive because each one may touch a different, arbitrarily located page on disk. An LSM tree flips this entirely: writes are sequential and cheap, landing anywhere is fine because nothing is searched for in place, but reads must potentially check multiple locations and rely on background compaction to keep that number bounded. Neither design is strictly better; a write-heavy workload like log ingestion or time-series data tends to favor LSM trees, while a read-heavy workload with few writes often favors B-trees, and the choice of storage engine is really a choice about which cost, read amplification and compaction overhead, or random write cost, a workload can afford to pay.

Frequently asked questions

Try it live

Everything above runs in your browser — open LSM Tree: How Cassandra, RocksDB, and LevelDB Write Fast and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.