Storage Engines: B-Tree / LSM / Bw-Tree

A storage engine is the lowest layer of a database — the part that takes a logical operation like “set key X to value Y” and turns it into actual writes to disk, then turns “read key X” back into the right bytes. Above it sits the query planner, the network protocol, the consistency layer. Below it sits the operating system and the hardware.

Three families dominate the landscape. Each makes different trade-offs, and those trade-offs explain why one database is great at writes, another at reads, another at both. Cosmos DB uses a fourth, less famous descendant — the Bw-tree.

B-Tree: balanced, page-based, classic

The B-tree (and its more common variant, B+ tree) has been the default choice since the 1970s. PostgreSQL, MySQL InnoDB, MongoDB WiredTiger, SQL Server — all B-tree under the hood.

The structure:

                    [50, 100]                       ← internal page
                   /     |     \
              [10,30] [60,80] [110,150]             ← internal pages
              / | \   / | \    / | \
            ...     ...     ...                    ← leaf pages (with data)

• Fixed-size pages (typically 4–16 KB) hold sorted keys.
• Internal pages route to child pages.
• Leaf pages hold the actual data (or pointers to data).
• Updates rewrite the page in place. If the page overflows, it splits into two. If a sibling underflows, they merge.

Strengths

• Read latency is predictable — at most a handful of disk seeks (height ≈ log_B(N)).
• Range scans are fast — leaves are linked, so you walk sequentially.
• Reasoning is simple — it’s a tree.

Weaknesses

• Write amplification. Updating a single 100-byte field requires rewriting the whole 8 KB page. With WAL + index updates + buffer-pool flushes, one logical write becomes 10–30 physical writes.
• Random I/O. Modifying scattered keys means scattered page rewrites. SSDs handle this OK; spinning disks don’t.
• Concurrent updates need locks. B-trees use latches (lightweight locks) on pages during writes. Under heavy contention, latches become bottlenecks.

LSM Tree: write-optimized, append-everywhere

Log-Structured Merge trees flip the assumption — instead of optimizing for reads with in-place updates, they optimize for writes by appending everywhere.

WRITE PATH                                READ PATH

write → memtable                          read → memtable + L0 + L1 + L2 + ...
         (in-mem sorted)                          (check each level)
         |
         v full →
   flush as SSTable (immutable)                Bloom filters
         |                                     prune unnecessary
         v compaction →                        SSTable lookups
   merge SSTables in background
   (level 0 → level 1 → ...)

• Writes go to an in-memory memtable — a sorted in-memory tree (skip-list or similar). Single-digit-microsecond writes.
• When the memtable fills, it’s flushed to disk as an immutable SSTable (Sorted String Table). Flush is a sequential write — much faster than B-tree’s random writes.
• Reads check the memtable first, then each SSTable level until they find the key.
• Compaction runs in the background — merging SSTables, removing obsolete versions, eliminating tombstones.

Strengths

• Sequential writes — friendly to all storage media, especially SSDs and HDDs.
• High write throughput — Cassandra easily hits 10–100K writes/sec/node.
• Compaction is async — foreground writes don’t pay full amortization cost.

Weaknesses

• Read amplification — a key might exist in 5+ SSTables. Bloom filters prune most lookups, but worst-case reads are slower than B-tree.
• Compaction I/O — compaction competes with foreground reads. Tail latency spikes when compaction runs.
• Space amplification — until compaction merges, the same key can have multiple obsolete copies on disk.

Used by — Cassandra, ScyllaDB, RocksDB (and everything built on it — TiKV, CockroachDB’s storage layer), LevelDB, BigTable, HBase.

Bw-Tree: B-tree logic, append-only physics

The Bw-tree, designed at Microsoft Research and used inside Cosmos DB and SQL Server’s Hekaton in-memory engine, gets the read profile of a B-tree with the write profile of an LSM tree.

The trick — immutable pages with a mapping table.

   Logical PageID  ──→  [Mapping Table]  ──→  Physical address of latest delta

   Updates append a delta to the page's chain (Compare-And-Swap on mapping):

      [Page V0] ← [Δ insert(7)] ← [Δ delete(4)] ← [Δ insert(9)]
                                                      ↑
                                                  CAS here

• Every B-tree page has a logical PageID.
• A mapping table translates PageID → physical address.
• Updates don’t rewrite pages. They append a delta record (an insert, delete, etc.) and atomically swing the mapping-table pointer with a Compare-And-Swap.
• Reads follow the chain of deltas from newest to base page, applying them in reverse-chronological order.
• When chains get too long, a background consolidation rewrites the chain as a fresh page (also via CAS).

Strengths

• Lock-free. No latches anywhere — concurrent updates are CAS-based. Scales linearly with CPU cores.
• Flash-friendly. All writes are sequential appends. No in-place page rewrites.
• B-tree reads. The logical structure is still a B-tree — point reads and range scans are efficient.

Weaknesses

• Complexity. The implementation is significantly more involved than B-tree or LSM. Few systems have the engineering capacity to build one well.
• Consolidation cost. Long delta chains must be consolidated, which is similar in spirit to LSM compaction.

Used by — Cosmos DB (per-partition), SQL Server Hekaton, a small handful of research systems.

Why this matters even though you can’t choose

You don’t get to pick Cosmos’s storage engine — it’s Bw-tree, end of story. But understanding the family explains so much:

• Why writes cost more than reads. Bw-tree appends are cheap, but they still cost RUs because the index updates ripple to multiple delta chains. Lesson V07 (Indexing) shows how to limit that.
• Why range queries on the partition key are cheap. Bw-tree leaves are linked — a range scan is a sequential walk.
• Why deletes are still expensive. A delete is just another delta in the chain; the actual space isn’t reclaimed until consolidation runs.
• Why the partition key matters at the storage layer. Each partition has its own Bw-tree. Cross-partition queries fan out across N independent trees.

Where this connects

• F1 Replication — replication runs above the storage engine. Each replica has its own Bw-tree; consensus keeps them in sync.
• F4 Cosmos Architecture — the Bw-tree sits inside each replica, below the indexing layer.
• V07 Indexing — every indexed JSON path is a separate Bw-tree. Cutting unused indexes cuts write amplification.
• V09 Request Units — the Bw-tree’s append-only design is why writes cost ~5–7 RUs and reads cost ~1 RU. Different engine, different ratio.

If you’re building a database from scratch, the engine choice is consequential. If you’re using a managed system like Cosmos, the engine choice has been made for you — and knowing why it was made tells you what the system will be good at and what it won’t.