We use analytics cookies.We use cookies to analyze site traffic and improve your experience.
Loading...
System Design and AI Engineering, by Roni Das. 984 interactive lessons.
Start LearningIntermediate · Database Types & Storage
Log-Structured Merge Tree: a write-optimized data structure that buffers writes in memory and periodically flushes sorted runs to disk. Used by Cassandra, RocksDB, and LevelDB.
In short
An LSM tree (Log-Structured Merge tree) is a write-optimized storage structure that buffers incoming writes in an in-memory sorted table, then flushes them to disk in large sorted batches called SSTables, and periodically merges those files together in a background process called compaction. By turning slow random disk writes into fast sequential ones, it powers high-write databases like Cassandra, RocksDB, and LevelDB.
In short
An LSM tree (Log-Structured Merge tree) is a write-optimized storage structure that buffers incoming writes in an in-memory sorted table, then flushes them to disk in large sorted batches called SSTables, and periodically merges those files together in a background process called compaction. By turning slow random disk writes into fast sequential ones, it powers high-write databases like Cassandra, RocksDB, and LevelDB.
Learn it in the course
This page is the free part.
₹1,111 in India$25 everywhere elseonce, for the whole course
The System Design course covers LSM Tree across a run of lessons, not one page. These 3 alone are about 103 minutes of step-by-step reading, every one with a quiz.
How an LSM tree turns random writes into fast sequential ones: the memtable, WAL and SSTables, size-tiered vs leveled compaction, and what reads cost.
Design a distributed key-value store - LSM trees, compaction, consistent hashing, replication, tunable consistency, and failure detection.
How LSM-tree databases like Cassandra, RocksDB, and LevelDB clean up their mess, merging, sorting, and reclaiming space.
all part of
System Design Masterclass
770 lessons · about 287 hours · 18 free to read
₹1,111in India, by UPI
$25everywhere else, by PayPal
It is really nice and good Please join the course
You own this course
Continue with LSM Treespay once,
yours for life
An LSM tree is a way to store sorted key-value data that is tuned for fast writes. Instead of editing data where it already sits on disk, which is what a B-tree does, an LSM tree only ever appends. New writes land in memory first, and disk files are written once and never modified again.
It has three moving parts. The memtable is a sorted in-memory structure, usually a skip list or red-black tree, that absorbs every incoming write. A Write-Ahead Log (WAL) records each write to disk first so nothing is lost on a crash. SSTables (Sorted String Tables) are immutable sorted files on disk that hold the flushed data.
Because every disk file is sorted and immutable, the engine never has to seek around to update a page. It writes one big sequential block at a time, which is the whole reason LSM trees exist.
Every write goes to the WAL and the memtable at the same time. The memtable keeps keys sorted as they arrive, so reads of recently written data are served straight from RAM. When the memtable fills up, typically at 64 to 256 MB, it is frozen and written to disk as a single new SSTable in one sequential pass.
Over time you accumulate many SSTables. Reads now have to check the memtable, then each SSTable from newest to oldest, because a newer file may hold an updated value or a tombstone marking a deletion. Two structures keep this cheap. A bloom filter per SSTable answers definitely not here without touching disk, and a sparse index per file points reads near the right offset.
Compaction is the background job that keeps things from sprawling. It merges several SSTables into fewer, larger sorted files, drops overwritten and deleted entries, and deletes the old files. Two common strategies are size-tiered, which merges files of similar size and is used by Cassandra by default, and leveled, which keeps non-overlapping key ranges per level and is the default in RocksDB and LevelDB.
Reach for an LSM-backed store when your workload is write-heavy: IoT sensor streams, application logs, event ingestion, time-series metrics, or any system where writes vastly outnumber reads. Sequential writes are several times faster than small random writes on SSDs and hundreds of times faster on spinning disks, so the gap over a B-tree is large under load.
The cost is read amplification and write amplification. A point lookup may consult several files, and a range scan has to merge data spread across levels, so reads are more work than the single-tree lookup a B-tree gives you. Compaction also rewrites data repeatedly: leveled compaction can physically write each value 10 to 30 times as it sinks through levels, which wears SSDs faster and competes for I/O.
If your workload is read-heavy with lots of complex range queries, a B-tree engine like PostgreSQL or InnoDB is simpler and more predictable. Most distributed databases pick LSM trees anyway, because replication and reconciliation make them write-heavy by nature, and their sorted, immutable files tend to compress well.
Picture a fleet of delivery trucks each pushing a GPS ping every few seconds into Cassandra. That is a flood of small writes with almost no in-place updates. Each ping appends to the WAL and the memtable, the memtable flushes to an SSTable when it fills, and compaction quietly stitches the files together overnight.
Reading the last hour for one truck is a short range scan that the bloom filters and per-level indexes make fast, while the heavy ingest never blocks because it never seeks to random disk pages. A B-tree handling the same firehose would thrash on random page updates and splits.
This is exactly why RocksDB sits underneath TiKV and Kafka Streams state stores, why CockroachDB built Pebble, its own RocksDB-inspired LSM engine, and why Cassandra and ScyllaDB chose the LSM design for their core engines.
RocksDB
Meta's embeddable LSM engine; runs inside MyRocks, CockroachDB, TiKV, and Kafka Streams as the on-disk state store.
Apache Cassandra
Uses memtables and SSTables with size-tiered compaction by default, leveled compaction for read-heavy tables.
Google LevelDB
The original open-source leveled-compaction LSM library that RocksDB was forked from; ships inside Chrome and Bitcoin Core.
ScyllaDB
A C++ rewrite of Cassandra that keeps the LSM storage model and tunes compaction per shard for high write throughput.
A B-tree updates data in place, which means random writes to specific disk pages and good read performance. An LSM tree appends writes to memory and flushes them as large sequential files, giving much faster writes at the cost of slower reads and background compaction work.
A Sorted String Table is an immutable on-disk file of key-value pairs sorted by key. It is what an LSM tree produces when it flushes a full memtable, and it is never edited afterward, only merged away by compaction.
Each memtable flush creates a new SSTable, so files pile up and reads slow down because a lookup may have to check many files. Compaction merges SSTables into fewer larger ones, removes deleted and overwritten entries, and reclaims disk space.
It is how many times a single logical write gets physically rewritten to disk. As data sinks through compaction levels it is rewritten repeatedly, so one user write can become 10 to 30 disk writes under leveled compaction, which matters for SSD wear and I/O budget.
Each SSTable carries a bloom filter that can rule it out without any disk access, and a sparse index that points reads near the right offset. With a 1 percent false positive rate the engine skips almost all irrelevant files, so most point lookups touch very few SSTables.
B-Tree
A self-balancing search tree in which each node is a page holding many sorted keys, so it stays wide and shallow. Most database indexes use it: finding one key among millions takes only a few page reads.
Write-Ahead Log
A technique where changes are written to a log before being applied to the database. Ensures durability and crash recovery.
NoSQL
Databases that don't use traditional table-based relational models. Includes document stores, key-value, graph, and column-family databases.
Redis
An in-memory data store used as a cache, message broker, and database. Blazing fast because everything lives in RAM.
Memcached
A simple, high-performance distributed memory caching system. Stores key-value pairs in RAM. Simpler than Redis but less feature-rich.
Document Database
A NoSQL database that stores data as flexible JSON-like documents. MongoDB and CouchDB let each document have a different structure.
This page explains the idea. The "LSM Trees" lesson builds it up step by step, with diagrams. It is part of the System Design Masterclass course, which has 770 lessons. 18 of them are free to read. You pay once and keep it for life, with no subscription.
Open the LSM Trees lessoncourse 1
From absolute beginner to principal engineer, drawn step by step.
Asked about LSM Tree in an interview?
Each question has why it is asked, a full answer, what the interviewer listens for, the follow-ups, the common mistakes and a diagram (268 diagrams in all). A PDF you keep, junior to staff level.
India: UPI, cards or netbanking through Razorpay. Elsewhere: card or PayPal. Download at once from My packs.
