B-tree vs LSM Tree

Interactive comparison of two fundamental storage engine data structures. B-trees optimize for reads with in-place updates. LSM trees optimize for writes with append-only operations.

Interactive Simulation

Watch how the same operations behave differently in each structure. Click Demo to run the default scenario, or use individual operation buttons.

Speed:800ms
View:
Operations:

B-tree

Order: 3Height: 0Nodes: 0
Empty tree
Reads
0
Writes
0
Splits
0
Merges
0

LSM Tree

Memtable: 0/4Levels: 3
WAL
empty
Memtable
empty
L0
empty
L1
empty
L2
empty
WAL Writes
0
Flushes
0
Compactions
0
Reads
0

Operation Log

No operations yet

Explanation

overview

See the complete structure of both data structures. B-tree shows node hierarchy with sorted keys. LSM shows WAL, memtable, and SSTable levels.

Quick comparison:
B-tree
  • • Read-optimized
  • • In-place updates
  • • Good for mixed workloads
LSM Tree
  • • Write-optimized
  • • Append-only
  • • Good for write-heavy loads

B-tree

Write Pattern
In-place update
Read Pattern
Single path traversal
Space Amplification
Low (~1.5x)
Write Amplification
High (random I/O)
Best For
Read-heavy, OLTP
Examples: PostgreSQL, MySQL InnoDB, SQLite

LSM Tree

Write Pattern
Append-only
Read Pattern
Multi-level scan
Space Amplification
Medium (~2-3x)
Write Amplification
Low (sequential I/O)
Best For
Write-heavy, time-series
Examples: RocksDB, LevelDB, Cassandra, ScyllaDB

Key Trade-offs

Read Amplification

B-tree: 1 path from root to leaf
LSM: Check memtable + multiple SSTables

Write Amplification

B-tree: May rewrite page for single key
LSM: Sequential append, batch compaction

Space Amplification

B-tree: Minimal overhead per key
LSM: Multiple versions until compaction

When to Use What

Choose B-tree when:

  • Read-heavy workloads (80%+ reads)
  • Need consistent read latency
  • Frequent range scans
  • Space efficiency matters
  • Traditional OLTP (transactions, updates)

Choose LSM when:

  • Write-heavy workloads (lots of inserts)
  • Time-series or log data
  • Can tolerate read latency variance
  • Need high write throughput
  • SSD storage (sequential writes extend life)