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)
When writing, columnar storage must place values of different columns into different locations, so the cost of a single-row insert is far higher than in row-based storage, and therefore OLAP systems typically use batch import and background merging (such as LSM-Tree compaction) to amortize write costs.
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.
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.
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.
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.
Implementing a simplified LSM-Tree storage engine by hand helps in understanding the architectural design of LevelDB, RocksDB, and Cassandra.
All Facts (8)
When writing, columnar storage must place values of different columns into different locations, so the cost of a single-row insert is far higher than in row-based storage, and therefore OLAP systems typically use batch import and background merging (such as LSM-Tree compaction) to amortize write costs.
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%UnverifiedLSM-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%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%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%UnverifiedImplementing a simplified LSM-Tree storage engine by hand helps in understanding the architectural design of LevelDB, RocksDB, and Cassandra.
50%