B-Tree vs LSM-Tree: Database Storage Engine Mechanics
At the heart of every database system lies a Storage Engine that determines how data is written to disk, indexed, and retrieved. Relational databases like PostgreSQL and MySQL traditionally use B-Trees (and B+ Trees), whereas high-throughput key-value and NoSQL stores like RocksDB, Cassandra, and LevelDB use Log-Structured Merge-trees (LSM-Trees).
This guide breaks down the structural differences between B-Tree in-place updates and LSM-Tree append-only writes, analyzing write amplification, read latency, compaction algorithms, and SSD longevity.
In-Place B-Tree Updates vs. Append-Only LSM-Trees
B-Trees break data down into fixed-size pages (typically 4 KB to 16 KB) organized in a balanced search tree hierarchy. Writes update pages in-place on disk. To prevent corruption during partial page writes, B-Tree databases write changes to a Write-Ahead Log (WAL) before modifying disk pages.
LSM-Trees avoid random in-place disk writes entirely. Incoming writes are appended to an in-memory skip-list (MemTable) and written sequentially to a Write-Ahead Log. When the MemTable fills up, it is flushed to disk as an immutable SSTable (Sorted String Table).
Quick reference
- B-Tree: Optimized for fast point and range reads ($O(\log N)$), but suffers from random write I/O overhead on disk.
- LSM-Tree: Converts random writes into sequential disk I/O, delivering massive write throughput.
- LSM-Tree Compaction: Background processes periodically merge smaller SSTables to reclaim deleted keys and maintain read efficiency.
Remember this
B-Trees optimize for fast read queries; LSM-Trees optimize for high-concurrency write ingestion.
Write Amplification & SSD Hardware Impact
Write Amplification Factor (WAF) measures the ratio of bytes written to underlying storage relative to bytes submitted by the application. In B-Trees, updating a single 50-byte row requires writing an entire 8 KB or 16 KB page to disk, resulting in high write amplification and faster NVMe SSD wear.
LSM-Trees minimize initial write amplification by buffering writes sequentially in RAM before flushing. However, background SSTable compaction generates deferred write amplification as data cascades down storage levels.
Quick reference
- High B-Tree write amplification can shorten SSD lifespan in write-heavy production workloads.
- Bloom Filters are placed in front of LSM-Tree SSTables to prevent expensive disk lookups for non-existent keys.
- Compare with Database Indexing Mechanics and PostgreSQL vs MongoDB.
Remember this
LSM-Trees extend SSD hardware lifespan under heavy write workloads by eliminating random page overwrites.
Storage Engine Selection Matrix
Choosing between B-Tree and LSM-Tree storage engines depends on your application's read-to-write query ratio.
For related guides, see our articles on Sharding & Replication and Query Execution Plans.
Quick reference
- Choose B-Tree (PostgreSQL, MySQL InnoDB, SQLite) for read-heavy relational workloads, complex JOINs, and point updates.
- Choose LSM-Tree (RocksDB, Cassandra, ScyllaDB, CockroachDB) for write-heavy telemetry, event logging, and time-series data.
- Hybrid engines like WiredTiger (MongoDB) use B-Trees for indexes and LSM options for log collections.
Remember this
Match B-Tree engines to read-heavy relational apps and LSM-Tree engines to high-volume write ingestion pipelines.
Key takeaway
Understanding B-Tree in-place updates versus LSM-Tree append-only SSTables empowers developers to choose the optimal database storage engine for performance and hardware longevity.
Shoaib Hossain
Lead Author & Systems ArchitectSoftware engineer and distributed systems architect specializing in backend scalability, cloud-native infrastructure, databases, and AI engineering workflows. Author and maintainer of Core Concept Learning.
Related Articles
Explore this topic