B-Trees vs LSM Trees: Why Databases Store Data Differently

The short answer

Quick answer: Databases use two main families of storage engine. A B-tree keeps data sorted in fixed-size pages and updates those pages in place. It gives fast, predictable reads and is the default in PostgreSQL, MySQL, SQLite and most relational databases. An LSM tree (log-structured merge-tree) never updates in place. It collects writes in memory, flushes them to disk as immutable sorted files, and merges those files in the background. It gives very fast writes and good compression and is used by RocksDB, Cassandra, ScyllaDB and LevelDB. B-trees favour reads; LSM trees favour writes.

B-trees: update in place

A B-tree stores sorted keys in pages arranged as a shallow tree, as described in how database indexes work. To write:

1. Walk down the tree to the leaf page where the key belongs.
2. Modify that page.
3. If the page is full, split it in two and update the parent.

Each write changes a page that already exists somewhere on disk, so writes land at effectively random locations. To stay safe across crashes, the change is first recorded in a write-ahead log, then applied to the page. So the data is written at least twice.

Strengths: each key lives in exactly one place. A read follows one path from root to leaf, typically three or four pages, most of them cached. Performance is steady and well understood after decades of use.

Weaknesses: random page writes were painful on spinning disks, and pages are usually only partly full, leaving wasted space.

LSM trees: never update in place

An LSM tree turns random writes into sequential ones. The RocksDB overview describes a typical design.

The write path

1. Append to the log. The write is added to a write-ahead log for crash safety.
2. Insert into the memtable. The write also goes into a sorted in-memory structure. The write is now complete, which is why LSM writes are so fast.
3. Flush. When the memtable fills, it is written to disk as an SSTable (sorted string table): an immutable file of sorted key-value pairs. A new memtable takes over.

Updates and deletes are just more writes. An update adds a newer version of the key. A delete adds a marker called a tombstone. Old versions are cleaned up later.

The read path

A key could be in the memtable or in any of several SSTables, so a read checks the newest data first and works backwards until it finds the key. To avoid opening every file, each SSTable has:

• A Bloom filter: a small probabilistic structure that can say "this key is definitely not in this file". Most files are skipped without touching disk.
• A sparse index of key positions within the file.

Compaction

Left alone, SSTables would pile up, reads would slow down, and deleted data would never be freed. Compaction merges SSTables in the background: it combines sorted files, keeps only the newest version of each key, drops tombstoned data, and writes out new, larger files.

There are two common strategies:

Compaction is the price of the LSM design. It consumes CPU and disk, and if it falls behind, writes may be throttled or stall.

The three amplifications

Storage engines are often compared on three ratios:

• Write amplification: bytes written to storage per byte of user data. B-trees rewrite whole pages for small changes; LSM trees rewrite data repeatedly during compaction.
• Read amplification: storage reads per query. Low for B-trees; higher for LSM trees.
• Space amplification: disk used relative to the logical data size. B-trees carry partly empty pages; LSM trees carry not-yet-compacted old versions.

No design minimises all three at once. Tuning an engine means choosing which to sacrifice.

How SSDs changed the picture

LSM trees were designed when random writes on spinning disks were extremely slow. SSDs made random I/O cheap, as covered in why SSDs are faster than HDDs, which narrowed the gap.

But LSM trees remain attractive on flash: their files compress well, saving expensive SSD capacity, and their sequential, lower-volume writes can reduce wear. Meta built MyRocks, a MySQL engine on RocksDB, largely for space savings.

Which should you choose?

Most of the time you do not choose directly; you choose a database, and the engine comes with it.

Many distributed and NoSQL databases use LSM trees because their workloads are write-heavy. Several distributed SQL databases build their SQL layer on top of an LSM key-value store.

The lines also blur. PostgreSQL is not a pure in-place engine: an update writes a new row version and leaves the old one for a background process (vacuum) to remove, a little like compaction.

Frequently asked questions

Why are LSM trees faster for writes?

A write only appends to a log and inserts into memory. Disk writes happen later, in large sequential batches, with no need to find and modify an existing page first.

What is an SSTable?

A sorted string table: an immutable file of key-value pairs sorted by key, with an index and usually a Bloom filter.

What is compaction?

The background process that merges SSTables, discarding overwritten and deleted entries so reads stay fast and space is reclaimed.

Do relational databases ever use LSM trees?

Yes. MyRocks for MySQL and several distributed SQL systems store their tables in LSM-based key-value engines.

Conclusion

B-trees and LSM trees answer the same question, how to keep sorted data on disk, with opposite strategies. B-trees do the work at write time to keep each key in one tidy place. LSM trees make writes cheap and defer the tidying to background compaction. Knowing which your database uses explains its performance profile, its tuning knobs and its bad days.

Related articles

• How a Database Index Makes Queries 1000x Faster
• How Write-Ahead Logs Prevent Data Loss During Crashes
• Why SSDs Are Faster Than HDDs, Explained From the Hardware Up
• SQL vs NoSQL: When to Use Which (Beyond the Hype)

Sources and further reading

• RocksDB Overview
• Log-structured merge-tree (Wikipedia)
• B-Tree Indexes, PostgreSQL documentation