How LSM Trees Work | Write Buffers, Sorted Files, Versions and Compaction

LSM trees work by collecting recent changes in memory, writing batches into sorted files, and reorganising those files through merging. Rather than immediately locating and rewriting the final disk position of every changed key, the storage engine records new versions and resolves which version a reader should see.

The full name is log-structured merge tree. The important idea is not a particular tree-shaped drawing. It is a division of work: accept changes through a controlled write path, search across the representations that currently hold them, and perform maintenance that keeps the accumulated files manageable.

This guide explains how LSM trees work using a small, fictional equipment catalogue. We will follow a value from its first write to memory, through a sorted file, into a later update and deletion. The example uses a single storage engine with ordered sequence numbers; distributed databases can add different conflict-resolution rules. RocksDB’s overview and LevelDB’s implementation notes provide concrete reference implementations, not universal specifications for every LSM system.

For the preceding storage design, read How B+ Trees Work. For other mechanisms, return to the How X Works library.

---

The Direct Answer: Accept Changes Now, Reorganise Them in Batches

Imagine a catalogue containing millions of equipment identifiers. A request changes the status of one item. Another changes a different item. Reorganising a large disk structure immediately for every small operation can be expensive, particularly when the workload touches many unrelated locations.

An LSM design collects these operations into a memory-resident write structure. When a batch is ready, it produces a sorted, immutable table on storage. Later batches produce more tables. Reads reconcile their contents, while compaction merges selected tables and removes information that is no longer needed.

The bargain is clear: batching can make the immediate write path efficient, but multiple files and versions make reading and maintenance more complicated. The system must pay that cost somewhere. An LSM tree is an organised way of deciding when to pay, which work to combine, and which correctness rules must survive the reorganisation.

Start With Three Different Kinds of Order

Arrival order, key order and version order

A recovery log records operations in an order suitable for replay. A sorted table arranges entries according to the key comparator. Version metadata tells the engine which change supersedes another. These orders are related but not interchangeable.

Suppose writes arrive for lamp-9, camera-2 and lamp-9 again. The arrival sequence repeats lamp-9 around another key. A sorted file groups entries by key, so camera-2 may appear before both lamp-9 versions. Within lamp-9, sequence metadata distinguishes the earlier status from the later one.

This distinction solves a common puzzle: how can a system described as log-structured also support ordered searches? The log and the sorted read representation do different jobs. The system does not force every physical structure to use the same ordering merely because they describe the same logical data.

The Main Components and the Question Each Answers

A useful first map has five components. The memtable answers where recent searchable changes live in memory. A write-ahead log, when enabled, provides recovery information. SSTables hold immutable sorted entries on storage. File-set metadata identifies which tables belong to the live database. Compaction reorganises selected tables while preserving required read results.

These are responsibilities rather than a promise that every product uses exactly five files or modules. An engine can have several active write buffers, many immutable buffers, multiple namespaces, different table formats and several maintenance policies.

The practical test is to ask where an acknowledged update can be recovered, where a reader can find it, and which metadata makes that representation authoritative. A file existing in a directory answers none of those questions by itself.

Follow One Write Into the System

Our illustrative operation is put(camera-2, available) at sequence 41. In a logged write path, the engine records recovery information and inserts the version into its memory structure. The exact scheduling, batching and acknowledgement rules depend on the implementation and its configuration.

Now a reader asks for camera-2. The engine must consult recent state rather than look only at old disk files. Otherwise the application could receive a successful write response and immediately read a stale value, even though the new value is already present in memory.

One write therefore establishes several obligations: preserve ordering among relevant operations, expose the right version to appropriate readers, retain a recovery path consistent with the advertised durability, and eventually transfer the memory representation into stable table storage. Simply placing bytes in RAM is not the complete operation.

Durability Is a Contract, Not a Consequence of the Word Log

A log append may first reach a process buffer or operating-system cache. A durable synchronisation request has a different purpose: it asks the storage stack to make the write survive the failures covered by that stack’s guarantees.

RocksDB exposes synchronous and asynchronous write choices, as well as an option to disable the write-ahead log. Those options affect what can be lost after different failures. They should not be collapsed into one statement that an LSM write is always immediately durable. See the engine’s Basic Operations documentation for its actual contract.

For the learner, separate four questions: did the process accept the request; can another permitted read see it; can the local engine recover it after a crash; and does another machine hold an adequate copy? Visibility, local durability and replication are different properties. One does not automatically prove the others.

The Memtable Is More Than a Disposable Cache

A conventional read cache holds replaceable copies of information that can be loaded again from another authoritative representation. A memtable participates in the write path. Until its contents have been safely transferred, it can hold versions that no installed SSTable contains.

Calling it a cache can therefore encourage a dangerous mistake: discard it under memory pressure as though it were an expendable collection of recently read blocks. Correct disposal requires evidence that recovery and live reads no longer depend on that memory generation.

Memtable implementations vary. Ordered structures support search and scans directly; some specialised representations optimise insertion or prefix access and arrange order differently at flush time. RocksDB documents several choices in its MemTable reference. The role is stable even when the internal data structure changes.

Freezing a Buffer Does Not Make Its Bytes Durable

When the active buffer is ready to flush, an engine can stop adding new writes to that generation and start another. The older generation becomes immutable for the purpose of accepting new changes.

That immutability is an ownership transition, not a storage guarantee. The old buffer can still exist only in volatile memory. It normally remains readable while a flush creates its replacement representation.

Picture two desks in the catalogue office. One desk accepts new forms. A second contains a sealed batch being copied into the archive. Sealing the batch prevents its contents changing during copying; it does not mean the archive copy is complete. The same distinction explains why immutable memtables still consume memory and why a backlog of them can eventually slow writers.

Flush Creates a Sorted Table

A flush turns the selected memory generation into one or more persistent sorted-table outputs under the engine’s rules. Those outputs can contain values, deletion markers and retained versions. Producing the file is followed by the steps that make it part of the recognised live file set.

Flush is not a synonym for compaction. A flush starts from memory and produces table storage. Compaction generally starts from existing tables and produces replacement tables or a different file organisation. Both may perform some version elimination when it is safe, but they address different stages of the lifecycle.

Do not expect a memory budget of 64 units to produce a file of exactly 64 units. Memory contains allocation and indexing overhead; the output may use compression and different encoding, and safe pruning can change the number of entries. Compare the same byte categories before interpreting a size difference.

An SSTable Is Sorted and Searchable, Not Merely a Text Log

SSTable commonly expands to sorted string table. In modern storage discussions, it means an immutable sorted table representation, not a guarantee that every engine uses the same file format or textual strings.

A block-based format can contain data blocks, an index, filters and metadata that help the reader avoid scanning the entire file. LevelDB’s table-format description provides a concrete example of the relationship among data blocks, block handles, indexes and a footer.

The useful distinction is between changing an existing table entry in place and creating a newer representation elsewhere. The old table can remain physically intact while the logical value has already changed. Immutability makes the physical file simpler to share; version resolution makes the database behave as though updates still occur.

One Key Can Have Several Physical Versions

Extend the fictional catalogue. Sequence 41 says camera-2 is available. Sequence 47 says it is reserved. Sequence 52 deletes the key. The entries may be spread across an older SSTable, a newer SSTable and a current memory buffer.

The database does not contain three independent current cameras. It contains three pieces of history for one logical key. A latest-state read resolves that history according to its visibility rules.

This is why file creation time is not a reliable replacement for version metadata. Compaction can write an old logical version into a newly created physical file. That file is new as an object on storage; the operation it contains is still sequence 41. Rewriting information must not silently make it the newest business fact.

Worked Read: Which Camera Status Should Appear?

Assume our teaching model orders committed operations by sequence number and a snapshot at S may see operations numbered no greater than S. At snapshot 45, sequence 41 is the newest eligible camera entry, so the result is available. At snapshot 49, sequence 47 is eligible and supersedes 41, so the result is reserved. At snapshot 55, sequence 52 is eligible and is a deletion, so the key is absent.

The file arrangement can change between these reads without changing their answers. Move sequence 41 from one SSTable into a compacted SSTable and the same rule still returns available at 45. Storage movement is not a new catalogue update.

Real snapshot implementations have their own details. RocksDB’s Snapshot documentation explains why compaction must preserve data visible to active snapshots. The example makes that obligation inspectable without pretending to reproduce every transaction mode.

A Tombstone Is an Answer, Not an Empty Search Result

A deletion marker, often called a tombstone, records that an earlier value must not be returned to a read for which the deletion is visible. It is positive information about absence.

If the newest eligible entry for camera-2 is its tombstone, the reader must not continue searching older files until it finds the available value. That would turn deletion into a temporary inconvenience rather than a logical operation.

Distinguish three outcomes from inspecting a source: this source has no entry for the key; this source has a value version; this source has a deletion version. Only the first means there is no relevant evidence in that source. The other two contribute to version resolution. This small distinction prevents one of the most serious classes of storage bugs: deleted data appearing again.

Why Reads May Consult Several Files

Each flushed batch is sorted internally, but two batches can cover overlapping key ranges. Yesterday’s batch and today’s batch may both contain camera-2. Sorting each batch does not place every version into one global physical location.

A reader uses file-range metadata, table indexes and filters to narrow the candidate sources. It then resolves the relevant versions using the engine’s ordering and visibility rules. Some layouts permit early termination once sufficiently recent evidence is found; others require reconciliation across several sources.

The safe general statement is not “read every file” or “read one file.” It is “inspect enough eligible sources to prove the answer under this layout.” The number of candidate files depends on overlap, compaction policy, cache state and the requested read.

Bloom Filters Reduce Unnecessary Checks, Not the Need for Correctness

A correctly constructed membership filter can rule out many files or regions that do not contain a requested key representation. A positive result says the key may be present, so the engine still checks the table. It is not permission to return a value without an exact lookup.

There is a second boundary: physical presence is not current visibility. A table can contain an older value that a newer tombstone hides. Its filter can correctly report possible presence while the database must still return absence.

RocksDB’s Bloom-filter documentation describes its filtering options. Ordinary key-membership filters should not be presented as exact answers to arbitrary range queries. Matching the filter’s key and prefix semantics to the actual read is part of the design.

Range Scans Merge Ordered Sources

An LSM range scan cannot generally treat the newest file as the whole range. One key may have its newest visible value in memory, another in a recent file, and another only in an older level.

A useful model is several sorted streams. Position each relevant stream near the lower bound, select the next key, gather its versions, emit the visible result if one exists, and continue. A tombstone can suppress an older entry even when that older entry arrives from a different stream.

This contrasts with the linked-leaf walk explained in the B+ tree cluster. Both structures can support ordered ranges, but their continuation work differs. A range returning ten live keys may examine far more than ten physical entries when many versions or tombstones lie inside the range. Output size and work examined are not the same measure.

Compaction Preserves Answers While Changing Representation

Compaction selects inputs, reads their sorted entries, reconciles versions under retention rules, builds outputs and publishes a replacement file set. Old files can be reclaimed only when the engine’s metadata and reader-lifetime rules make that safe.

The most important acceptance test is semantic: every read the system still promises to support must return the same result before and after ordinary compaction. Reducing file count is useful, but it is not enough. A compacted database that is smaller because it discarded a snapshot’s required value is wrong.

The separate Index Segments and Merges guide explains related maintenance in document-search indexes. Here the subject is key-value LSM storage, where sequence versions, sorted tables and tombstone coverage determine the read result. Similar maintenance language does not make the two structures identical.

Leveled and Tiered Layouts Make Different Trades

In a leveled design, files are organised into levels with controlled key-range overlap. RocksDB’s leveled-compaction description distinguishes overlapping level-zero files from deeper levels that each form a sorted run. Compaction merges selected ranges into a destination level.

Tiered or universal-style approaches keep several sorted runs and combine them according to policy. They can reduce repeated rewriting at the cost of additional read candidates or temporary storage. RocksDB documents its particular version in Universal Compaction; other engines need their own comparison.

Think of the choice as how much disorder to tolerate between consolidation events. More consolidation can simplify reads but consume more maintenance bandwidth. Less consolidation can reduce immediate rewriting but leave more work for future reads. Neither choice eliminates the need to preserve visible versions.

Three Amplifications, Three Different Denominators

Write amplification compares physical writes with an explicitly chosen logical-write baseline. Read amplification describes extra work needed to answer a read, which might be measured in files, blocks, bytes or operations. Space amplification compares occupied storage with a defined useful-data size.

These are not interchangeable scores. A configuration can lower one while increasing another. Even two write-amplification figures may be incomparable if one includes the recovery log and the other counts only table writes.

In a fictional accounting window, suppose the application accepts 100 MB of logical writes, table flushes write 100 MB and compactions write another 500 MB. Table-write amplification is 600/100 = 6 under that definition. If recovery logging adds 100 MB, the expanded host-write measure becomes 7. Neither is a measured benchmark; the example shows why every ratio needs a labelled numerator.

Background Maintenance Still Uses the Same Machine

The word background describes scheduling, not free resources. Compaction competes for CPU, storage bandwidth, cache space and temporary disk capacity. A machine can accept a short burst rapidly into memory while being unable to sustain that rate once maintenance work catches up.

RocksDB’s Write Stalls documentation describes throttling when flushes or compactions cannot keep pace. Such limits protect the engine from uncontrolled accumulation; increasing a threshold does not create additional long-run processing capacity.

A useful diagnostic question is therefore not only “How fast did writes enter?” Ask “Did the queues return to their previous size after the burst?” A demonstration that ends before the backlog drains has measured admission performance, not necessarily sustainable database throughput.

The File Catalogue Is Part of the Database

Directory contents can include active tables, unfinished outputs, obsolete files and files still retained for readers. The live database is not simply the set of every file whose name ends in a particular suffix.

RocksDB uses MANIFEST records to describe changes to the recognised file set. Its MANIFEST documentation explains this metadata layer. The general lesson is that producing replacement bytes and installing the replacement are separate events.

Suppose a crash occurs halfway through producing a compacted output. The old inputs must remain usable because the new output is incomplete. Suppose the output is complete but not yet installed. Its existence alone still does not authorise deleting the inputs. A correct recovery procedure follows durable metadata and the engine’s publication protocol, not optimistic guesses about filenames.

A Local Snapshot Is Not a Backup or a Replica

A snapshot defines a read view. A backup is a recoverable copy created under a backup protocol. A replica is another maintained copy with its own consistency and availability rules. These can interact, but they solve different problems.

RocksDB’s documented snapshots do not survive a database restart as the same live snapshot handles. That does not make them useless; it means they are a read-consistency mechanism rather than an automatically durable archive.

For our catalogue, keeping a snapshot open may preserve the earlier available status for a report. It does not prove that the report can be recreated after the storage device is destroyed. Likewise, a successful local compaction does not prove that a disconnected replica has learned about every deletion. Name the failure being addressed before choosing the mechanism.

Distributed LSM Systems Add Another Retention Boundary

The single-engine sequence model is useful for learning, but a distributed database must also resolve updates arriving from different nodes and retain deletion information long enough for its replication and repair rules.

Apache Cassandra, for example, documents tombstone grace periods and repair conditions. A grace period is not a universal instruction to erase every deletion marker at an exact age. Other relevant data and replica state matter. See Cassandra’s tombstone documentation.

Do not import Cassandra’s distributed retention settings into a local RocksDB explanation as though they were one shared rulebook. The common mechanism is versioned immutable storage and consolidation. The authority for choosing a visible value and safely retiring history belongs to the actual system.

Diagnose the First Broken Stage

If acknowledged writes disappear after power loss, inspect the durability contract, synchronisation errors and recovery path before changing compaction settings. If memory rises while immutable buffers accumulate, inspect flush progress and memory accounting. If files multiply and reads slow while memory remains stable, inspect compaction progress and overlap.

If a deleted key reappears after maintenance, investigate tombstone retention and version ordering. If point lookups work but scans miss keys, inspect merge iteration, comparator consistency and snapshot visibility. If storage is nearly full despite many deletions, distinguish live data from retained versions, unfinished outputs and files pinned by readers or backups.

This method is deliberately causal. “The database is slow” names an outcome. A useful repair begins by identifying the earliest stage whose promised input-to-output transformation is not occurring, then checking what resource or correctness condition is blocking it.

A Small Laboratory: Preserve the Read Results

Write six cards: camera-2 available at 41; lamp-9 ready at 43; camera-2 reserved at 47; tripod-4 ready at 48; camera-2 deleted at 52; lamp-9 checked-out at 54. Divide them between two sorted file piles and one memory pile.

At snapshot 49, the visible map is camera-2 reserved, lamp-9 ready and tripod-4 ready. At snapshot 55, camera-2 is absent, lamp-9 is checked-out and tripod-4 is ready. Check both point queries and the complete sorted map.

Now merge the two file piles without changing logical versions. Recalculate the two views. They must remain identical. Finally, pretend snapshot 49 is still active and remove lamp-9’s older ready card. The older snapshot can no longer be answered correctly. That failed transformation demonstrates why “remove all duplicates” is not a sufficient compaction rule.

How to Compare an LSM Engine With a B+ Tree Fairly

Hold the workload and guarantees constant. Specify key and value sizes, update locality, point-read hit rate, range lengths, database size, cache budget, concurrency, durability requirements and snapshot lifetime. Include maintenance after ingestion rather than stopping when a memory buffer fills.

A B+ tree organises records through ordered pages and usually supports range continuation through its leaf layer. An LSM engine batches writes into runs and may merge multiple sources during reads. Those different choices create different costs; neither structure is automatically best for every workload.

For example, a workload dominated by short random updates may benefit from batching. A workload with strict tail-latency requirements and frequent long ordered scans may value a different layout. These are hypotheses to test, not vendor-independent guarantees. Report throughput together with latency, space, recovery behaviour and the cost of maintaining the claimed steady state.

Frequently Asked Questions

Is an LSM tree literally a binary search tree?

No. The term describes a storage organisation and update strategy. A memory component may use a tree, skip list or another representation, while the persistent components are commonly sorted files. The word tree should not make you expect binary child pointers throughout the storage engine.

Does every write immediately create an SSTable?

No. Batching recent writes is central to the common design. A flush produces table output from a selected memory generation. Flush triggers are implementation-specific and can include memory pressure or log-retention pressure, not only a completely full buffer.

Why keep a deleted key in storage?

The deletion marker may still be needed to hide an older value in another file or to satisfy retention and repair rules. Removing a marker prematurely can make the old value visible again. Logical absence can precede physical reclamation.

Does compaction always shrink the database immediately?

No. It may mainly change layout, retain required history, or temporarily increase disk use while outputs coexist with inputs. Space becomes reclaimable only when the engine no longer needs the replaced files and its recovery and reader-lifetime rules permit removal.

Can an LSM tree answer ordered range queries?

Yes. Sorted components support merging iterators and ordered scans. However, the scan may reconcile several overlapping sources and suppress obsolete versions. Its physical work is not necessarily equal to the number of live results returned.

Will a larger memtable remove write stalls?

It can absorb a larger temporary burst, but it cannot fix an indefinite mismatch between incoming work and sustainable flush or compaction capacity. The right question is whether the backlog eventually drains while the application continues to meet its latency and memory requirements.

Sources, Scope and the Next Step

The implementation references in this article are the official LevelDB, RocksDB and Apache Cassandra materials linked beside the relevant explanations. File layouts, configuration defaults and distributed repair rules are product-specific. The catalogue sequences and amplification arithmetic are teaching examples, not measurements of those products.

The next three guides examine the memory handoff, the immutable file and the maintenance algorithm separately. Keep their roles distinct: a memtable accepts recent state; an SSTable organises persisted entries; compaction replaces representations without changing the read answers the system promises to preserve.

---

Final Synthesis: Fast Admission Needs a Sustainable Maintenance Plan

An LSM tree does not make update work disappear. It groups work, changes its timing and keeps enough history to answer reads correctly while physical organisation catches up. Memory buffering, sorted tables, version resolution and compaction form one connected mechanism.

The clearest test is to follow one key through every transition. Can the right reader still find the right version? Can an acknowledged write survive the promised failure? Can a deletion remain deleted? Can maintenance keep up without exhausting resources? When those answers remain sound, batching becomes a durable storage strategy rather than a fast first few seconds followed by an expanding queue.