B-Trees vs. LSM-Trees: Choosing Your Storage Engine

At the heart of every database is a storage engine that decides how data is laid out on disk. The two most dominant architectures are B-Trees and LSM-Trees. Understanding the difference is key to picking the right database for your workload.

1. B-Trees: The Read-Optimized Classic

Used by: PostgreSQL, MySQL, MongoDB, Oracle.

• The Structure: A B-Tree is a self-balancing tree that stores data in fixed-size blocks (pages).
• The Process: When you update a record, the B-Tree finds the specific page and overwrites it in place.
• Pros: Fast, predictable read performance ((\log N)$). Great for range scans and applications where data is read more often than written.
• Cons: Write amplification. Every small update requires reading and rewriting an entire page (usually 4KB or 8KB).

2. LSM-Trees: The Write-Optimized Modernist

Used by: Cassandra, RocksDB (used by Meta), LevelDB, DynamoDB.

• The Structure: A Log-Structured Merge Tree doesn't update data in place. Instead, it turns all writes into sequential appends.
• The Process:
  1. Writes go to an in-memory Memtable.
  2. When the Memtable is full, it's flushed to disk as an immutable SSTable.
  3. In the background, a Compaction process merges these files.
• Pros: Incredible write throughput. Writes are sequential, making them extremely fast on both HDD and SSD.
• Cons: Read amplification. To find a key, the engine may have to check the Memtable and multiple SSTables. (Though Bloom Filters help mitigate this).

3. The Trade-off: Read vs. Write Amplification

• Read Amplification: One logical read requires multiple physical disk reads. High in LSM-Trees.
• Write Amplification: One logical write requires multiple physical disk writes. High in B-Trees (due to page fragmentation and WAL overhead).

Summary

• Choose B-Trees (Postgres/Mongo) for standard CRUD apps, CMS systems, and relational data where query latency for reads is the primary concern.
• Choose LSM-Trees (Cassandra/RocksDB) for logging, telemetry, IoT data, and high-frequency messaging systems where you need to ingest millions of events per second.

By matching your data access patterns to the underlying storage structure, you can avoid costly performance bottlenecks as your system scales.