B-Trees vs LSM-Trees: The Storage Engine Wars in PostgreSQL and RocksDB

At the heart of every database is an indexing storage engine. The database world is divided between two philosophies: B-Trees and Log-Structured Merge-Trees (LSM-Trees).

1. B-Trees: In-Place Page Modification

Used by PostgreSQL, MySQL (InnoDB), and SQLite. Self-balancing search trees stored in fixed 4KB-16KB pages on disk.

• Advantage: Lightning-fast point lookups and range scans.
• Disadvantage: Random disk writes and write amplification on heavy insert workloads.

2. LSM-Trees: Append-Only Immutable Architecture

Used by RocksDB, Cassandra, and Bigtable. Writes go into an in-memory MemTable, flushed sequentially to immutable SSTable files on disk.

Practice tree structures in our Binary Search Trees Target!