Unlocking MySQL InnoDB Indexes: Deep Dive into Row Formats and B+Tree Mechanics

Introduction

Recently I discussed indexes with a friend and decided to write a systematic article covering MySQL InnoDB indexes.

Common questions: B‑Tree usage, transaction isolation implementation, data persistence after power loss, join algorithms, and cost estimation for SQL optimization.

Row Formats

Compact

Compact is a space‑efficient row format that stores extra metadata alongside user data. It uses a fixed header and variable‑length field list.

Example of inserting two rows and how the Compact format looks.

Variable‑Length Field List

Stores length of each variable‑length column (VARCHAR, TEXT) in reverse order. The size is determined by M (max length), W (max bytes per character), and L (actual length). Formula: if M*W > 255 then use 2 bytes, otherwise 1 byte.

NULL Value List

Bitmask indicating which columns are NULL, stored in reverse column order.

Record Header

Fixed 5‑byte header containing flags, transaction ID, rollback pointer, etc.

Transaction ID

6‑byte identifier for the transaction that created the record.

Rollback Pointer

7‑byte pointer used for MVCC rollback.

Real Data Columns

Shows how actual column values are stored after the headers.

Page Structure

Record Chain

Records are linked via the next_record pointer, forming a singly linked list within a page.

Infimum and Supremum

Special pseudo‑records representing the minimum and maximum keys in a page.

Page Directory (Slot Array)

Maps logical record numbers to physical offsets, enabling binary search within a page.

Page Header

56‑byte fixed header storing page state, LSN, and other metadata.

File Trailer

8‑byte checksum (FIL_PAGE_END_LSN) used to verify page integrity after a crash.

InnoDB B+Tree Index

InnoDB stores clustered (primary) indexes as a B+Tree where leaf pages contain the full row. Non‑clustered (secondary) indexes store the indexed columns plus the primary key.

Root → internal nodes (page directories) → leaf pages → rows.

When a page becomes full, it splits; some records may be moved to a new page, and the parent node is updated.

Composite Indexes

Composite indexes sort by the first column, then the second, and so on. Queries must include the leftmost column(s) to use the index efficiently (left‑most prefix).

Examples of queries that use or fail to use a composite index are illustrated.

Index Usage Tips

Index only columns used for search, sorting, or grouping.

Keep indexed column types small.

Consider prefix indexes for long strings.

Avoid page splits by using monotonic primary keys (e.g., auto‑increment).

Remove duplicate or redundant indexes.

Prefer covering indexes to avoid back‑table lookups.

Conclusion

This article covered the fundamentals of InnoDB row formats, page layout, B+Tree organization, and practical indexing strategies. The next part will dive into cost‑based optimization, EXPLAIN analysis, and transaction internals.