Two Ways to Store Data on Disk

Every database has to answer a basic question: how do you organise data on disk so you can write it quickly and find it again quickly? Two designs dominate:

  • B-trees: keep data sorted in pages and update pages in place. Used by PostgreSQL, MySQL (InnoDB), SQL Server and SQLite.
  • LSM trees (log-structured merge trees): collect writes in memory, flush them as sorted, immutable files, and merge files in the background. Used by Cassandra, RocksDB, ScyllaDB, HBase and many time-series databases.

Neither is "better." They make opposite trade-offs between write speed and read speed.


๐ŸŽฏ Quick Answer (30-Second Read)

  • B-tree: great reads and range scans; writes update pages in place (random I/O).
  • LSM tree: great write throughput; writes are sequential appends; reads may check several files.
  • LSM pieces: write-ahead log โ†’ in-memory memtable โ†’ flushed to sorted SSTables โ†’ merged by compaction.
  • Bloom filters help LSM reads skip files that don't contain a key.
  • Choose B-tree for read-heavy, transactional workloads. Choose LSM for heavy writes: logs, events, time series, feeds.

How a B-Tree Works

flowchart TB R["Root page
[ 100 | 500 ]"] --> A["Page
[ 20 | 60 ]"] R --> B["Page
[ 200 | 350 ]"] R --> C["Page
[ 700 | 900 ]"] A --> A1["Leaf: 1โ€“19"] A --> A2["Leaf: 20โ€“59"] A --> A3["Leaf: 60โ€“99"] B --> B1["Leaf: 100โ€“199"] C --> C1["Leaf: 500โ€“699 ..."]
  • Data lives in fixed-size pages (often 4โ€“16 KB) arranged as a shallow, wide tree.
  • Reading key 42: follow pointers from the root to a leaf: a few page reads, even for billions of rows.
  • Writing: find the right leaf and update it in place. If the page is full, split it.
  • Crash safety: a write-ahead log records changes before pages are modified (Write-Ahead Log Explained).

How an LSM Tree Works

flowchart LR W["Write"] --> WAL[("WAL
(durability)")] W --> MEM["Memtable
(sorted, in memory)"] MEM -->|"full โ†’ flush"| L0["SSTable files
(sorted, immutable)"] L0 -->|"compaction:
merge + drop old versions"| L1["Larger SSTables
(next level)"] L1 -->|"compaction"| L2["Even larger
SSTables"]
  1. Write goes to the WAL and an in-memory sorted memtable. Fast.
  2. When the memtable fills, it's flushed to disk as a sorted, immutable SSTable file. Sequential write.
  3. Updates and deletes don't modify old files; they write newer versions (deletes write a "tombstone").
  4. Compaction merges SSTables in the background, keeping only the latest version of each key.

Reading: check the memtable, then SSTables from newest to oldest. A Bloom filter per file quickly rules out files that can't contain the key (Bloom Filter Explained).


The Trade-offs

B-tree LSM tree
Write pattern Random in-place updates Sequential appends
Write throughput Good Excellent
Point reads Excellent (one path) Good (memtable + several files, helped by Bloom filters)
Range scans Excellent Good, can be slower
Space usage Some fragmentation Old versions until compaction
Background work Page splits, vacuum (Postgres) Compaction (can cause spikes)
Used by PostgreSQL, MySQL InnoDB, SQLite Cassandra, RocksDB, ScyllaDB, HBase
Key takeaway: B-trees pay at write time to keep data perfectly organised for reads. LSM trees make writes cheap and pay later, during reads and background compaction.

Amplification: The Hidden Costs

Database engineers compare storage engines with three "amplification" measures:

  • Write amplification: how many bytes the disk actually writes per byte you write. Compaction rewrites data several times in LSM trees; B-trees rewrite whole pages for small changes.
  • Read amplification: how many places the database checks per read. Higher for LSM trees.
  • Space amplification: extra disk space used. LSM trees keep old versions until compaction.

You can't minimise all three at once. Every storage engine picks a balance.


Which Should You Choose?

  • Typical app with users, orders and transactions: a B-tree database (Postgres, MySQL). Most apps should start here.
  • Massive write volume (event logs, IoT sensors, chat history, metrics): LSM-based stores.
  • Embedded key-value store inside your service: RocksDB (LSM) is widely used.
  • Remember: indexes, schema design and query patterns usually matter more than the engine.

Frequently Asked Questions

Why are LSM trees faster for writes?

LSM trees buffer writes in memory and flush them to disk as sorted files using sequential writes, instead of updating pages in place at random disk locations. Sequential writes are much cheaper, so LSM-based databases handle very high write throughput.

Does PostgreSQL use a B-tree?

Yes. PostgreSQL's default index type is a B-tree, and MySQL's InnoDB engine stores tables and indexes as B+ trees. Both also use a write-ahead log for crash safety.

What is compaction in an LSM tree?

Compaction is a background process that merges sorted files (SSTables), discarding overwritten values and deleted keys. It keeps reads efficient and reclaims space, but uses disk I/O and CPU, which can affect performance during heavy compaction.


Conclusion

B-trees keep data sorted in place for fast reads and are the backbone of relational databases. LSM trees turn writes into fast sequential appends and organise data later through compaction, making them ideal for write-heavy systems. Knowing the trade-off helps you choose the right database and tune it.


Sources

Last verified: 2 November 2026.


Related reads: Write-Ahead Log Explained ยท Bloom Filter Explained ยท SQL vs NoSQL ยท PostgreSQL vs MySQL

I explain the tech behind everyday products. Follow on LinkedIn or X, or invite me to speak.