LSM Tree vs B-Tree: Why Write-Heavy Systems Skip the B-Tree
How MemTables, SSTables and compaction make writes fast, explained in 3 minutes.
I was working on a system design question: "How do you design a write-heavy system?" While digging into it, I ran into something I had never heard of: the LSM tree (Log-Structured Merge tree).
In college, we all learned B-Trees. So I wanted to know: why would anyone use something else? Here is what I found.
Note: This is an overview, not a textbook. I don't cover definitions here. If a term is new to you, read up on it on your own.
TL;DR
- B-Trees are great for reads. They are slow when writes land at random spots on disk.
- LSM trees are built for writes. They turn random writes into fast, sequential ones.
- An LSM tree has three parts: MemTable, SSTables and compaction.
- Pick by workload: read-heavy goes B-Tree, write-heavy goes LSM.
Both are popular, but for different jobs
Both data structures are used everywhere. They just shine in different places:
- B-Tree: read-heavy systems
- LSM tree: write-heavy systems
B-Trees slow down when writes are random
A B-Tree is really good at finding where your data lives. That's why reads are fast.
Writes are a different story. If you write to random places, the database keeps jumping around the disk to change different pages. This causes heavy random I/O, and that kills write speed.
Random writes like this are very common in today's distributed systems, like social media apps. So in those cases, B-Trees are not a great fit.
How an LSM tree makes writes fast
An LSM tree works across two layers: memory and disk. Here is what happens to a write.
1. MemTable (in memory)
A new write goes straight into the MemTable. It is a sorted data structure in memory, like a SkipList.
The write is also added to a Write-Ahead Log (WAL) on disk. The WAL is only there for crash recovery. Adding to the end of a log is a sequential write, so it's cheap.
Writing to RAM is very fast, so your write finishes almost right away.
2. SSTables (on disk)
When the MemTable fills up, it gets flushed to disk as an SSTable (Sorted String Table).
SSTables are immutable. Once written, they are never changed.
3. Compaction
Since SSTables never change, updating a record means writing a new version of it in a newer SSTable.
A background process called compaction keeps merging SSTables. It throws away old and deleted versions to save space.
LSM tree vs B-Tree at a glance
| B-Tree | LSM tree | |
|---|---|---|
| Best for | Read-heavy work | Write-heavy work |
| Writes | In place, at random spots | Appended in order |
| Updates | Change the page directly | Write a new version |
| Reads | Fast, one path to the data | May check a few SSTables |
| Disk space | Little extra | Old versions wait for compaction |
| Used by | PostgreSQL, MySQL (InnoDB) | Cassandra, RocksDB, LevelDB |
So which one should you pick?
- Mostly reads? Go with a B-Tree.
- Lots of writes, landing all over the place? Go with an LSM tree.
So are LSM trees bad at reads?
No. LSM trees can be fast at reads too.
But not in every case. A key could be hiding in the MemTable or in any one of many SSTables. Checking them all, one by one, gets slow.
So how do LSM trees skip the files that don't have your key? One small trick does most of the work.
Hint: Bloom filters. That's the next post.
Have a question, or a topic you want me to cover? Find me on X @YadavVageshwar.
- system-design
- databases
- data-structures
Found this useful? Share it.
