Why architecture matters here
The architecture matters because the LSM-tree makes an explicit, tunable trade among three costs that a B-tree makes implicitly and rigidly. A B-tree updates a page in place: one logical write becomes roughly one page read and one page write, and reads touch a single path from root to leaf. That is beautifully balanced for read-heavy workloads, but it turns every insert into a random write, and random writes are exactly what storage hardware hates. Under a high ingest rate — sensor data, event logs, message queues, write-through caches — a B-tree spends its life seeking, and its page cache thrashes.
An LSM-tree answers by moving the cost off the write path and onto a background process. Writes become cheap: a sequential log append and an in-memory insert, both O(1) amortized and both friendly to the device. The bill arrives later, as compaction, and the crucial design property is that you get to choose how you pay it. Push compaction hard and you keep files few and reads fast, at the cost of rewriting data many times (high write amplification). Compact lazily and you save I/O, but reads must merge across more files (high read amplification) and stale versions pile up (high space amplification). No setting wins all three; the art is matching the strategy to the workload.
Getting the architecture right is therefore a capacity-planning decision, not just a code choice. It determines how much of your disk bandwidth is available for user traffic versus consumed by background merges, how much extra space you must provision for versions in flight, and how gracefully the store behaves when ingest outruns compaction. Treat the LSM-tree as a black box and you will eventually be paged for a write stall you did not know how to prevent.
There is a hardware dimension worth making explicit. On solid-state drives the sequential-append pattern is not only faster but kinder to the device: the flash translation layer strongly prefers large sequential writes, so batching updates into flushes reduces device-level write amplification even where it can raise engine-level amplification. On spinning disks the effect is starker still, since avoiding random seeks is the difference between a few hundred and tens of thousands of operations per second. The LSM-tree's shape is, in this sense, a direct reflection of storage physics — it is what you would design if you started from 'sequential writes are cheap, random writes are expensive' and reasoned forward. That is precisely why the same structure keeps reappearing across otherwise unrelated databases and key-value stores.
The architecture: every piece explained
A write enters through the write-ahead log. Before the engine acknowledges anything, it appends the mutation to a sequential WAL file and (depending on the durability setting) fsyncs it. The WAL exists solely for crash recovery: if the process dies before the in-memory data reaches disk as an SSTable, the WAL is replayed on restart to rebuild it. In parallel the mutation is inserted into the MemTable, an ordered in-memory structure — typically a skip list or a balanced tree — that keeps keys sorted so that scans and flushes are cheap.
When the MemTable reaches a size threshold it is frozen into an immutable MemTable and a fresh one takes over incoming writes. A background thread then flushes the frozen table to disk as a Sorted String Table (SSTable): an immutable file of key-value pairs in sorted order, accompanied by a sparse block index for binary search and a bloom filter that can quickly say 'this key is definitely not here.' Immutability is the linchpin — because an SSTable never changes after it is written, it needs no locking, caches trivially, and can be shared, snapshotted, and deleted atomically.
SSTables are organized into levels. Freshly flushed files land in L0, where they may overlap in key range because each is an independent snapshot of a MemTable. Below that, L1 through Ln hold files that are non-overlapping within a level and grow geometrically in total size — a common ratio is 10x per level. Compaction is the process that reads files from one level, merges them with the overlapping files in the next, drops superseded versions and expired tombstones, and writes fresh non-overlapping SSTables down a level. The level structure is what bounds read cost: a point lookup consults at most L0's few files plus one file per lower level, and the bloom filters let it skip most of those without touching disk.
Two supporting structures make the level scheme practical. Each SSTable carries a sparse index — sometimes called fence pointers — recording the first key of every data block, so a lookup binary-searches that index in memory and reads exactly one block from disk on a hit. And the engine maintains a manifest: a durable log of which SSTables exist at which levels, updated atomically as flushes and compactions add and retire files, so that after a crash the engine reconstructs a consistent view of the tree without scanning the whole directory. The manifest plus SSTable immutability is what lets an LSM engine offer consistent point-in-time snapshots almost for free — a snapshot is simply a pinned set of SSTables that compaction is instructed not to delete yet.
End-to-end flow
Follow a put(key, value). The engine appends the record to the WAL, fsyncs if configured for strong durability, and inserts it into the active MemTable, which keeps it in sorted position. The write is acknowledged — no SSTable was touched, no random I/O occurred. As more writes arrive the MemTable grows; when it crosses its threshold it is frozen and a flush thread streams it out as a new L0 SSTable, building the bloom filter and block index as it goes. Once the SSTable is durably on disk, the portion of the WAL that fed that MemTable can be discarded.
Now a get(key). The read checks the active MemTable first, then the immutable MemTables, then descends the levels newest to oldest. At each SSTable the bloom filter is consulted: a negative answer skips the file entirely without a disk seek, while a positive answer triggers a block-index binary search and, on a cache miss, a single block read. The first match found — searching newest to oldest — is the current value, because newer versions always shadow older ones. A range scan is more involved: it must open an iterator over every level, merge them in key order with a heap, and surface the newest version of each key while discarding shadowed ones and tombstoned deletes.
Meanwhile compaction runs continuously in the background. A strategy decides when a level has accumulated too much data or too many files and schedules a merge. The compactor opens iterators over the input SSTables, performs a k-way merge, keeps only the newest version of each key, drops tombstones whose deletes are safely older than any surviving version, and writes the output as fresh SSTables at the target level. When the output is durable the input files are atomically retired. This steady rhythm — append, flush, merge — is what keeps the file count bounded and reads fast even as terabytes stream in.
One property of this flow deserves emphasis: an LSM-tree never reads before it writes. A blind put does not check whether the key already exists; it appends a newer version and lets compaction reconcile the old one away later. This is why write throughput stays high even for update-heavy workloads that would force a B-tree to read a page, modify it, and write it back. The cost resurfaces on reads and at compaction, but for ingest-dominated systems that is exactly the right place to move it. Read-modify-write semantics such as counters, by contrast, must be handled carefully — often with merge operators that let compaction combine partial updates — because the engine's native model is append-and-reconcile, not update-in-place.