LSM tree.
also: LSM trees · log-structured merge tree · LSM-tree · SSTable · SSTables · memtableA write-optimised structure: writes go to an in-memory table, flush to sorted immutable files, and background compaction merges them.
the two-minute refresher
- Write path: WAL, then the in-memory memtable; when full it is flushed as a sorted SSTable.
- Reads check the memtable, then SSTables newest first; Bloom filters skip files without the key.
- Compaction merges files and drops overwritten and deleted data.
- Used by RocksDB, LevelDB, Cassandra and HBase: great write throughput, more read work.