Every database that stores data on disk has to answer the same question: how should the data be laid out so that reads and writes are both reasonably fast? There is no structure that is optimal at both, so database engineers have converged on two dominant answers. B-trees, refined for decades, keep data sorted on disk so that reads are cheap and predictable. Log-structured merge-trees (LSM-trees), introduced in a 1996 paper by Patrick O’Neil and co-authors, instead buffer writes in memory and write them out in large sequential batches, trading some read performance for dramatically cheaper writes. Almost every database you’ve heard of picked one of these two, and the choice shapes everything else about how it behaves under load.
At a Glance
| Dimension | B-Tree | LSM-Tree |
|---|---|---|
| Write pattern | In-place, random page updates | Append-only, sequential batches |
| Read pattern | Single tree descent, generally fast | May check memtable plus multiple on-disk levels |
| Optimized for | Read-heavy / balanced workloads | Write-heavy, high-ingest workloads |
| Background cost | Page splits, occasional rebalancing | Compaction (merging and rewriting sorted files) |
| Typical use cases | OLTP tables, general-purpose relational storage | Time-series data, logging, event streams, high-write-rate key-value stores |
| Real systems | PostgreSQL, MySQL/InnoDB, SQLite | RocksDB, LevelDB, Apache Cassandra |
How B-Trees Work — and Why They’re Read-Optimized
A B-tree is a balanced, multi-way tree. PostgreSQL’s own documentation describes its B-tree index as organized into levels that can each be traversed as a doubly linked list of pages, with a fixed metapage at the start of the index and leaf pages — which make up over 99% of all pages in practice — holding the tuples that point back to table rows. Internal pages hold “downlinks” to the level below. When a leaf page fills up, it splits in two and a new downlink is inserted into its parent; if the root itself has to split, the tree gains a new level. This is the mechanism that keeps the tree balanced: height only grows when the root splits, so every leaf stays the same distance from the root.
SQLite’s file format documentation describes the same balance property from a different angle: an interior b-tree page’s children are all required to be at the same depth, which is what keeps lookups to a predictable number of page reads. MySQL’s InnoDB storage engine likewise clusters table rows directly in the leaf pages of a B-tree keyed on the primary key (its “clustered index”), with secondary indexes stored as separate B-trees that point back to that primary key.
Because the tree stays sorted and balanced at all times, a lookup, a range scan, or an ORDER BY can walk directly from the root to the relevant leaf in a small, predictable number of I/Os. PostgreSQL’s documentation on index types notes that B-tree indexes handle not just equality but also range comparisons, BETWEEN, IN, and sorted output, which is why B-tree is the default index type for CREATE INDEX. The cost of that convenience shows up on the write side: inserting or updating a row means finding the correct leaf page and modifying it in place, which the original LSM-tree paper describes as costing “about two random disk I/Os” for an index on a table growing quickly — a cost that accrues continuously as more pages fill up and split.
How LSM-Trees Work — and Why They’re Write-Optimized
The log-structured merge-tree was introduced by Patrick O’Neil, Edward Cheng, Dieter Gawlick, and Elizabeth O’Neil in a 1996 paper in Acta Informatica, motivated by exactly the write-cost problem above: on a file experiencing a high rate of inserts, maintaining a B-tree index in real time could push total system I/O cost up by as much as 50%. Their fix was to stop updating the on-disk structure immediately and instead defer and batch those updates.
The paper’s design uses multiple components of increasing size. The smallest, C0, is “entirely memory resident,” so new entries can be inserted with no disk I/O at all. In modern systems such as RocksDB this component is called the memtable — RocksDB’s own wiki describes it as an in-memory, skiplist-based structure that absorbs every write, and which becomes read-only (immutable) once it reaches a size threshold (64MB by default), at which point a new memtable takes over and a background thread flushes the full one to disk as an SST file, RocksDB’s on-disk sorted-string table format — the modern descendant of the paper’s larger, disk-resident C1 component.
Once data lands on disk as immutable sorted files, it has to be kept under control, because a lookup may otherwise have to check every file ever flushed. This is done by compaction: a background process that merges sorted files together, drops overwritten or deleted entries, and writes the result out as new, larger sorted files. The original paper calls this a “rolling merge,” carried out by a cursor that circulates through the key range, moving entries from the smaller component into the larger one; because the merge writes to new disk locations, the old blocks remain valid until the merge’s trailing edge frees them, which keeps crash recovery simple. RocksDB’s compaction documentation describes the same idea in modern terms: in its default “leveled” compaction style, level 0 holds the newest flushed data, and each level below is progressively larger and older, with compaction merging data from one level into the next.
Here is a simplified sketch of the merge step at the heart of compaction — merging several sorted runs into one, keeping only the newest version of each key:
function compact(sorted_runs):
# sorted_runs: list of sorted (key, value, sequence_number) iterators,
# newest run first
output = []
heap = min-heap of (key, run_index) seeded with each run's first entry
while heap is not empty:
key, run_index = heap.pop_min()
entry = sorted_runs[run_index].current()
# keep only the newest version of this key across all runs
if entry.sequence_number is the highest seen for `key`:
if not entry.is_tombstone:
output.append(entry)
# else: deletion marker, drop the key entirely
advance sorted_runs[run_index]
skip any further entries in other runs that still match `key`
if sorted_runs[run_index] has more entries:
heap.push(sorted_runs[run_index].current().key, run_index)
write output as one new sorted fileBecause every write — insert, update, or delete — is just an append to the current memtable and, eventually, a sequential write during flush or compaction, LSM-trees turn expensive random-page writes into cheap sequential ones. The cost shows up later and in the background, during compaction, rather than synchronously on every write.
Write Amplification vs. Read Amplification
The trade-off between these two designs is usually described with two terms: write amplification (how many times a byte of data gets physically rewritten before it settles) and read amplification (how many places a read might have to check before it finds the right version of a key).
B-trees have low write amplification per logical write in the sense that only the affected leaf (and occasionally its ancestors, on a split) is touched — but each of those touches is a random I/O, and the original LSM-tree paper’s whole argument is that on a fast-growing index this random-I/O cost dominates. Reads, by contrast, are cheap: one descent from root to leaf.
LSM-trees push that cost around. Writes are sequential and batched, so they’re fast, but the same piece of data can be rewritten multiple times as it’s compacted from one level to the next — RocksDB’s compaction documentation states this directly, noting that its default leveled compaction style has “higher write amplification” because data is rewritten at each level, while its alternative “universal” (tiered) style minimizes write amplification at the cost of higher read and space amplification, because more separate sorted runs have to be kept and checked. Apache Cassandra’s documentation makes the same point about its own LSM-based storage engine: compaction “causes write amplification, meaning data is rewritten multiple times,” which it frames as the explicit cost of a write-optimized design, offset by Bloom filters that let reads skip files that can’t contain a given key. A read against an LSM-tree, in the worst case, has to check the memtable and then every relevant on-disk level until it finds the key (or confirms it’s absent) — the 1996 paper notes plainly that “LSM-tree finds of three or more components suffer somewhat in performance, typically by one extra page I/O per disk component.”
B-Trees vs. LSM-Trees: Side by Side
| Factor | B-Tree | LSM-Tree |
|---|---|---|
| Write cost | Random I/O per update; costly under high insert rate | Sequential, batched; cheap per write, cost deferred to compaction |
| Read cost | One predictable tree descent | May touch memtable plus several on-disk levels/files |
| Space overhead | Pages kept partially full to allow inserts (InnoDB reserves ~1/16 of each page) | Stale/overwritten versions linger until compaction reclaims them |
| Background work | Occasional page splits/merges | Continuous compaction merging sorted files |
| Update-in-place | Yes, row is modified where it lives | No, new version appended; old version removed later by compaction |
| Best fit | Mixed read/write OLTP workloads | Write-heavy / high-ingest workloads tolerant of eventual background cost |
Which Real Databases Use Which
The split between the two designs is visible across the industry’s best-known systems.
- PostgreSQL uses a B-tree as the default index type for CREATE INDEX, per its own documentation, handling equality, range comparisons, and sorted retrieval.
- MySQL (InnoDB) stores table rows directly inside a B-tree clustered on the primary key, with secondary indexes as separate B-trees pointing back to it, as described in MySQL’s own InnoDB documentation.
- SQLite stores every table and index as a B-tree on disk — a “table b-tree” keyed by rowid holding the actual row data, and “index b-trees” for secondary indexes — as laid out in SQLite’s file format documentation.
- RocksDB, Meta’s embedded key-value store, is explicitly built as a log-structured merge-tree: writes land in an in-memory memtable and a write-ahead log, and are later flushed and compacted into on-disk SST files, per its own wiki documentation.
- LevelDB, the Google-originated key-value library RocksDB was forked from, uses the same memtable/SSTable/compaction design.
- Apache Cassandra documents its storage engine as explicitly “based on Log Structured Merge (LSM) trees,” using an append-only commit log, memtables, and SSTables merged by background compaction.
Several other widely used systems (such as HBase and ScyllaDB) also use LSM-tree-based storage engines, though this article focuses on the sources verified above.
Bottom Line
Neither design is objectively better — they optimize for opposite failure modes. A B-tree keeps data sorted on disk at all times, so reads stay fast and predictable, at the cost of expensive random writes as the tree grows; that’s the right trade-off for general-purpose relational tables and anything read-heavy. An LSM-tree defers that cost by buffering writes in memory and flushing them as large sequential batches, accepting slower and more variable reads (and ongoing compaction overhead) in exchange for write throughput that can be an order of magnitude higher; that’s the right trade-off for logging, time-series ingestion, and other high-write-rate workloads. Many modern systems don’t pick just one globally — some let you choose a storage engine per table or per workload — but understanding which cost each structure defers, and to where, is what makes that choice make sense.
FAQ
Is an LSM-tree always faster than a B-tree?
No. It’s faster for writes because it turns random writes into sequential ones, but reads can be slower because a lookup may have to check the memtable plus multiple on-disk levels, and compaction adds background I/O. The 1996 paper that introduced the structure says this plainly: lookups “will lose I/O efficiency in some cases” compared to a B-tree.
What is compaction, in one sentence?
It’s the background process that merges multiple sorted on-disk files into fewer, larger ones, discarding obsolete or deleted entries so reads don’t have to check an ever-growing number of files.
Why do B-trees reserve empty space in their pages?
So that later inserts and updates can be absorbed without an immediate page split. MySQL’s InnoDB documentation notes it tries to keep about 1/16 of each clustered index page free by default for this reason.
Can a database use both structures?
Yes, at the system level. Several databases support multiple storage/index engines, and an application can mix a B-tree-backed relational database with an LSM-based key-value store for different parts of the same system, choosing per workload.
Does “sorted string table” (SSTable) mean the same thing as the original paper’s “C1 component”?
Conceptually yes — both are immutable, sorted, disk-resident structures that hold the bulk of the data and are produced and merged by batch processes. SSTable is the specific file format used in LevelDB, RocksDB, Cassandra, and similar systems; the term predates the original paper’s exact terminology but implements the same core idea.
Sources
- O’Neil, Cheng, Gawlick, O’Neil, “The Log-Structured Merge-Tree (LSM-Tree),” Acta Informatica, 1996 (PDF)
- RocksDB Wiki: MemTable
- RocksDB Wiki: Compaction
- RocksDB Wiki: RocksDB Basics
- PostgreSQL Documentation: B-Tree Indexes (Implementation)
- PostgreSQL Documentation: Index Types
- SQLite Documentation: Database File Format (B-tree structure)
- MySQL Documentation: InnoDB Physical Structure
- Apache Cassandra Documentation: Storage Engine
Discover more from Software Online Review
Subscribe to get the latest posts sent to your email.
