Understanding InnoDB Data Pages, Index Directories, and B+ Tree Indexing

Building on the previous discussion about the Buffer Pool, each InnoDB data page (the smallest unit of MySQL data operations) is loaded from disk into the Buffer Pool, modified there, and later flushed back to disk by an asynchronous thread.

Data Page

Every data page is 16kb in size and consists of several sections (header, free space, row data, etc.). When performing crud operations, MySQL reads the page from disk into the Buffer Pool, updates it, and eventually writes it back.

The minimum unit for MySQL data manipulation is a data page, and each page contains multiple rows.

Each data page defaults to 16kb and is composed of several parts as shown in the diagram above.

Free Space

Before any rows are written, a page contains only free space. As rows are inserted, the free space shrinks until it is exhausted, at which point a new page is allocated.

Double‑Linked List

The page header stores metadata such as the current page number, page type, tablespace ID, previous page number, and next page number. These pointers form a double‑linked list that connects all data pages.

Within a page, rows are stored in primary‑key order, each row pointing to the next row, forming a singly linked list.

This structure is inefficient for lookups because searching by primary key ID requires scanning the singly linked list.

Data Page Directory

The data page directory stores pairs of primary‑key values ( ID) and their row offsets, enabling binary search within a page.

Using the directory, the engine can quickly locate a row without scanning the entire page.

Index

Without an index, MySQL must perform a full‑table scan, which is prohibitively slow for large tables.

Page Split

If the primary key is not monotonically increasing, inserting a row may require moving existing rows to a new page—a process called a page split.

Move row with id=6 from page 0 to page 1

Update page 1 directory

Move row with id=3 from page 1 to page 0

Update page 0 directory

Primary‑Key Directory (Index)

The primary‑key directory (a type of index) records the minimum primary‑key value of each data page together with the page number.

Search steps:

Binary‑search the primary‑key directory to locate the target data page

Enter the data page and binary‑search its page directory to find the exact row

When the table contains millions of rows, the primary‑key directory itself may become large, so InnoDB stores it across multiple index pages .

Index Page

An index page stores index information; its header includes a page‑type field to distinguish it from regular data pages.

Index pages contain two kinds of entries: (1) minimum primary‑key value with the index‑page number, and (2) minimum primary‑key value with the data‑page number.

B+ Tree Structure

Multiple index pages are organized into a B+ tree, allowing efficient binary search across the entire index.

The overall search process becomes:

Binary‑search the primary‑key index (B+ tree) to find the appropriate index page

Binary‑search the index page to locate the target data page

Enter the data page, binary‑search its page directory, and retrieve the row

This concludes the walkthrough from data pages to index pages, illustrating how InnoDB optimizes data retrieval.