B+Tree and LSM-Tree indexes differ in how they apply index changes to storage. A B-tree is the traditional comparison point discussed by the original LSM paper; an LSM-Tree stages changes in a memory component and later merges them into one or more disk components. Neither design is universally faster. The useful choice depends on the balance of inserts, deletes, and retrievals, the need for immediate lookup responses, and the cost of moving data between components.

Concept illustration comparing a page-based B+Tree index with LSM-Tree memory and disk components

The workload question in the original paper

Patrick O’Neil, Edward Cheng, Dieter Gawlick, and Elizabeth O’Neil frame the problem around indexing a rapidly growing history table. The paper’s abstract identifies the cost of maintaining a conventional disk-based index such as a B-tree as records are inserted. It presents the Log-Structured Merge-Tree as a way to defer and batch index changes, cascading them from a memory component through disk components. The design target is a workload with a high rate of inserts and deletes, where repeatedly maintaining a conventional index can consume substantial disk I/O.

That motivation is not a promise of free writes. An LSM-Tree first places an index entry in a smaller memory-resident component; the entry later migrates into a larger disk-resident component. The paper describes lookup as checking the components and says index values remain available during merging, apart from short locking periods. It also explicitly cautions that indexed finds requiring an immediate response can lose I/O efficiency in some cases. A fair comparison therefore cannot reduce the claim to “LSM writes are always fast” or “LSM reads have no extra latency.”

What the two structures do, and what the evidence does not establish

The paper’s two-component description makes the LSM change path concrete. A new history-row index entry is added to the memory-resident C0 component. A rolling merge then moves entries into the disk-resident C1 component. Searches can find entries in either component. The authors compare the merge process to merge sort and describe deferring the final placement of index entries rather than making each change immediately at its ultimate disk location. This is the core idea supported by the paper; the exact topology and tuning of a modern engine may differ.

The same paper uses B-tree as the conventional alternative for its history-index example. It calculates I/O costs for a particular benchmark scenario with randomly chosen account keys and a large accumulated history index. Those figures explain the paper’s motivation; they are not universal measurements for present-day B-tree implementations, storage devices, buffer pools, or workloads. The cited sources also do not establish universal page sizes, a fixed tree height, or a rule that every B-tree update must rewrite an entire disk page. Such details need evidence from the documentation of the specific engine being considered.

This limitation matters when discussing products. The specialist source available for this comparison documents RocksDB’s leveled-compaction policy. It does not support classifying ClickHouse or a broad list of database products as LSM-Tree systems. Product names should not substitute for checking the documented storage engine or table type in the relevant product’s own materials.

A RocksDB example of compaction trade-offs

RocksDB’s “Leveled Compaction” page illustrates one concrete way an LSM implementation can trade write work for a different read path. It says that too many L0 files hurt read performance for many queries. RocksDB may compact some L0 files together into a larger file; the page describes this as adding write amplification while potentially improving L0 read amplification. The same discussion distinguishes this additional cost from the larger write amplification often associated with leveled compaction generally.

Practitioner perspective: test the workload, not the label

The original authors’ stated fit—an index workload in which inserts are more common than retrieval finds—provides a testable starting hypothesis. First record the proportions of inserts, deletes, point lookups, and range retrievals, along with the required response time for each. Check whether the current workload actually resembles the high-update history-table case in the paper. If a system requires immediate lookup responses, the paper’s warning about possible I/O inefficiency should remain part of the evaluation even when the write rate is high.

The evidence has boundaries. The LSM paper analyzes a 1990s disk-cost model and a specific history-table example. Its saved PDF identifies itself as “To be published,” so this copy does not establish a publication date. The RocksDB wiki describes one implementation’s leveled-compaction behavior. Together they support the design rationale and a concrete RocksDB trade-off, but they do not rank current commercial products or predict modern device performance. Use them to form a workload hypothesis, then validate that hypothesis on the engine and storage actually under consideration.

Sources