LSM-Tree
A data structure proposed by Patrick O'Neil and others in 1996 that converts random writes into sequential writes. It reduces write amplification through an in-memory MemTable buffer and a tiered compaction mechanism. LSM-Tree is widely used in high-write-throughput storage engines such as RocksDB and LevelDB.
Timeline (last 90 days)
LSM-Tree was proposed by Patrick O'Neil et al. in 1996, originally to address the random I/O bottleneck of traditional B-trees under high write loads.
Storage engines optimized for write performance typically use LSM-Tree (Log-Structured Merge-Tree) as the underlying data structure.
LSM-Tree converts random writes into sequential writes: data is first written to an in-memory MemTable, which is batch-flushed to disk once a threshold is reached, and then organized layer by layer through background Compaction.
There is an inverse trade-off between write amplification and read amplification: lowering the Compaction trigger threshold can reduce read amplification but increases write amplification.
LSM-based engines have an advantage in writes, but reads — especially range queries — may require searching across multiple levels, resulting in read amplification.
Due to frequent page splits, write amplification in B+ trees is typically above 10x; write amplification in LSM-Trees typically fluctuates between 3x and 30x.
Implementing a simplified LSM-Tree storage engine by hand helps in understanding the architectural design of LevelDB, RocksDB, and Cassandra.
All Facts (7)
LSM-Tree was proposed by Patrick O'Neil et al. in 1996, originally to address the random I/O bottleneck of traditional B-trees under high write loads.
50%UnverifiedStorage engines optimized for write performance typically use LSM-Tree (Log-Structured Merge-Tree) as the underlying data structure.
50%UnverifiedLSM-Tree converts random writes into sequential writes: data is first written to an in-memory MemTable, which is batch-flushed to disk once a threshold is reached, and then organized layer by layer through background Compaction.
50%UnverifiedThere is an inverse trade-off between write amplification and read amplification: lowering the Compaction trigger threshold can reduce read amplification but increases write amplification.
50%UnverifiedLSM-based engines have an advantage in writes, but reads — especially range queries — may require searching across multiple levels, resulting in read amplification.
50%UnverifiedDue to frequent page splits, write amplification in B+ trees is typically above 10x; write amplification in LSM-Trees typically fluctuates between 3x and 30x.
50%UnverifiedImplementing a simplified LSM-Tree storage engine by hand helps in understanding the architectural design of LevelDB, RocksDB, and Cassandra.
50%