B-Trees vs LSM Trees: How Databases Choose Between Reads and Writes

Two databases can expose almost identical put, get, and range APIs while behaving completely differently under load. One slows down as random writes hit storage. Another accepts writes quickly, then spikes during compaction.

The difference often starts with the storage structure: B-tree or LSM tree.

The Problem Both Solve

A database needs to keep keys sorted so it can support:

point lookup:     find key = 42
range scan:       find keys from 100 through 200
ordered output:   return rows by key
updates:          replace or delete a value

Keeping one giant sorted file would make reads easy and writes terrible. Inserting a key near the beginning could require rewriting everything after it.

B-trees and log-structured merge trees avoid that rewrite in different ways.

B-Trees: Update Sorted Pages

A B-tree stores many keys in each fixed-size page and keeps the tree shallow.

                 [40 | 80]
                /    |     \
       [10 20 30] [45 60] [90 100 120]

A lookup starts at the root, chooses a child range, and repeats until it finds the leaf page. Because each page holds many keys, a tree containing millions of rows may be only three or four levels deep.

When a page fills, it splits:

before: [10 20 30 40 50 60]

after:  [10 20 30]  [40 50 60]
                  ↑ parent gains a separator

PostgreSQL's default index type and many relational database indexes use B-tree variants because they provide predictable point lookups and efficient ordered range scans.

What a B-Tree Write Costs

Updating one row can involve:

Write the change to a durability log
Find and modify the relevant data or index page in memory
Eventually flush the dirty page to storage
Split or rebalance a page if necessary

Even a tiny logical update may cause a full page write. Random key updates also scatter I/O across the data set. Caches hide much of this when the working set fits in memory.

B-trees tend to provide stable read latency because the newest value lives in one logical place. They pay more of the organization cost near write time.

LSM Trees: Buffer, Flush, Merge

An LSM tree turns random writes into sequential writes.

write
  ↓
write-ahead log (durability)
  ↓
memtable (sorted in memory)
  ↓ when full
immutable SSTable on disk
  ↓ over time
compaction merges SSTables

The in-memory memtable may be a skip list or balanced tree. When full, it becomes an immutable sorted-string table (SSTable) on disk. New writes go to a new memtable while background compaction combines files and discards overwritten or deleted entries.

Appending a log and later writing one sorted file is friendly to storage. This is why LSM-based engines are attractive for write-heavy workloads.

Reads Search Multiple Places

The latest value may be in the active memtable, an immutable memtable waiting to flush, or one of several SSTables.

get("user:42")
  1. check active memtable
  2. check immutable memtable
  3. check newest relevant SSTable
  4. check older levels until found

Engines use indexes, block caches, and Bloom filters to avoid reading every file. A Bloom filter can say a file definitely does not contain the key, skipping an I/O.

Point reads can still be fast, but their behavior depends heavily on cache hit rate, file layout, and compaction health.

Deletes Become Tombstones

SSTables are immutable, so an LSM engine cannot immediately remove an older key from an existing file. It writes a deletion marker—a tombstone.

older SSTable: user:42 = Alice
newer SSTable: user:42 = <tombstone>

Reads see the newer tombstone and treat the key as absent. A later compaction can discard both the tombstone and values it covers, once the engine knows no older copy can reappear.

Large numbers of tombstones can increase read work and disk use until compaction catches up.

Compaction Is the Deferred Bill

LSM writes are cheap partly because organization happens later. Compaction reads existing SSTables, merges sorted streams, and writes new SSTables.

That creates three amplification effects:

write amplification — one logical byte is rewritten multiple times
read amplification  — a lookup may consult multiple structures
space amplification — old and new files coexist during compaction

If incoming writes exceed sustainable compaction throughput, pending work grows. Eventually the engine throttles writes or runs out of disk.

Monitor compaction backlog, bytes pending, stall duration, cache hit rate, and disk headroom—not just request latency.

Leveled vs Size-Tiered Compaction

Common strategies make different trade-offs.

Leveled compaction keeps sorted, mostly non-overlapping files at each level. Reads examine fewer files and space amplification is controlled, but data may be rewritten frequently as it moves through levels.

Size-tiered compaction merges files of similar size. It usually writes less during ingestion, but overlapping key ranges can make reads and temporary disk usage more expensive.

Engine defaults are not universally optimal. A write-heavy event stream and a read-heavy metadata store want different compaction behavior.

Practical Comparison

                         B-tree             LSM tree
point reads              predictable        fast with good filters/cache
range scans              excellent          good, merges multiple sources
random writes            page-oriented      buffered and sequential
background maintenance   page cleanup       compaction is fundamental
write amplification      page + log writes  repeated compaction
read amplification       tree depth         memtables + SSTable levels
space spikes             moderate           compaction needs headroom

This table describes tendencies, not benchmark results. Implementations matter enormously. Storage hardware, cache size, key distribution, value size, compression, and durability configuration can reverse a simplistic comparison.

Choosing in Practice

Choose based on the database as a whole, not the data structure in isolation.

A B-tree-based relational database is often a strong fit when you need transactions, joins, constraints, varied queries, and predictable indexed reads.

An LSM-based key-value or wide-column store is often a strong fit when writes are heavy, access is mostly by known keys or key ranges, and the system can dedicate I/O and disk headroom to compaction.

Do not migrate because a benchmark says LSM writes are faster. Test your read/write ratio, key and value sizes, deletion patterns, working set, durability mode, and p99 latency during compaction.

The Bottom Line

B-trees organize data as writes happen. LSM trees buffer writes and organize data through background merging.

The rules:

Expect B-trees to excel at predictable point and range reads
Expect LSM trees to excel at turning random writes into sequential I/O
Remember that LSM compaction pays the deferred organization cost
Budget disk space for compaction and tombstones
Watch amplification and tail latency, not just operations per second
Treat cache and Bloom filters as part of LSM read performance
Benchmark the complete database with your real workload

There is no free storage layout. The real choice is when, where, and how often you want to pay for keeping data ordered.