LSM Tree vs B-Tree

The choice between LSM tree and B-tree storage engines is the most consequential low-level architectural decision in database system design. These two data structures represent fundamentally different philosophies: B-trees maintain a single, mutable sorted structure that is updated in place, optimizing for read performance at the cost of random write I/O; LSM trees accumulate immutable sorted runs that are merged in the background, optimizing for write throughput at the cost of read amplification. Every production database makes this choice, and understanding the trade-offs is essential for selecting the right engine for a given workload.

Write amplification -- the ratio of total bytes written to storage versus the logical bytes of user data -- is where LSM trees have a clear structural advantage. When a B-tree modifies a single key, it must rewrite the entire page (typically 4KB-16KB) containing that key, even if the actual change is a few bytes. A page split during insertion rewrites two pages plus the parent, and these writes are random I/O scattered across the disk. An LSM tree, by contrast, appends the write sequentially to a WAL and buffers it in memory. When the memtable flushes, it writes a sorted SSTable in a single sequential operation. However, LSM trees have their own write amplification from compaction: in leveled compaction, data is rewritten at each level transition, resulting in a total write amplification of approximately 10-30x over the data's lifetime. The key difference is that all of this I/O is sequential, which on HDDs is approximately 100x faster than random I/O, and on SSDs is still 3-10x faster.

Read amplification -- the number of I/O operations required to satisfy a point lookup -- favors B-trees. A B-tree lookup traverses from root to leaf, touching one page per level; with internal pages cached in the buffer pool, this typically means a single disk read for the leaf page. An LSM tree point lookup must potentially check the memtable, then each SSTable level from newest to oldest. Without optimizations, a 5-level LSM tree could require 5 disk reads per lookup. Bloom filters reduce this dramatically: with 10 bits per key (~1% false positive rate), most levels are skipped, and the expected number of disk reads drops to approximately 1.1 for a point lookup. But for range scans, LSM trees must merge-sort results from multiple SSTables, while B-trees simply follow the linked leaf chain -- a significant advantage for range-heavy workloads like analytics queries and ordered iteration.

Space amplification -- the ratio of total disk space used versus the logical size of the data -- is another critical dimension. B-trees typically maintain 65-75% page utilization after random insertions (due to page splits leaving pages half-full), resulting in approximately 1.3-1.5x space amplification. LSM trees with leveled compaction maintain around 1.1x space amplification in steady state because compaction produces tightly packed SSTables. However, during compaction itself, the system temporarily needs space for both the input SSTables and the output SSTable, which can spike to 2x the logical data size. Size-tiered compaction is worse: because it delays merging large tiers, space amplification can reach 2-10x. For cost-sensitive deployments, this difference in storage efficiency can be the deciding factor.

SSD-specific considerations add nuance to the comparison. SSDs have asymmetric read/write performance, limited write endurance (each cell can only be written a finite number of times), and internal write amplification from garbage collection. LSM trees' sequential write patterns align well with SSD internals: sequential writes minimize the SSD's internal garbage collection overhead and reduce write amplification at the device level. However, heavy compaction can cause periodic I/O spikes that interfere with foreground request latency -- a phenomenon called 'compaction stalls.' B-trees benefit from SSDs' fast random reads (SSD random reads are only 4-10x slower than sequential, compared to 100x on HDDs), which makes the B-tree's random read pattern much less costly on modern hardware. The convergence of random and sequential I/O performance on SSDs has narrowed the write throughput gap between LSM and B-tree engines, though LSM trees still hold a significant advantage for sustained write-intensive workloads.

Hybrid approaches attempt to combine the best of both architectures. The BW-tree (used in Microsoft's Hekaton in-memory OLTP engine and Azure SQL Database) uses a B-tree structure but with delta chains instead of in-place updates, converting random writes into sequential log-structured appends while maintaining B-tree read patterns. Facebook's RocksDB introduced a feature called BlobDB that stores large values in a separate log-structured blob store while keeping keys and small values in the LSM tree, reducing write amplification for workloads with large values. TiDB takes a different hybrid approach: it uses RocksDB (LSM) as the storage engine for its TiKV OLTP layer, but uses a columnar format in TiFlash for OLAP queries, routing queries to the appropriate engine based on the query pattern. These hybrid designs acknowledge that no single data structure is optimal for all access patterns, and the future of storage engines lies in adaptive, workload-aware combinations.

Imagine two systems for tracking inventory changes. The B-tree approach is like a filing cabinet with folders sorted alphabetically: to update an item, you find the right folder (fast lookup), erase the old count, and write the new one (in-place update, but you touched the whole page). The LSM approach is like a notebook: you jot each change on the next blank line (fast sequential write). To find the current count for an item, you scan backward through the notebook looking for the latest entry for that item (slower read). Periodically, you rewrite the notebook by consolidating all entries per item into a clean sorted version (compaction). The filing cabinet is great for looking things up; the notebook is great for recording lots of changes quickly.