LSM‐Tree Engine

The LSM-Tree Engine. Log-Structured Merge-tree (LSM-Tree) engine is a storage architecture optimized for high-throughput write operations. Traditional databases use B-Trees, which write data directly to random locations on disk, causing expensive disk-head movements or flash-memory wear. LSM-Trees turn random writes into fast, sequential writes.

How data flows through an LSM engine:

1. MemTable: When data is written, it goes straight into an in-memory sorted buffer (usually a SkipList). Simultaneously, it appends to a Write-Ahead Log (WAL) on disk for crash recovery.
2. SSTables (Sorted String Tables): When the MemTable fills up, it freezes and flushes its sorted contents sequentially to disk as an immutable file called an SSTable.
3. Levels & Compaction: Because SSTables are immutable, updates and deletes don't overwrite old data; they just create new entries. Over time, multiple versions of the same key accumulate across different files. Compaction is the background process that merges these files, purges duplicates or deleted keys (tombstones), and organizes them into hierarchical levels to keep reads fast.