Inside MySQL InnoDB: How B+Tree Indexes and Data Pages Really Work

1. Abstract

MySQL InnoDB uses B+‑tree indexes to accelerate SQL queries, but the internal layout of these indexes and the underlying storage structures are rarely examined. This article starts from the MySQL row record format and progressively explores data pages, clustered indexes, secondary indexes, and finally offers practical indexing recommendations.

2. Record Storage Format: COMPACT Row

Each row in MySQL is stored according to the table definition, but InnoDB adds extra hidden columns to each record. Variable‑length fields (VARCHAR, VARBINARY, TEXT, BLOB) are stored with length information, and three hidden columns are added:

DB_ROW_ID – a unique identifier used as a primary key when no explicit primary key exists.

DB_TRX_ID – the transaction ID.

DB_ROLL_PTR – the rollback pointer.

These hidden columns, together with the user columns, form the complete row structure.

3. Data Page – The Box That Holds Records

Data pages are the basic unit of I/O in InnoDB (default size 16 KB). A page stores user records in the User Records area, free space in Free Space , and two fixed pseudo‑records: infimum (minimum) and supremum (maximum). The infimum record contains the ASCII string “infimum”, and the supremum record contains “supremum”.

Rows are linked in a single‑direction chain via the next_record pointer, ordered by the primary key. Deleting a row marks it as deleted but does not immediately reclaim space; the chain is updated accordingly.

4. Page Header and Directory

The Page Header records metadata such as the number of records, the offset of free space, and the count of slots in the Page Directory . Each slot (2 bytes) stores the offset of the last record in a group, enabling binary search within the page.

5. Fast Lookup: B+Tree Indexes

InnoDB’s primary key index is a clustered B+‑tree where leaf nodes store the actual row data. Secondary (non‑clustered) indexes also use B+‑trees, but leaf entries contain the indexed column values plus the primary‑key pointer, requiring a “row lookup” (回表) to fetch the full row.

6. Composite Indexes

Composite indexes store rows ordered first by the leftmost column, then by subsequent columns. They support left‑most prefix queries, e.g., a three‑column index (C1, C2, C3) can satisfy queries on (C1), (C1, C2), or (C1, C2, C3).

7. Index Advantages and Drawbacks

Advantages include fast point lookups, range scans, order‑by and group‑by acceleration, and the possibility of covering indexes that avoid row lookups.

Drawbacks are increased storage consumption, maintenance overhead on INSERT/UPDATE/DELETE (especially when primary‑key order is not monotonic), and potential performance penalties from excessive or low‑selectivity indexes.

8. Practical Recommendations

Create indexes only on columns used for search, sorting, or grouping.

Prefer columns with high cardinality and small data types.

For long text columns, index a prefix (e.g., INDEX(col(10))).

Use covering indexes to eliminate the need for row lookups.

Avoid using functions on indexed columns in WHERE clauses.

9. Sample SQL

CREATE TABLE record_format_demo(
  c1 VARCHAR(10),
  c2 VARCHAR(10) NOT NULL,
  c3 CHAR(10),
  c4 VARCHAR(10)
) CHARSET=ascii ROW_FORMAT=COMPACT;

INSERT INTO record_format_demo(c1,c2,c3,c4) VALUES
  ('aaaa','bbb','cc','d'),
  ('eeee','fff',NULL,NULL);

CREATE TABLE page_demo(
  c1 INT,
  c2 INT,
  c3 VARCHAR(10000),
  PRIMARY KEY (c1)
) CHARSET=ascii ROW_FORMAT=COMPACT;

INSERT INTO page_demo VALUES
  (1,100,'aaaa'),(2,200,'bbbb'),(3,300,'cccc'),(4,400,'dddd');

These examples illustrate how rows are stored, how pages are filled, and how indexes are built and used.