Peeling Back MySQL InnoDB: A Deep Dive into Its Storage Engine

1. Page Structure – The First Layer

MySQL stores data in units called pages . Understanding how a page looks is essential to grasp data placement. A page consists of:

Page Header (56 bytes) : holds statistics and control information, including pointers to the left and right sibling pages, forming a doubly‑linked list.

Virtual Records : a maximum and a minimum virtual record bound the range of keys stored in the page; they are compared using the primary key.

Record Heap : contains actual rows, split into live records and deleted records. Deleted rows form a free‑space list that links the gaps together.

Unallocated Space : the remainder of the page that can receive new rows.

Slog Area : a region useful for data retrieval (details omitted for later).

Page Tail (8 bytes) : stores a checksum for detecting page corruption.

2. Clustered Index – The Second Layer

InnoDB implements the primary key as a clustered index , which is a B+‑tree where the data rows are stored together with the index entries in primary‑key order. This means the physical layout of rows follows the logical order of the key.

The article contrasts two ordering models:

Physical ordering : inserting keys 10, 9, 8 requires moving existing rows each time, leading to heavy write‑amplification.

Logical ordering : new keys are linked via pointers (10 → 9 → 8) without moving existing rows.

Because InnoDB’s pages are linked by a doubly‑linked list, the logical order is preserved across pages, while the B+‑tree provides efficient range scans.

3. Slot Area – The Third Layer

Within a page, records are not searched by binary search; instead, InnoDB uses a Slot array that points to sub‑lists of records. The process is:

Locate the minimum and maximum virtual records.

Use the Slot array to perform a coarse binary search, selecting a sub‑list whose size is roughly equal.

Traverse the chosen sub‑list sequentially to find the exact record.

This approach resembles a skip‑list: each Slot acts like a higher‑level pointer that narrows the search range before a linear scan.

4. Insertion and Space Reclamation

When inserting a new row, InnoDB first reuses space from the free‑space list; if that is insufficient, it uses unallocated space. However, fragmentation can occur when old rows are larger than new rows, leaving unusable gaps.

After many insert‑delete cycles, a table may need to be rebuilt (e.g., via a double‑copy or “online rebuild”) to compact the pages.

5. Summary

The article walks through the three “layers” of InnoDB storage:

Page layout with header, virtual records, record heap, free‑space list, unallocated space, Slog, and tail.

Clustered index (B+‑tree) that orders pages logically and stores data together with the primary key.

Slot array that enables an approximate binary search followed by linear traversal inside sub‑lists.

Understanding these mechanisms reveals why InnoDB can provide both efficient reads (through logical ordering and slot‑based search) and reasonable write performance (by reusing free space and limiting page moves).