LSM-Tree vs B-Tree
AdvancedB-Trees are the default index structure in relational databases, optimised for reads. LSM-Trees (Log-Structured Merge-Trees) are optimised for write-heavy workloads, used in Cassandra, RocksDB, and LevelDB.
Overview
B-Trees and LSM-Trees are the two dominant data structures for database storage engines. B-Trees (used by PostgreSQL, MySQL InnoDB, Oracle) organise data in a balanced tree of sorted pages. Reads are fast (O(log n)) because you traverse the tree. Writes require finding the correct page and updating it in place (random I/O). LSM-Trees (used by Cassandra, RocksDB, LevelDB, HBase) buffer writes in an in-memory table (memtable). When the memtable is full, it is flushed to disk as an immutable sorted file (SSTable). Background compaction merges SSTables to maintain read performance. LSM-Trees convert random writes to sequential writes, achieving much higher write throughput. The trade-off is that reads may need to check multiple SSTables (Bloom filters mitigate this) and compaction uses CPU and I/O in the background. The choice depends on your read/write ratio: B-Trees for read-heavy, LSM-Trees for write-heavy.
B-Tree
B-Trees store data in sorted, balanced pages. Reads traverse the tree from root to leaf. Writes update pages in place. Widely used in OLTP databases.
// B-Tree structure (simplified)
//
// [50] ← root page
// / \
// [20,30] [70,80] ← internal pages
// / | \ / | \
// [...] [...] [...] [...] ← leaf pages (data)
//
// Read: traverse root → internal → leaf = O(log n)
// 4 levels can index ~1 billion rows (branching factor ~500)
//
// Write: find leaf page → update in place → write page to disk
// Random I/O (write to specific page location)
// WAL write first for durability
//
// Strengths:
// ✅ Fast reads — O(log n), few disk seeks
// ✅ Efficient range queries — leaves are linked
// ✅ Predictable performance
//
// Weaknesses:
// ❌ Write amplification — updating one row writes entire page
// ❌ Random I/O for writes
// ❌ Page splits when full (rebalancing)LSM-Tree
LSM-Trees buffer writes in memory (memtable), flush to disk as sorted files (SSTables), and merge SSTables in background compaction. All writes are sequential — optimised for write throughput.
// LSM-Tree write path
//
// 1. Write → WAL (durability)
// 2. Write → Memtable (in-memory sorted structure, e.g. red-black tree)
// 3. Memtable full → flush to disk as immutable SSTable (sorted string table)
// 4. Background compaction: merge SSTables → remove duplicates, deleted keys
//
// Write: O(1) amortised (append to WAL + memtable insert)
// Flush: sequential I/O (write sorted file — fast!)
//
// Read path:
// 1. Check memtable
// 2. Check SSTables (newest first)
// 3. Bloom filter: quickly skip SSTables that don't contain the key
//
// Read: potentially slower than B-Tree (check multiple SSTables)
// Bloom filters reduce false lookups to < 1%
// Compaction strategies:
// Size-tiered: merge similarly-sized SSTables (Cassandra default)
// ✅ High write throughput
// ❌ Space amplification (temporary duplicate data)
// Leveled: merge into fixed-size levels (RocksDB, LevelDB)
// ✅ Better read performance, less space amplification
// ❌ Higher write amplification from rewriting levelsComparison & When to Use
B-Trees for read-heavy OLTP. LSM-Trees for write-heavy workloads (logs, time-series, IoT). Many modern systems offer both.
// B-Tree vs LSM-Tree comparison
//
// Factor | B-Tree | LSM-Tree
// ──────────────────────────────────────────────────
// Read performance | ✅ Fast (1 path) | ⚠️ Check multiple SSTables
// Write performance | ⚠️ Random I/O | ✅ Sequential I/O
// Write throughput | Moderate | Very high
// Space amplification| Low | Medium (compaction)
// Write amplification| Medium | Higher (compaction rewrites)
// Use cases | OLTP, queries | Logs, time-series, IoT
//
// Databases:
// B-Tree: PostgreSQL, MySQL InnoDB, Oracle, SQL Server
// LSM-Tree: Cassandra, RocksDB, LevelDB, HBase, ScyllaDB
// Both: MongoDB (WiredTiger supports both), CockroachDB (RocksDB)
//
// Rule of thumb:
// Read/write ratio > 70/30 → B-Tree
// Read/write ratio < 30/70 → LSM-Tree
// Mixed → depends on latency vs throughput priorityKey Points to Remember
- 1B-Trees: in-place updates, fast reads (O(log n)), random write I/O — default for OLTP databases.
- 2LSM-Trees: buffer in memory, flush as sorted files, sequential I/O — optimised for write-heavy workloads.
- 3LSM-Trees use Bloom filters to skip SSTables during reads, mitigating the multi-file read overhead.
- 4Compaction is the trade-off: LSM-Trees need background CPU/I/O to merge SSTables.
- 5Choose based on read/write ratio: B-Tree for read-heavy, LSM-Tree for write-heavy.
Interview Questions
Sign in to ask AriaWhat is the difference between B-Tree and LSM-Tree storage engines?
Why are LSM-Trees better for write-heavy workloads?
What are Bloom filters and how do they help LSM-Tree reads?
Explain the compaction process in LSM-Trees.
Design a storage engine for a time-series database ingesting 1M writes/sec.
Ask Aria about LSM-Tree vs B-Tree
Your personal AI tutor — ask anything about this concept
Revision Status
Personal Notes
Sign in to save personal notes for this topic.
Discussion
Sign in to join the discussion.