SQL vs NoSQL: How to Choose
SQL vs NoSQL explained: data models, consistency, scaling, query flexibility and when to use relational, document, key-value, wide-column or graph databases.
B-Trees vs LSM Trees: How Databases Store Data
How B-tree and LSM-tree storage engines work, why one favours reads and the other writes, write and read amplification, compaction and which databases use each.
Key takeaways
- B-trees update pages in place and give fast, predictable reads; most relational databases use them.
- LSM trees buffer writes in memory and write sorted files sequentially, giving very high write throughput.
- LSM trees trade extra read work and background compaction for faster writes.
On this page
Underneath every database is a storage engine that decides how data is laid out on disk. The two dominant designs, B-trees and log-structured merge trees (LSM trees), make opposite trade-offs, and knowing them helps you pick the right database for a workload.
B-trees
A B-tree keeps keys sorted in fixed-size pages arranged in a shallow, balanced tree. Finding a key means walking from the root to a leaf, usually just a few page reads, even for huge tables.
Writes update pages in place. To survive crashes, changes are first recorded in a write-ahead log. When a page fills up, it splits.
Strengths: fast, predictable reads and range scans; mature and well understood. Most relational databases use B-tree indexes; our guide to database indexing shows how to design them for your queries.
LSM trees
An LSM tree turns random writes into sequential ones:
- Writes go to an in-memory sorted structure (the memtable) and a log.
- When the memtable fills, it’s flushed to disk as an immutable sorted file (an SSTable).
- In the background, compaction merges files, discarding overwritten and deleted values.
Reads check the memtable, then files from newest to oldest. Bloom filters let the engine skip files that definitely don’t contain a key.
Strengths: very high write throughput and good compression. Many wide-column and key-value stores use LSM trees.
Comparing the trade-offs
| B-tree | LSM tree | |
|---|---|---|
| Write pattern | Random, in place | Sequential, batched |
| Write throughput | Good | Excellent |
| Read latency | Predictable | Can vary; more files to check |
| Write amplification | Page rewrites | Compaction rewrites |
| Space | Some fragmentation | Better compression; temporary duplicates |
| Background work | Little | Compaction needs I/O headroom |
Amplification, in brief
- Write amplification: bytes written to disk per byte of data written by the application.
- Read amplification: disk reads per query.
- Space amplification: disk space used relative to live data.
Every engine balances these three; tuning compaction strategy shifts the balance for LSM trees.
Choosing
- Read-heavy, transactional workloads with range queries: B-tree engines are a safe default.
- Write-heavy workloads such as logs, metrics, events and time series: LSM engines shine.
Engine choice often comes bundled with your database choice; see SQL vs NoSQL. At larger scale, combine it with sharding.
Frequently asked questions
Why do LSM trees need compaction?
Because files are immutable, updates and deletes create new entries. Compaction merges files and removes obsolete data to keep reads and storage efficient.
Are B-trees slow for writes?
Not slow, but random in-place updates are generally less efficient than sequential batched writes.
What is a Bloom filter?
A compact probabilistic structure that can say “definitely not here” or “possibly here”, letting LSM engines skip unnecessary file reads.
Sources
Every article is edited by a human and checked against our editorial policy. Spotted a mistake? Tell us.
Keep reading
Database Sharding Explained
What database sharding is, when you need it, how to choose a shard key, range vs hash vs directory sharding, and the operational pain points to plan for.
Database Indexing Explained
How database indexes work: B-tree and other types, composite and covering indexes, why queries ignore indexes, the write cost and checking with EXPLAIN.