B-Trees and Page-Based Storage (PostgreSQL, MySQL InnoDB)

For over four decades, the B+ Tree has been the foundational data structure powering relational database storage engines, including PostgreSQL, MySQL (InnoDB), Oracle, Microsoft SQL Server, and SQLite.

To engineer high-performance systems, you must understand how B+ Trees organize physical disk pages, execute binary searches inside memory buffers, manage node splits, and handle the steep penalty of Write Amplification.

---

1. Why B+ Trees Dominate: Branching Factor & Low Tree Height

Unlike in-memory binary search trees (AVL, Red-Black Trees) where each node has a branching factor of 2 ($B=2$), database B+ Trees are optimized for disk block size ($4\text{KB},8\text{KB},16\text{KB}$).

The Branching Factor Equation:

With a page size of $16\text{KB}$ (MySQL InnoDB default) and an average index key + pointer size of $32\text{ bytes}$:

$B=\frac{16,384\text{ bytes}}{32\text{ bytes}}\approx 500\text{ pointers per node}$

$\text{Height }h=\lceil {\log }_B(N)\rceil$

Key Takeaway: A 3-level B+ Tree can index 125 million rows with only 3 disk reads, and because the root and internal levels remain permanently cached in RAM, most single-row point lookups require exactly 1 physical disk read!

---

2. Anatomy of a Database Page: The Slotted-Page Architecture

In page-based engines, files on disk are divided into fixed-size chunks (e.g. $8\text{KB}$ in PostgreSQL, $16\text{KB}$ in InnoDB).

To support variable-length columns (such as VARCHAR and JSONB) without fragmentation, pages use a Slotted-Page Layout:

Why Slotted Pages?

• An index pointer never points to a raw byte offset on disk; it points to a Tuple ID (TID) = (Page Number, Slot Index).
• If a row is updated and changes size, the database can move the tuple anywhere inside the page and update the slot pointer, without invalidating secondary indexes across the entire database!

---

3. Node Splitting and Page Merging Mechanics

When an INSERT arrives at a leaf page that has insufficient free space, the engine must perform a Page Split:

The 50/50 Split vs Right-Leaning Split:

• Random Inserts: Pages split 50/50, resulting in an average page fill factor of $\approx 67\%$ (33% wasted space due to fragmentation).
• Auto-Increment Monotonic Inserts: InnoDB detects sequential inserts and performs a 90/10 or 100/0 Split, keeping pages 100% full and avoiding wasted space.

---

4. Concurrency Control: Latch Crabbing (Coupling)

How do multiple threads traverse and mutate a B+ Tree simultaneously without corrupting node pointers?

Storage engines use Latch Crabbing (Latch Coupling):

---

5. The Fatal Flaw of B-Trees: High Write Amplification

While B+ Trees deliver stellar $O(\log N)$ point reads and range scans, they suffer from severe Write Amplification:

$\text{Write Amplification Factor (WAF)}=\frac{\text{Bytes Written to Physical Storage}}{\text{Bytes of Logical Application Data}}$

The Math of B-Tree Write Amplification:

Suppose you update a single 20-byte user_status string in a row:

1. Engine writes the WAL delta record: $\approx 80\text{ bytes}$.
2. Engine writes the modified $16\text{KB}$ page to MySQL's Doublewrite Buffer: $16,384\text{ bytes}$.
3. Engine flushes the dirty $16\text{KB}$ table page to physical disk: $16,384\text{ bytes}$.
4. If a secondary index page is updated, repeat steps 2 & 3: $+32,768\text{ bytes}$.

$\text{Total Physical Bytes Written}\approx 65,616\text{ bytes for a 20-byte update!}⟹\text{WAF}>3,000\times$

On write-heavy workloads (such as IoT telemetry, high-frequency logs, and real-time streaming), B+ Trees saturate SSD write channels and trigger flash drive wear-out.

---

6. Code Deep-Dive: In-Memory B+ Tree Node Search & Split Engine

---

7. Production Failure Postmortem: Table Bloat & Latch Contention

Incident Overview:

In 2020, an e-commerce marketplace experienced 10-second checkout query timeouts during Black Friday, caused by severe B-Tree page bloat and root-node latch contention in PostgreSQL.

What Happened:

1. High-frequency inventory decrement queries repeatedly updated stock rows: UPDATE items SET stock = stock - 1.
2. PostgreSQL's MVCC architecture writes a new tuple version for every update and marks the old version as dead.
3. The autovacuum worker could not keep up with the update volume, causing leaf pages to bloat with 85% dead tuples.
4. B+ Tree height grew from 3 levels to 5 levels, expanding the index size from $4\text{GB}$ to $38\text{GB}$ (exceeding server DRAM buffer pool).
5. All concurrent checkout workers competed for read/write latches on internal index pages, causing CPU thread starvation.

Remediation:

• Scheduled off-peak pg_repack to rebuild bloated B+ Trees online with zero table locking.
• Tuned PostgreSQL autovacuum settings (autovacuum_vacuum_scale_factor = 0.02) to aggressively reclaim dead slots before page splits occur.

---

8. Chapter Summary & B-Tree Storage Invariants