The Log-Structured Merge-Tree (LSM-Tree)

In one breath — the whole paper, compressed

High-insert-rate History tables and transaction logs need a real-time index, but in the paper's modified TPC-A example a B-tree on Account-ID concatenated with Timestamp adds 2000 random I/Os per second on top of the 2000 the Account table already needs, doubling the disk arms and raising total system cost by up to fifty percent. The LSM-tree replaces immediate placement with deferred, batched placement: every entry is inserted into a memory-resident C0 tree at zero I/O cost, and a continuously circulating rolling merge cursor sweeps sorted runs of C0 entries into a disk-resident C1 tree, reading and writing only multi-page blocks of about 256 KBytes to fresh disk locations. Two multiplicative savings follow: a page I/O inside a multi-page block costs about one tenth of a random page I/O, and M entries get merged into each C1 leaf page for the price of one read and one write. Generalizing to K+1 components with a geometric size ratio between neighbours lets the expensive memory component shrink while keeping the merge I/O rate low. On the paper's worked example a B-tree costs $56,400 against $11,400 for a two-component LSM-tree, and at ten times the insert rate $506,400 against $11,300 for three components.

Before this paper — the world it landed in

In 1996 the B-tree was the default on-disk index in every commercial system, and a B-tree insert at a random key costs a search down the directory plus a dirty leaf write - about De + 1 random page I/Os, with the effective depth De typically 2 for indexes of this size. Gray and Putzolu's Five Minute Rule set the economics of the alternative: it pays to buy memory to hold a page only if that page is referenced more often than roughly once every 60 seconds at 1995 prices, a threshold that had fallen from five minutes in 1987 because memory got cheap and mass-produced disks got cheaper. A 20-day Acct-ID concatenated with Timestamp index holding 576,000,000 entries occupies 9.2 GBytes on about 2.3 million leaf pages, so any single page is touched for an insert only about once every 2,300 seconds - far below the buffering threshold, meaning every insert really does go to disk twice. At the same time, long-lived activity-flow systems such as Sagas, ConTracts and the Escrow method were generating so many log records over such long durations that the memory-resident structures traditionally used to track active logs no longer fit. Earlier designs did defer placement - the Time-Split B-tree, the MD/OD R-tree, Differential Files - but all of them treated the small fresh component as disk resident, which is precisely why none of them cut the insert cost.

The problem — what was actually breaking

In the modified TPC-A example, maintaining a real-time B-tree index on Acct-ID concatenated with Timestamp adds 2000 random I/Os per second to the 2000 already required by the Account table, forcing the purchase of 50 more disk arms and effectively doubling the disk cost of the application.
Because Acct-ID values are drawn at random from 100,000,000 accounts, every new index entry lands on an essentially arbitrary one of the 2.3 million existing leaf pages, so there is no locality for a buffer manager to exploit.
By the Five Minute Rule those leaf pages are referenced only about once every 2,300 seconds, far too rarely to justify memory residence, so each insert pays one page read and, in the steady state, one page write.
The gating cost is disk arms rather than disk media: the index needs only 9.2 GBytes of capacity but must be spread over enough spindles to sustain its I/O rate, so most of the purchased capacity sits idle.
Long-lived activity-flow and workflow systems accumulate so many log records over such extended durations that the memory-resident structures used to track active logs are no longer feasible, yet those logs must still be queryable in real time.
No classical access method escapes this: B-trees, SB-trees, Bounded Disorder files and extendible hashing all place a new entry immediately in its final collation order - what the paper names a Continuum Structure - and therefore all cost at least two I/Os per insert.

Core ideas — the contributions, and why they work

Deferred, batched index placement

The LSM-tree never puts a new entry where it ultimately belongs. An insert goes only into the memory-resident C0 tree, costing no I/O at all, and the entry migrates outward later in the company of many neighbours. This works because the cost of an index insert is dominated by disk arm rental, and an arm that moves once on behalf of hundreds of entries is hundreds of times cheaper per entry. The paper is emphatic that deferral alone is not enough: the initial component must be guaranteed memory resident, since a component that is merely likely to be buffered will degrade back to two I/Os per insert, which is exactly why the Time-Split B-tree and the MD/OD R-tree do not deliver this win.

The rolling merge

Rather than a periodic reorganization, a conceptual cursor circulates continuously through equal key values of C0 and C1, drawing entries out of memory into the disk component in quantized merge steps. Each step reads one leaf node of C1 from a buffered emptying block, merges it with the matching range of C0 entries, and writes the result into a filling block that goes to a fresh disk location once packed. When the cursor reaches the maximum key value it wraps around and starts again from the smallest. Because the sweep is sorted and monotone, all merge traffic is large sequential block I/O rather than random page I/O, and the trailing edge of the cursor frees whole blocks at once.

Multi-page blocks and fully packed nodes

C1 has a B-tree-like directory, but its nodes are 100 percent full and sequences of single-page nodes below the root are laid out contiguously in multi-page disk blocks envisioned at about 256 KBytes, an optimization taken from the SB-tree. Merges and long range retrievals read and write whole blocks; exact-match finds descend a path of single-page nodes so buffer demand stays small. Amortizing one seek and one rotational delay across roughly 64 pages is precisely what makes the block page cost about one tenth of the random page cost. Full packing also gives a capacity advantage over a growing B-tree, which sits at only about 70 percent occupancy.

The two-factor insert cost model

The paper compresses the entire comparison into one ratio: the LSM-tree insert cost divided by the B-tree insert cost equals K1 times COSTpi/COSTP times 1/M, where K1 = 2/(De+1) is about 0.67. The first factor is the block-I/O discount, roughly 1/10, fixed by disk mechanics and untouchable by any algorithm. The second is the batch-merge parameter M, the average number of C0 entries merged into each C1 leaf page, equal to (Sp/Se) times S0/(S0+S1), which grows as the memory component grows. Their product typically gives nearly two orders of magnitude, and the model is honest enough to state its own failure condition: if M ever drops below K1 times COSTpi/COSTP, you should use a plain B-tree instead.

Multi-component trees and the optimal size ratio

Making M large in a two-component tree requires an expensive C0, so the fix is to interpose intermediate disk components C0, C1, ..., CK of increasing size with an independent asynchronous rolling merge between every adjacent pair. Theorem 3.1 proves that with the largest size SK, the memory size S0 and the insert rate R all fixed, the total merge page I/O rate H is minimized exactly when all the ratios ri = Si/Si-1 equal a single value r, namely the Kth root of SK/S0, giving H = (2R/Sp) times (K(1+r) - 1/2). Batching efficiency then compounds geometrically across levels, so the memory component can shrink dramatically - in the paper's example, going from two to three components cuts S0 from 135 MBytes to 17 MBytes at a lower total cost. This is the result that modern leveled compaction implements.

Mergeable operations beyond insert

Deletes get the same deferral: if the key is absent from C0, a delete node entry is placed there carrying the RID to remove, and it annihilates the real entry when the two meet during a later merge. Finds must be filtered through delete node entries, which is cheap because the tombstone always sits in an earlier component than its victim. An update to an indexed value is treated as a delete followed by an insert. The paper also defines predicate deletion, where merely asserting a predicate such as older than 20 days causes matching entries to be dropped as the merge passes over them, and long-latency finds, where a find note entry rides the cursor outward accumulating RIDs until it reaches the largest relevant component.

Indexing as lowering data temperature

The paper defines the temperature of a body of data as H/S, accesses per second per megabyte, with a freezing point Tf = COSTd/COSTP below which storage capacity is the binding cost and a boiling point Tb = COSTm/COSTP above which memory residence pays - a direct generalization of the Five Minute Rule. In this language, what the LSM-tree achieves is a reduction in the actual disk access rate and therefore a lowering of the effective temperature of the indexed data. A workload that is hot in logical insert rate becomes merely warm in physical disk access rate, so data a B-tree would force into memory can stay on disk. Reframing an access-method choice as a hardware-purchasing argument is the paper's real rhetorical weapon.

How it works — the mechanism, concretely

Insert path: log first, then C0

A new History row first writes an ordinary transactional insert record to the sequential log file, exactly as it would anyway; no special index log is created. The index entry then goes into C0, the memory-resident component, at zero I/O cost. C0 need not resemble a B-tree because it never sits on disk, so nodes can be any size and a (2-3) tree or an AVL tree is appropriate - there is no reason to sacrifice CPU efficiency to minimize depth. When C0 reaches its threshold size, a leftmost contiguous run of entries is deleted from it in a single batch and handed to the rolling merge, with the tree rebalanced once after the batch rather than after each individual entry delete.

Anatomy of a merge step

The cursor holds an inner-component position in Ci-1 and an outer-component position in Ci, at the leaf level and at every directory level along the access path. A multi-page block of Ci leaves is read into an emptying block buffer; entries are merged with the incoming run and written left to right into a filling block buffer, and when that block is packed it is written to a new free area on disk rather than over the old block. Parent directory nodes in Ci are updated in buffer to point at the new leaves, and the old leaves are invalidated and dropped from the directory. Leftovers are normal: a merge step rarely empties an old node just as a new one fills, so partially full nodes and blocks persist in buffer and the structure is designed to tolerate them. In the fully general case, where some entries are deliberately retained in Ci-1, there is an emptying and a filling block on both the inner and the outer side, so four nodes are in play at once.

Disk layout and the find path

Every disk component is built from page-sized nodes in a B-tree-shaped directory, except that runs of nodes in key order below the root sit together on multi-page blocks, and the directory records which node sequence occupies which block so an entire block can be read or written in one I/O. Directory nodes are forced to new disk positions when their multi-page block buffer fills, when the root splits and deepens the tree, or when a checkpoint is taken. An exact-match find descends single-page nodes only, avoiding block reads to keep buffering cheap, while long range retrievals use block reads. A find searches C0, then C1, and so on out to CK, so in the general case it must touch every component - typically one extra page I/O per disk component relative to a B-tree, and the paper prices this at about $6,400 of directory buffering saved but one extra read incurred.

Stopping a find early

The paper gives three ways to avoid searching every component. If uniqueness is guaranteed by how values are generated - distinct timestamps, for instance - the search terminates as soon as a match appears in an early Ci. If the find criterion references recent timestamps, the entries sought cannot have migrated out to the largest components yet. And the merge can deliberately retain entries inserted in the last tau_i seconds inside Ci rather than pushing them outward, so by recording transaction start times the system can guarantee that all logs for a transaction begun within the last tau_0 seconds are still in C0, with no disk access at all - which makes C0 serve as a genuine buffer for recent data, exactly the property that makes UNDO-log indexes cheap.

Sizing the components

Given a steady insert rate R bytes per second and page size Sp, each disk component Ci contributes ri.R/Sp page reads for the merge into it, (ri+1).R/Sp page writes for that same merge, and R/Sp page reads for the merge out of it, summing to H = (2R/Sp) times (sum of ri, plus K - 1/2). Minimizing this subject to the product of the ri being SK/S0 forces all ri equal, so component sizes form a geometric progression. Total cost is COSTm.S0 + max(COSTd.S1, COSTpi.H): shrinking S0 trades expensive memory for cheap disk until the arms saturate, after which further shrinkage forces the data across more spindles and cost rises again. For two components the optimum follows s = t while t is at most 1 and s = the square root of t beyond, giving a minimum cost of 2 times the square root of (COSTm.S1)(2.COSTpi.R/Sp) - which grows as the square root of R where the B-tree grows linearly in R.

Concurrency

Nodes are the unit of locking. Three physical conflicts must be mediated: a find touching a node that a rolling merge is rewriting; a find or insert into C0 touching the range being merged out to C1; and a faster inner cursor needing to pass a slower outer cursor, since migration out of Ci-1 is always at least as fast as migration out of Ci. Nodes under merge are write-locked, finds read-lock nodes on their access path and release them as soon as the leaf entries have been scanned. In the general case the cursor write-locks four nodes at once - inner and outer emptying nodes, inner and outer filling nodes - and releases them each time an emptying node in the outer component is fully depleted, and that quantized release is exactly the window that lets one cursor overtake another; the bypassed cursor's inner position is invalidated and must be reoriented. In C0 the locking depends on the structure chosen, for example write-locking the subtree under one (2-3) directory node covering the merge range. The paper deliberately restricts itself to this lowest level of multi-level locking and leaves key-range locking and phantoms to others.

Checkpoint and recovery

Recovery reuses the ordinary transactional insert logs as logical logs from which index entries can be reconstructed, at the cost of retaining those logs a little longer before storage reclamation. At a checkpoint taken at time T0 the system finishes all in-flight merge steps so node locks are released, pauses new inserts, writes C0 to a known disk location, flushes every dirty buffered node of the disk components, and then writes a checkpoint log holding LSN0 of the last indexed row, the disk addresses of all component roots, the position of every merge cursor, and the current dynamic multi-page block allocation state. Restart reloads C0 and the buffered blocks, replays logs after LSN0 into C0, and restarts the rolling merges. This is safe because merged blocks always go to new disk positions, so nothing needed for recovery is ever overwritten - old information is only invalidated once newer writes succeed. Emptying blocks and newly created nodes are assigned new disk addresses immediately and their parent directory pointers corrected in buffer, so a checkpoint never stalls waiting on I/O to fix directories.

What the paper showed — measurements and proofs

Two independent disk measurements put the block-to-random page cost ratio COSTpi/COSTP at about 1/10: a 1989 IBM analysis of DB2 on 3380 disk gives about 20 ms for a single random page read against about 2 ms per page for a 64-page sequential prefetch, and a SCSI-2 4 KByte read gives 16 ms random against 95 ms for 64 contiguous pages, about 1.5 ms per page.
With 1995 workstation prices of COSTm = $100/MByte, COSTd = $1/MByte, COSTP = $25 per page-per-second and COSTpi = $2.50, the freezing point is 0.04 and the boiling point 4 I/Os per second per MByte, and the Five Minute Rule reference interval computes to tau = 62.5 seconds per I/O for a 4 KByte page.
The insert cost ratio K1 times COSTpi/COSTP times 1/M, with K1 about 0.67 for these index sizes, typically yields an improvement of nearly two orders of magnitude; with 16-byte entries, 200 entries per page and C1 forty times the size of C0, the batch parameter M works out to 5.
Example 3.3, at R = 16,000 bytes per second over a 9.2 GByte index: a B-tree costs $50,000 in disk arms for 2,000 random I/Os per second plus $6,400 of memory to buffer the level above the leaves, a total of $56,400, while a two-component LSM-tree with r = 460 and a 20 MByte C0 costs $9,200 of disk plus $2,000 of memory plus $200 of merge buffers, a total of $11,400.
Example 3.4, at ten times that insert rate: the B-tree needs 500 GBytes of disk purely to supply 20,000 random I/Os per second, 491 GBytes of it unused, for $506,400; the best two-component LSM-tree costs $27,200 with 13.5 GBytes of disk and 135 MBytes of memory; a three-component tree with r = 23, a 400 MByte C1 and a 17 MByte C0 costs $11,300.
Theorem 3.1 proves that with SK, S0 and R fixed the total merge page I/O rate H = (2R/Sp)(K(1+r) - 1/2) is minimized exactly when all adjacent size ratios are equal; Theorem 3.2 gives the recurrence rK-1 = rK + 1, rK-2 = rK-1 + 1/rK-1, and so on when the total size S is held fixed instead, and the paper notes the two agree closely because useful values of r are 20 or more.

Limits and trade-offs — conceded and discovered

The paper concedes that finds requiring immediate response lose I/O efficiency: a lookup must in general search every component, costing roughly one extra page I/O per disk component, so the LSM-tree is only appropriate where inserts greatly outnumber retrievals - which the authors argue is typical of History tables and log files.
The paper concedes a hard practical ceiling on the number of components. Each extra component adds CPU cost for another rolling merge and memory for its merge buffers, which will actually swamp the memory cost of C0 in common cost regimes, and adds one more component to every find; the benefit runs out once r falls to e = 2.71, and the authors conclude that three components are probably the most that will be seen in practice.
The paper concedes that its cost analysis is insert-only: all disk I/O capacity is assigned to the rolling merge, deletions before component CK are ignored, and balancing find traffic against merge traffic is explicitly listed as future work.
The paper concedes that a checkpoint imposes a possibly large pause while C0 and all dirty buffers are written, that cursor-bypass reorientation and the merge algorithms for higher directory levels are left for later work, and that no formal correctness proof and no implementation existed at publication - the entire case is analytic, with no measured system.
Later work exposed what the paper did not model. There is no Bloom filter in the LSM-tree design itself (filters appear only in the discussion of Differential Files), so multi-component point lookups really did touch every level until LevelDB and RocksDB added per-table filters; and the write, read and space amplification of compaction, together with the tail-latency spikes it causes, became the dominant engineering problem for production LSM engines, driving the leveled-versus-tiered debate and tuning work such as bLSM, Monkey and Dostoevsky.

What it became — the systems that inherited it

The LSM-tree became the default storage structure for write-heavy systems, and its vocabulary is now the vocabulary of an entire industry. Google's Bigtable is the canonical instantiation: a memtable playing the role of C0, immutable SSTables playing the disk components, a commit log for recovery, and minor, merging and major compactions playing the rolling merge. LevelDB and then RocksDB turned that into a reusable embedded engine and made Theorem 3.1 operational - leveled compaction with a fixed size ratio between adjacent levels, ten by default, is exactly the geometric progression the paper proved optimal - while adding per-table Bloom filters to blunt the find penalty the paper had conceded. Apache HBase and Apache Cassandra inherited the design through Bigtable and Dynamo, and it spread on into ScyllaDB, InfluxDB's TSM engine, MongoDB's WiredTiger LSM option, and CockroachDB and TiDB via RocksDB and Pebble; Lucene's segment merging is a close cousin. The paper's cost framing outlived its hardware: swap disk arms for SSD write endurance and the same argument produces the write-amplification analyses that drive modern compaction research and the RUM conjecture's read-update-memory trade-off triangle. Even the name generalized - LSM-tree today names a whole design family rather than the specific two- and three-component structures the paper actually analyzed.

In the paper’s words — verbatim

“The LSM-tree uses an algorithm that defers and batches index changes, cascading the changes from a memory-based component through one or more disk components in an efficient manner reminiscent of merge sort.”

Abstract

“The idea of always writing multi-page blocks to new locations was inspired by the Log-Structured File System devised by Rosenblum and Ousterhout [23], from which the Log-Structured Merge-tree takes its name.”

§2.1

“In these cases, the data is hot in terms of logical access rate (inserts/sec) but only warm in terms of physical disk access rate because of the batching effect of the LSM tree.”

§6

Vocabulary — as this paper uses it

LSM-tree: A disk-based index composed of two or more tree-like components of increasing size, C0 through CK, where C0 is memory resident and all others are disk resident, with entries migrating outward through rolling merges.
C0 component: The memory-resident smallest component, which absorbs every insert at zero I/O cost. It need not be a B-tree since it never sits on disk; the paper suggests a (2-3) tree or an AVL tree.
C1 component: The disk-resident larger component. It has a B-tree-like directory, but its nodes are 100 percent full and node sequences below the root are packed into contiguous multi-page blocks for efficient arm use.
Rolling merge: The continuous background process in which a conceptual cursor circulates through matching key ranges of two adjacent components in quantized merge steps, pushing entries outward and wrapping back to the smallest key when it reaches the largest.
Multi-page block: A contiguous run of page-sized nodes, envisioned at about 256 KBytes, read or written as a single unit so that seek time and rotational latency are amortized over roughly 64 pages.
Emptying block and filling block: The pair of buffers straddling the merge cursor at each level: the emptying block holds old nodes the cursor has not yet reached, the filling block accumulates merged output until it is full enough to be written to a fresh disk position.
Batch-merge parameter M: The average number of C0 entries merged into each single-page C1 leaf node during the rolling merge, equal to (Sp/Se) times S0/(S0+S1). It is the batching half of the LSM-tree's cost advantage over a B-tree.
Data temperature (H/S): Page accesses per second per megabyte of stored data. Below the freezing point Tf = COSTd/COSTP data is capacity limited; above the boiling point Tb = COSTm/COSTP it should be memory resident; the LSM-tree works by lowering an index's effective temperature.
Continuum Structure: The paper's name for any access method that immediately places a newly inserted entry in its ultimate collation order among all existing entries. B-trees, SB-trees, Bounded Disorder files and extendible hashing all qualify, and all therefore need at least two I/Os per insert.

On the timeline — where this sits in the story

Year1996

MilestoneLog-Structured Merge Tree (LSM-tree)

Problem solvedTraditional disk indexes were inefficient for high-write workloads because random in-place updates were expensive.

How it solved itLSM-trees batch writes in memory and merge sorted components over time, trading write efficiency against controlled read amplification.

Why it matteredBecame foundational for Bigtable, Cassandra, HBase, LevelDB, RocksDB, and many key-value stores.

DDIACh. 4: Storage & Retrieval

View on the timeline