Storage Engines: B+ Trees & Slotted Pages

Module Overview

The Storage Engine is the internal subsystem responsible for reading, writing, caching, and organizing persistent records on block storage devices (SSDs/NVMe). In this sixth installment, we analyze the low-level physical architectures that dictate database I/O performance: the Slotted-Page architecture, the internal lifecycle of the Buffer Pool, replacement heuristics (LRU, Clock, 2Q), the mechanics of B+ Tree Indexing (fan-out, splits, merges), and high-throughput Log-Structured Merge-Trees (LSM-Trees).

1. Disk Block Layout & The Slotted-Page Architecture

Operating systems and block devices transfer data in fixed-size blocks (typically 4KB to 16KB). Database storage engines structure their physical table files into corresponding discrete Pages (or blocks, e.g., PostgreSQL 8KB, MySQL InnoDB 16KB).

Because tuples within real-world tables possess variable-length attributes (such as VARCHAR or TEXT), modern storage engines organize pages using the Slotted-Page Architecture:

Slotted-Page Layout Anatomy

1. Page Header (Top of Page): Fixed-size metadata containing the page LSN (Log Sequence Number for crash recovery), transaction identifiers, free-space pointer, and total slot count.

2. Slot Array (Grows Downward): An array of 4-byte slot entries, each recording an exact byte offset and length pointing to a tuple within this page. The slot array expands from top to bottom.

3. Free Space Window (Center): The unallocated gap between the end of the slot array and the start of the lowest tuple payload.

4. Tuple Payloads (Grows Upward): Actual row byte streams written starting from the bottom of the page moving toward the top.

Record Identifier (RID): To prevent moving or resizing a variable-length row from breaking external foreign keys or secondary indexes, rows are globally addressed via a tuple identifier: RID = (Page_ID, Slot_Number). If a row expands or is relocated within the page during defragmentation, only its internal slot offset updates; its external RID remains invariant!

2. Buffer Pool Architecture & Frame Eviction Policies

Reading from physical disk or NVMe drives incurs high latency compared to RAM (nanoseconds vs. microseconds). The Buffer Pool is an in-memory cache managed entirely in user space by the DBMS, partitioned into fixed-size Frames that mirror disk page dimensions.

Pin Count & Dirty Pages

Each frame tracks a pin_count (active worker threads currently accessing the page, preventing eviction) and a is_dirty flag (indicating the in-memory page was modified and must be flushed to disk before frame reuse).

Eviction Heuristics (Clock / 2Q)

Naïve LRU queues suffer from cache pollution during large sequential table scans. Production engines use the Clock Algorithm or 2Q / LRU-K, tracking multiple reference queues to protect frequently accessed root index pages from being flushed by one-time analytical batch queries.

3. B+ Tree Index Architecture

The B+ Tree is the dominant persistent index data structure in relational database systems (e.g., MySQL InnoDB, PostgreSQL, SQLite). It maintains the fundamental invariant that all leaf nodes reside at the exact same depth, guaranteeing strictly logarithmic $O(\log N)$ search, insertion, and deletion complexity.

B+ Tree Structural Invariants

High Fan-Out ($M$): Internal nodes store up to $M$ child page pointers and $M-1$ separating search keys. In typical 8KB/16KB pages, $M$ reaches 100 to 1,000+, allowing a 4-level B+ tree to index billions of records in just 3 to 4 disk page lookups.
Internal Nodes vs. Leaf Nodes: Internal nodes store only guiding keys and child page pointers without tuple payloads. Leaf nodes store search keys alongside actual tuple data or RIDs.
Doubly-Linked Leaf Chain: Leaf pages maintain explicit forward and backward pointers (prev_page, next_page), transforming range scans (WHERE age BETWEEN 25 AND 35) into linear pointer traversals without revisiting parent levels.

4. Log-Structured Merge-Trees (LSM-Trees)

While B+ trees optimize for reads, random updates incur heavy write amplification and random disk I/O. In write-heavy distributed engines (e.g., RocksDB, Apache Cassandra, ClickHouse), LSM-Trees replace random in-place updates with sequential append-only writes:

1. MemTable & WAL

Incoming writes are appended sequentially to a Write-Ahead Log on disk for durability, then inserted into an in-memory sorted data structure (SkipList or Red-Black Tree) called the MemTable.

2. Immutable SSTables (Sorted String Tables)

When the MemTable reaches size capacity, it is frozen and flushed to disk as an immutable, sorted SSTable organized into hierarchical numbered levels ($L_0, L_1, \dots$).

3. Compaction & Bloom Filters

Background compaction merges overlapping SSTables, purging obsolete versions and deletion tombstones. Probabilistic Bloom Filters in RAM intercept read queries, identifying whether a given key definitely does not exist in an SSTable before performing any disk I/O.

Next in Curriculum

In Part 7: Query Execution Engines: Volcano Iterators & Cost-Based Optimization, we explore how query execution engines read pages through the Volcano iterator model and cost-based plan generation.