Deep Dive into Modern Database Indexing: B-Trees vs LSM-Trees

The Core Database Dilemma: Reads vs Writes

At the heart of every storage engine lies an engineering trade-off: How do we make search fast without making insertions prohibitively expensive?

A raw append-only log achieves optimal write throughput ($O(1)$ writes), but reading requires a full table scan ($O(N)$ reads). Conversely, keeping an array sorted enables $O(\log N)$ binary search, but inserting an item at the beginning requires moving all $N$ elements ($O(N)$ writes).

To solve this, modern databases leverage two dominant data structures:

1. B-Trees (specifically B+ Trees): Powering PostgreSQL, MySQL (InnoDB), and SQLite.
2. LSM-Trees (Log-Structured Merge Trees): Powering RocksDB, Cassandra, ScyllaDB, and ClickHouse.

---

1. Anatomy of B+ Trees

In a B+ Tree, every node is sized to match one disk block (typically 4KB or 8KB).

Key Characteristics:

• Balanced Depth: All leaf nodes reside at the exact same depth.
• High Fan-out: Each interior node can hold hundreds of keys, keeping tree height extremely shallow ($3-4$ levels for billions of records).
• Sequential Leaf Chaining: Leaf nodes are linked via doubly linked lists, making range queries like WHERE age BETWEEN 20 AND 30 exceptionally fast.

             [ 50 | 100 ]
           /      |       \
   [ 10 | 30 ] [ 60 | 80 ] [ 120 | 150 ]
        │           │             │
  Leaves: [1..49] <-> [50..99] <-> [100..200]

The Bottleneck: Random I/O and Write Amplification

Updating a row in a B-Tree requires an in-place overwrite. If the targeted leaf page is not in the RAM buffer pool, the database must perform a random disk seek to fetch the page, modify it, and flush it back.

---

2. Anatomy of LSM-Trees (Log-Structured Merge Trees)

LSM-Trees completely eliminate random writes by turning all mutations into sequential appends.

Structural Components:

1. WAL (Write-Ahead Log): Appended sequentially on disk for crash recovery.
2. MemTable: An in-memory sorted data structure (typically a SkipList or Red-Black Tree).
3. SSTables (Sorted String Tables): Immutable, sorted files persisted on disk across generational levels ($L_0, L_1, L_2$).
4. Bloom Filters: Probabilistic bit arrays that verify if a key definitely does NOT exist in an SSTable before performing any disk I/O.

Writes ──> [ Write-Ahead Log ] (Sequential Disk)
   │
   ▼
[ MemTable (RAM) ] ── (Flushed when full) ──> [ SSTable Level 0 ]
                                                       │
                                                 (Compaction)
                                                       ▼
                                             [ SSTable Level 1 ]

---

3. Comparison Matrix

---

Conclusion

Understanding the storage engine underneath your database enables you to make informed infrastructure decisions. If your workload is $80%$ reads, traditional B+ Trees in Postgres deliver unmatched latency. If you are handling millions of sensor writes per second, an LSM-Tree architecture will maximize hardware efficiency.