B-Trees vs. LSM-Trees: Database Storage Engine Architecture // Subroutine CS

When designing production storage engines, software engineers face a fundamental physical constraint: random disk I/O is orders of magnitude slower and more expensive than sequential disk I/O.

Whether building a low-latency cache, an analytical columnar warehouse, or an OLTP transactional database, your choice of underlying storage engine architecture dictates read latency, write throughput, write amplification, and recovery overhead.

1. Summary & Key Architectural Tradeoffs

Architecture Metric	B+ Tree Storage Engine	LSM-Tree Storage Engine
Write Pattern	In-place random page updates	Sequential append-only WAL & Memtable
Write Amplification	High (full page rewrite per key update)	Low to Medium (amortized via SSTable compaction)
Read Amplification	$O(\log_B N)$ single page fetch	Multiple SSTable levels (mitigated by Bloom filters)
Primary Use Cases	Traditional OLTP, mixed read/write workloads	High-ingest telemetry, time-series, write-heavy workloads
Flagship Engines	PostgreSQL, MySQL (InnoDB), SQLite	RocksDB, LevelDB, Cassandra, Pebble

2. Interactive B+ Tree vs. LSM-Tree Engine Simulation

Test the difference below between B+ Tree page insertions and LSM-Tree append-only Memtable flushes:

Database Storage Engine Architecture

Comparing In-Place B+ Tree Pages vs. Append-Only LSM-Tree Compaction

Insert Key (1-99):

Order M=4 (Max 3 keys / page node)

Root Index Node (RAM/Disk Page)

2050

Leaf Page #1

1015

Leaf Page #2

3042

Leaf Page #3

608599

B+ Tree initialized with Order M=4. Max 3 keys per node.

3. Storage Pipeline Comparison

graph TD
    subgraph LSM["LSM-Tree Pipeline (Append-Only)"]
    W["Write Request"] --> WAL["1. Disk Write-Ahead Log (WAL)"]
    W --> MEM["2. RAM Memtable (SkipList)"]
    MEM -->|Flush| SS["3. Level 0 Disk SSTable"]
    SS -->|Compaction| SS1["4. Level 1 Disk SSTable"]
    end

    subgraph BTree["B+ Tree Pipeline (In-Place)"]
    W2["Write Request"] --> BWAL["1. WAL Disk Log"]
    W2 --> PAGE["2. Read Page to RAM"]
    PAGE --> MUT["3. Mutate Key in RAM Page"]
    MUT --> WRITE["4. Rewrite 8KB Page to Disk"]
    end

4. Multi-Language Engine Code Implementation

Storage Engine Code Comparison

btree_page.cpp

C++20 (B+ Tree Page)

#include <cstdint>
#include <array>

// 4KB Aligned B+ Tree Page Node
#pragma pack(push, 1)
template <typename KeyType, typename ValueType, size_t PageSize = 4096>
struct BTreePage {
    uint16_t node_type;       // 0 = Internal, 1 = Leaf
    uint16_t num_keys;        // Active key count
    uint32_t right_sibling;   // Right leaf pointer for O(1) range scans
    
    std::array<KeyType, 128> keys;
    std::array<ValueType, 128> values;
};
#pragma pack(pop)

5. Architectural Guidance

Choose B+ Tree (PostgreSQL / InnoDB) when your workload is read-heavy, requires multi-key transactions, complex SQL joins, and strict point-lookup SLAs.
Choose LSM-Tree (RocksDB / Cassandra) when your application ingests high-volume telemetry, time-series data, or experiences heavy write throughput.