Understanding LSM-Tree (Log-Structured Merge Tree) and Its Storage Mechanisms

The Log-Structured Merge Tree (LSM-Tree) is an immutable, tiered storage structure that transforms random writes into sequential writes, greatly improving write performance for write‑heavy, read‑light workloads.

Its storage consists of a write‑ahead log (WAL) on disk, an in‑memory ordered structure (MemTable) often implemented with a SkipList, an immutable MemTable (ImmuTable) created when the active MemTable fills, and on‑disk SSTables that store sorted key‑value pairs with accompanying index and Bloom‑filter structures.

The write workflow proceeds as follows: (1) incoming data is first appended to the WAL for durability; (2) the same data is inserted into the MemTable for ordered caching; (3) when the MemTable reaches a size threshold it is frozen as an ImmuTable and a new MemTable is created; (4) ImmuTables are flushed to disk as SSTables through a compaction step, merging overlapping files and eliminating deleted or obsolete entries; (5) periodic compaction across levels further consolidates SSTables, reducing read and space overhead.

While LSM‑Tree boosts write throughput, it introduces three main amplification issues: read amplification (multiple SSTables must be consulted to locate a key), space amplification (obsolete versions linger until compaction), and write amplification (data is rewritten during compaction). Bloom filters and tiered indexing are employed to mitigate these effects.

Because of these characteristics, many modern databases such as LevelDB, HBase, Google BigTable, and Cassandra adopt LSM‑Tree as their storage engine.