Modern Storage Architecture: B-Trees, LSM-Trees & Open Table Formats

Every transactional database (OLTP), petabyte-scale log search engine, and analytical data warehouse (OLAP) rests upon a single foundational determinant of performance: the storage engine. Beneath the high-level abstractions of SQL query planners or distributed key-value APIs, the storage engine governs how raw bytes are organized across NVMe solid-state blocks or cloud object storage, how concurrent mutations preserve ACID durability, and how physical I/O amplification is bounded.

In storage systems engineering, no single data structure can simultaneously minimize read latency, write overhead, and storage footprint. Formalized by the RUM Conjecture (Read, Update, Memory/Space Overhead), optimizing any two of these axes fundamentally requires sacrificing the third. This evergreen architectural guide dissects the three dominant storage paradigms powering modern infrastructure: update-in-place B+Trees, write-optimized Log-Structured Merge-Trees (LSM-Trees), and immutable Columnar Open Table Formats led by Apache Parquet, DuckDB, and Apache Iceberg.

1. The RUM Conjecture and NVMe I/O Amplification Mathematics

To evaluate the mechanical trade-offs between B+Trees and LSM-Trees, systems architects measure three primary ratios: Write Amplification Factor (WAF), Read Amplification Factor (RAF), and Space Amplification Factor (SAF). Write Amplification quantifies the ratio of physical bytes written to underlying non-volatile storage relative to the logical bytes issued by the application.

On modern NAND Flash NVMe SSDs, read and program (write) operations occur at the granularity of flash pages (typically 4 KB or 16 KB), whereas erase operations can only execute across entire erase blocks (often several megabytes in size) managed by the drive's internal Flash Translation Layer (FTL). When a storage engine performs frequent random in-place modifications of 8 KB or 16 KB database pages, the SSD controller's FTL garbage collector must relocate valid pages before erasing blocks—compounding both device-level write amplification, tail latency spikes, and NAND cell wear.

2. B+Tree Internals: Slotted Pages, Buffer Pools, and ARIES Recovery

Relational engines such as PostgreSQL (Heap + B-Tree indexes), MySQL InnoDB (Clustered B+Tree), and SQLite organize data into fixed-size pages (8 KB in PostgreSQL, 16 KB in InnoDB). Unlike textbook B-Trees that store data payloads inside both internal and leaf nodes, production B+Trees store only separator keys and child page IDs inside internal routing nodes, packing all actual row payloads (or heap tuple pointers) sequentially inside doubly-linked leaf pages.

Within each 8 KB page, records are structured using a Slotted Page layout. The top of the page begins with a fixed Page Header (containing the 64-bit Log Sequence Number pd_lsn, CRC32C page checksum, and free-space boundary pointers), immediately followed by an array of Line Pointers (Slot Array) that grows downward. Actual variable-length data tuples are allocated from the bottom of the page growing upward. Because external indexes reference a row by its Page Number and Slot Index (ItemId) rather than its exact byte offset, the storage engine can compact and defragment tuples inside a page without invalidating any index pointers.

+-----------------------------------------------------------------------+
| Page Header (24B): pd_lsn (8B) | pd_checksum | pd_lower | pd_upper    |
+-----------------------------------------------------------------------+
| Line Pointers / Slot Array (grows downward -->)                       |
| [Slot 0: offset 7920, len 180] [Slot 1: offset 7710, len 210] [Slot 2]|
+-----------------------------------------------------------------------+
|                       <--- Unallocated Free Space --->                |
+-----------------------------------------------------------------------+
|                      (<-- grows upward) Variable-Length Data Tuples   |
| ... [Tuple 2 (xmin, xmax, payload)] [Tuple 1] [Tuple 0: offset 7920]  |
+-----------------------------------------------------------------------+

Because pages are mutated in-memory inside the Buffer Pool and flushed asynchronously by background checkpointer threads, B+Tree engines guarantee crash durability through the ARIES (Algorithms for Recovery and Isolation Exploiting Semantics) protocol operating under a Steal/No-Force policy. No-Force means a committing transaction does not need to synchronously flush dirty 8 KB data pages to disk; it only needs to append a compact redo record to the sequential Write-Ahead Log (WAL) and issue fsync(). Upon crash recovery, ARIES executes three passes—Analysis, Redo (repeating history up to the crash state using page LSNs), and Undo (rolling back uncommitted transactions).

Multi-Version Concurrency Control (MVCC) in B+Tree systems follows two distinct architectural schools. InnoDB and Oracle employ In-Place Updates with Undo Logs: updating a row mutates the clustered B+Tree leaf page directly while copying the prior version into a rollback undo segment for snapshot readers. Conversely, PostgreSQL utilizes Append-Only Tuple Versioning, where every UPDATE inserts a brand-new tuple version into the heap and stamps visibility transaction IDs (xmin and xmax). While avoiding undo chain reconstruction for current reads, PostgreSQL's design requires continuous background autovacuum workers to reclaim dead tuples, update the Visibility Map, and prevent Transaction ID Wraparound.

3. LSM-Tree Internals: MemTables, Immutable SSTables, and Compaction

When workloads demand sustained high-velocity ingestion—such as time-series telemetry, distributed event streams, stateful stream processors (Apache Flink), or distributed SQL storage layers (CockroachDB, TiKV)—random page flushes in B+Trees saturate disk IOPS. The Log-Structured Merge-Tree (LSM-Tree), pioneered in Google Bigtable, LevelDB, Meta's RocksDB, and Apache Cassandra, eliminates random in-place disk updates entirely.

In an LSM-Tree engine like RocksDB, every incoming write (PUT, DELETE tombstone, or MERGE operand) is appended sequentially to an on-disk Write-Ahead Log and inserted into an in-memory sorted structure called a MemTable (typically implemented as a lock-free Concurrent SkipList). Because both operations are purely sequential or memory-resident, write throughput scales near the raw sequential bandwidth of the underlying storage medium.

4. Columnar Execution & SIMD Vectorization in Parquet and DuckDB

Both B+Trees and LSM-Trees are row-oriented storage engines: all columns of a record are stored contiguously. While optimal for fetching an entire user profile by primary key, row stores perform poorly on analytical queries (OLAP) that scan billions of records to aggregate only 3 out of 150 columns—wasting over 95% of memory bandwidth and polluting CPU cache lines with unused attributes.

Columnar formats such as Apache Parquet and in-process analytical engines like DuckDB employ a hybrid PAX (Partition Attributes Across) layout. Datasets are horizontally sliced into Row Groups (typically 128,000 rows or 64–512 MB), and within each Row Group, attributes are stored vertically as contiguous Column Chunks and Data Pages.

-- Vectorized analytical query execution in DuckDB directly over partitioned Parquet / Iceberg files:
EXPLAIN ANALYZE
SELECT
    region_code,
    date_trunc(class="text-[#7ee787]">'day', event_timestamp) AS event_day,
    count(*) AS total_requests,
    approx_quantile(latency_ms, 0.99) AS p99_latency_ms
FROM read_parquet(class="text-[#7ee787]">'s3://prod-telemetry-lake/events/year=2026/month=10/*.parquet')
WHERE status_code >= 500
  AND event_timestamp >= TIMESTAMP class="text-[#7ee787]">'2026-10-14 00:00:00'
GROUP BY ALL
ORDER BY total_requests DESC;

Modern analytical storage engines achieve orders-of-magnitude speedups through four mechanical optimizations: (1) Type-Specific Lightweight Compression—because a column page contains homogeneous values, Dictionary Encoding, Run-Length Encoding (RLE), Delta-Binary-Packing, and Frame-of-Reference (FOR) compress data 5x to 15x tighter than generic row compression; (2) Zone Map Min/Max Pruning—every Row Group and Data Page header records minimum, maximum, and null counts, enabling the query engine to skip entire gigabytes of irrelevant blocks before reading them; (3) Cache-Resident Vectorized Execution—instead of the classic Volcano tuple-at-a-time iterator model that incurs millions of virtual function calls and branch mispredictions, DuckDB processes fixed-size arrays (vectors of 2,048 values) that fit snugly inside the CPU's 32 KB L1 data cache using AVX-512 or ARM NEON SIMD instructions; and (4) Late Materialization, evaluating filter predicates directly on compressed dictionary integer codes before reconstructing wide strings.

5. Apache Iceberg Architecture: ACID Transactions Over Object Storage

For over a decade, cloud data lakes built on object stores (Amazon S3, Google Cloud Storage, Azure ADLS) suffered from the architectural limitations of the legacy Apache Hive directory layout: no multi-file ACID transactions, expensive and eventually-consistent directory LIST operations, inability to evolve partitioning schemes without full table rewrites, and unisolated partial writes visible to concurrent readers.

Apache Iceberg resolves these flaws by introducing a persistent, copy-on-write metadata tree above immutable Parquet data files. Rather than defining a table by physical directory paths, Iceberg tracks every individual file through a four-tier hierarchy anchored by an atomic pointer inside the Iceberg Catalog.

6. Comparative Storage Engine Architecture Matrix

The architectural matrix below summarizes the physical layout, I/O amplification profile, and workload trade-offs across modern production storage engines:

+--------------------------+------------------------+-------------------------+--------------------------+
| Architectural Dimension  | B+Tree (PostgreSQL /   | LSM-Tree (RocksDB /     | Columnar Lakehouse       |
|                          | InnoDB)                | Cassandra / Pebble)     | (Parquet + Iceberg)      |
+--------------------------+------------------------+-------------------------+--------------------------+
| Fundamental Storage Unit | Fixed Slotted Page     | MemTable + Immutable    | Row Group (64-512MB) +   |
|                          | (8 KB - 16 KB)         | SSTable Blocks          | Column Chunks            |
| Write I/O Pattern        | Random In-Place +      | Sequential Append-Only  | Immutable File Write +   |
|                          | Sequential WAL         | WAL + Compaction Merge  | Atomic Metadata Swap     |
| Write Amplification (WAF)| High (10x - 30x)       | Low-Moderate (3x - 10x) | Minimal (1x - 2x)        |
| Point Lookup Latency     | Ultra-Low (<0.5ms)     | Low (1-3ms, accelerated | High (Not designed for   |
|                          | O(log_B N) page hops   | by Bloom/Ribbon Filter) | OLTP point lookups)      |
| Analytical Scan Speed    | Low (Row-oriented)     | Moderate (Range scan)   | Extreme (SIMD + Pruning) |
| Space Amplification      | Moderate (~25-33%      | Very Low (~10% overhead | Very Low (5x-15x RLE &   |
|                          | page fragmentation)    | in Leveled Compaction)  | Dictionary compression)  |
| Target Production Role   | Low-latency OLTP &     | High-ingest KV stores,  | Analytical Lakehouse,    |
|                          | transactional systems  | stream state & logs     | AI curation & telemetry  |
+--------------------------+------------------------+-------------------------+--------------------------+

“Selecting a storage engine is never about finding a universally faster data structure; it is the discipline of aligning your application's access distribution with hardware physics—trading in-place page locality in B+Trees against sequential ingestion in LSM-Trees and vectorized SIMD density in columnar lakehouses.”