DDIA Learn — Designing Data-Intensive Applications

Storage engines are the library components that databases use to store and retrieve bytes on disk. The two dominant families are log-structured merge (LSM) trees and B-trees — each optimizing for different workloads.

LSM-Trees vs B-Trees

B-trees update pages in place — predictable read latency, but random writes can be slow on spinning disks. LSM-trees append writes to a log, then compact sorted segments — excellent write throughput at the cost of occasional read amplification during compaction.

Real-world engines

RocksDB and LevelDB use LSM-trees. PostgreSQL and MySQL InnoDB use B-trees. Choosing an engine is choosing a read/write trade-off.

In practice

Cassandra, ScyllaDB, and RocksDB-backed stores favor LSM-trees for high write throughput. PostgreSQL, MySQL InnoDB, and SQL Server use B-tree variants for predictable OLTP reads. Redis keeps everything in memory with hash tables and skip lists — a different trade-off entirely.

Google at scale

Bigtable and LevelDB pioneered LSM-trees for Google's indexing and analytics pipelines — append-heavy writes with background compaction. Spanner layers B-tree pages on top of a distributed LSM for OLTP with global consistency.

typescript — LSM append vs B-tree in-place update

// Storage engine trade-off: LSM append vs B-tree in-place update
// LSM (RocksDB / Cassandra): batch writes to memtable → SSTable segments
await rocksdb.put(key, value); // append-only, compaction merges later

// B-tree (PostgreSQL InnoDB): update page in place on disk
await db.query("UPDATE users SET balance = $1 WHERE id = $2", [newBal, id]);
// Predictable reads; random writes cost more on spinning disks

Data Structures That Power Your Database

LSM-Trees vs B-Trees