Understanding InnoDB Index Structure and Height Estimation

The author, a MySQL ACE and technical service director, introduces the fundamentals of InnoDB index storage, noting that InnoDB uses a B+Tree where the smallest storage unit is a 16 KB page.

Two kinds of indexes are described: the clustered index (the primary key or a unique key whose rows form the data pages) and secondary indexes, which store the indexed column as the key and the clustered index key as the value.

An index tree consists of three page types: root page (created when the index is first built and holds pointers to child pages), non‑leaf (internal) pages that point to leaf or other internal pages, and leaf pages that store the actual records. Each page has a level number; leaf pages are level 0, and the root level depends on the tree height.

Leaf pages contain a next‑record pointer, and records are stored in ascending order but not necessarily contiguously. Pseudo‑records called infimum and supremum represent the minimum and maximum values.

The article then presents three experiments with tables of 900 000 rows using different primary‑key types (INT, BIGINT, UUID). For each table it lists the number of records per non‑leaf and leaf page, record size, and shows screenshots of the page layouts.

Based on these measurements, the author demonstrates how to estimate the height of an index tree for each primary‑key type, providing visual charts for INT, BIGINT, and CHAR(36) (UUID) primary keys.

Finally, a reference link to an external blog post about InnoDB behavior without a primary key is included.