🌲Log-Structured Merge-Tree

NEW

Also known as: LSM-Tree

A write-optimized index that stores sorted runs and periodically merges them, enabling high-throughput writes with acceptable read performance.

DESCRIPTION

The Log-Structured Merge-Tree is a disk-resident data structure designed for fast writes. Data is first buffered in memory (memtable) and flushed to immutable SSTables, which are compacted over time. Bloom filters and indexes accelerate lookups across multiple levels. LSM-trees trade read amplification and compaction overhead for vastly improved write throughput. They underpin modern key-value stores and wide-column databases. Common implementations include RocksDB, LevelDB, Cassandra, and HBase. LSM-trees are well-suited to SSDs and log-structured storage.

ALTERNATIVE DEFINITIONS

O’Neil et al. (1996)

The Log-Structured Merge-Tree (LSM-Tree) is a disk-based data structure designed to provide high write throughput.

Introduces the original concept focused on high write performance and merging.

Source

RocksDB

RocksDB stores data in a Log-Structured Merge-Tree (LSM) where updates are first written to a memtable and then flushed to SST files.

Highlights practical implementation details of LSM-trees in a production KV store.

Source

Apache Cassandra

Cassandra uses a log-structured merge-tree (LSM) storage engine to provide high write throughput.

Emphasizes high write throughput in a distributed wide-column database.

Source

Wikipedia

A log-structured merge-tree (LSM tree) is a data structure that is used for storing data that is being frequently inserted, updated, and deleted.

Highlights the suitability for write-heavy workloads and frequent updates.

Source

RELATED TERMS

SSTable Memtable Compaction Transaction Log Bloom Filter RocksDB Apache Cassandra LevelDB

COMPETING TERMS

B-Tree Fractal Tree Index

KNOWLEDGE AREAS

Data Storage & Operations Data Engineering Infrastructure Software Engineering

TARGET AUDIENCE

Data Engineer Software Developer Data Architect Solution Architect

EXTERNAL SOURCES

• Wikipedia - Log-structured merge-tree
• O’Neil et al. (1996) - Original LSM-tree paper
• RocksDB - Production LSM implementation
• Apache Cassandra - LSM storage engine overview

TOP QUESTIONS

Why is Log-Structured Merge-Tree favored in modern databases?

LSM-trees maximize write throughput and sequential I/O, ideal for SSDs and append-only logs. They efficiently handle high ingestion rates and compaction keeps data organized for reads.

Category: Relevancy

What performance trade-offs does a Log-Structured Merge-Tree make?

LSM-trees trade read amplification and compaction overhead for superior write performance. Bloom filters and tiering reduce read costs.

Category: Trade-off

Which systems commonly use Log-Structured Merge-Tree?

RocksDB, LevelDB, Apache Cassandra, and HBase use LSM-based storage engines to support write-heavy workloads.

Category: Examples

How does compaction work in a Log-Structured Merge-Tree?

Compaction merges overlapping SSTables into larger sorted runs, removing obsolete entries and improving read locality while balancing space and write amplification.

Category: Mechanism

What is the role of a memtable in a Log-Structured Merge-Tree?

The memtable buffers recent writes in memory, allowing fast updates, which are later flushed as immutable SSTables to disk.

Category: Concept

What are common mistakes when tuning a Log-Structured Merge-Tree?

Misconfiguring compaction strategies, bloom filter sizes, or write buffers can cause read amplification, latency spikes, and space bloat.

Category: Mistakes

How do bloom filters help in Log-Structured Merge-Tree reads?

Bloom filters quickly eliminate SSTables that don’t contain a key, reducing disk lookups and improving read performance.

Category: Optimization

What is a competing structure to Log-Structured Merge-Tree?

B-tree and B+ tree offer faster point reads and range scans under certain workloads, but they typically deliver lower write throughput.

Category: Alternatives

When should Log-Structured Merge-Tree not be used?

For read-heavy, low-update workloads with strict latency requirements, a B-tree-based engine may be more suitable.

Category: Risks