Parameters
About this exampleTree descent animation
About this example
Example query this animation executes
-- Non-covering secondary index lookup SELECT id, first_name, last_name, country_code FROM users WHERE email = 'alice@example.com'; -- idx_users_email contains only (email, id)
Switch the lookup-type dropdown to see PK-clustered vs covering-index vs non-covering variants of this query.
What you'll see in the animation
- The grey rectangles are B+tree pages. The top row is the root page, the middle rows hold internal pages and the bottom row holds leaf pages.
- A red diamond 'query token' appears above the root page and goes down one page at a time. Each step is one page read; Next step shows one read at a time.
- When the token arrives at a page, the page pulses yellow. That's the 'page is in the buffer pool now'.
- For non-covering secondary lookups, the secondary-tree leaf page stores the primary key (labelled 'PK = 42'), not the row. A dashed orange arrow links it to the clustered-tree leaf that holds the row: the key, not a disk address, is the link, so InnoDB then walks the clustered tree from its root page.
- That second walk is the extra I/O a covering index would eliminate.
- The simplified code beside the drawing highlights the lines each step runs.
Cost readout (updates live)
Fan-out (non-leaf) ?How many child pointers fit in one 16 KiB page. Higher fan-out means a shallower tree — fewer page reads per lookup.
—
Tree height ?Number of page levels from root to leaf. Each level is one disk page that InnoDB must read. A 1-billion-row table with BIGINT PK is only 4 levels deep.
—
Tree traversals ?A clustered-PK or covering-index lookup walks one tree. A non-covering secondary lookup walks two: the secondary index tree, then the clustered tree using the PK it found.
—
Pages touched ?Total page reads for this single-row lookup. Equals tree height times the number of traversals. Each page is 16 KiB by default.
—
Cold-cache I/O ?Worst-case: none of these pages are in the buffer pool yet, so every page is a disk read. In practice, the upper levels of the tree are almost always cached.
—
Complexity ?B+tree lookups are O(log n) — doubling the table size adds roughly one extra page read. Non-covering secondary adds a second tree walk: O(log users) + O(log users) = O(2 log n).
O(log users) = O(log n)
Pages touched vs table size (log–log)
Learn more — why is a non-covering secondary index slower?
InnoDB stores every table as a clustered B+tree on the primary key.
The leaf pages of that tree hold the full row. A secondary index is a
separate B+tree whose leaves hold (secondary_cols, primary_key),
not the row itself.
So a lookup by a non-covering secondary index has to:
- Walk the secondary B+tree down to a leaf, yielding
PK. - Walk the clustered B+tree using that
PKto fetch the row.
Two traversals, each the full height of its tree. That is why covering indexes — where the leaf already has every column the query asked for — are such an important tuning tool.
The fan-out formula here is
(page_size − 120) / (key_size + 9).
It's an approximation: real InnoDB records have variable-length headers and
leaf pages split at a 15/16 fill factor, so real fan-out is a bit lower.
The height is stable under that noise because it's a logarithm —
halving the real fan-out only adds one level of the tree for every
factor of the original fan-out.
Sources: MySQL 8.4 Reference Manual §17.6.2 (InnoDB Indexes),
§17.11.2 (File Space Management). Default
innodb_page_size = 16 KiB.