LSM Trees — Understanding the Data Structure that Powers NoSQL Databases
LSM Trees — Understanding the Data Structure that Powers NoSQL Databases
Author: Ramarathinam Iyer Date: 2026-03-02 Source: https://ramarathinam-iyer.medium.com/lsm-trees-understanding-the-data-structure-that-powers-nosql-databases-ee72d570bdc9
Why NoSQL Databases Exist
NoSQL emerged around 2010 as a response to relational database limitations. Traditional databases enforce strict schema and relationship constraints that can slow operations. NoSQL systems eliminate these restrictions for use cases that don't require them.
Fun fact: NoSQL stands for "Not Only SQL," a term that originated as a Twitter hashtag.
The Write Amplification Problem
While B trees perform all operations in O(log n) time, they create bottlenecks as databases scale. The issue stems from write amplification:
B trees use fixed-size pages (typically 8KB). Modifying a single byte requires loading the entire page into memory, modifying it, and writing it back. This causes "random I/O," which is slow on HDDs and expensive on SSDs.
B-Trees represent mutating in-place storage, while LSM Trees represent append-only storage. LSM trees never overwrite — they only add new sequential files and merge them later.
LSM Tree Architecture
MemTable
Holds data before disk flushing. Implemented as either a skip list or balanced tree, it keeps data sorted in RAM for efficient sequential writing to disk.
SSTables
Sorted String Tables contain numerous sorted key-value pairs. Once written to disk, these files are immutable and cannot be modified.
Data Flow
Write: Data enters the Write Ahead Log (WAL) for durability and the MemTable for speed.
Flush: When MemTable reaches a threshold (e.g., 64MB), it writes sequentially to disk as an SSTable, then clears.
Read: The system checks the MemTable first. If the key isn't found, it searches SSTables level-by-level, from newest to oldest.
Write Ahead Log
A sequential disk log recording every write operation before applying it to the MemTable. If the database crashes, committed data isn't lost and the MemTable can be reconstructed.
Bloom Filters for Efficient Reads
Systems use Bloom Filters — probabilistic data structures that answer: "The data is definitely NOT in this file" or "It MIGHT be in this file."
Before touching disk, the system checks the Bloom Filter in RAM. False returns skip that SSTable entirely. While false positives occur, this beats scanning every file.
Handling Updates and Deletions
Because SSTables are immutable, updates don't modify existing data. Instead, the new key-value pair is appended. Since reads proceed level-by-level, the system always retrieves the latest value.
Deletions use a special marker called a tombstone. When reading, seeing a tombstone indicates the record is deleted.
Compaction
Background process merging many small SSTables into fewer, larger ones.
Compaction Strategies
Leveled Compaction: Aggressively merges files to maintain high read speeds but with higher write amplification. Used by RocksDB and LevelDB.
Size-Tiered Compaction: Waits for several similar-sized files before merging. Offers faster writes but variable read latency. Used by Cassandra.
Tradeoffs
Write Stalls: If MemTable fills and disk flushing is slow, the database stops accepting writes. This applies backpressure when compaction can't keep pace with flush rates.
Space Amplification: Updating a record 100 times stores 100 versions on disk until compaction runs.