Log-Structured Merge (LSM) tree

The Log-Structured Merge Tree, also known as an LSM tree, is one of the most popular storage engines, focusing on performant write operations. The benefit over the B+ Tree with this mechanism is that it requires only a single random block access to update the same data in the index. It’s been heavily used in NoSQL DBs, though it’s also being used in relational DBs.

Building blocks

Building blocks: LSM intro

MemTable

A memtable is a data structure that holds data in memory before it’s flushed to disk. It is usually implemented as a balanced binary search tree.

A balanced binary search tree is a data structure in which the difference between the depths of the left and right subtrees is $0$ or $1$ at every node. Since the tree is balanced, its height is $O(\log N)$, where $N$ is the number of nodes — so lookups, inserts and deletes on the memtable are logarithmic in the number of in-memory keys.

SSTables (Sorted String Tables)

SSTables (Sorted String Tables): LSM sstable

Compaction

There can be multiple L0 files that are not sorted; hence, compaction happens differently in L0 than in the other levels.

Compaction: LSM l0 compaction

Compaction: LSM ln compaction

data compaction reduces storage requirements over time. Also, there’s a separate threshold at each level beyond which the compaction gets triggered, and that threshold limit increases exponentially at each level. This threshold value is dynamically determined to enable space amplification.

References

1. What is a log-structured merge tree (LSM tree)?
2. The Log-Structured Merge-Tree (LSM Tree)
3. A deep dive: What is LSM tree?
4. LSM Trees, Memtables & Sorted String Tables: An Introduction
5. Write throughput differences in B-tree vs LSM-tree based databases?
6. Dynamic Level Size for Level-Based Compaction
7. Option of Compaction Priority
8. Leveled Compaction