How Many Levels Does a MySQL InnoDB B+ Tree Need for 20 Million Rows?

Hello, I am Su San.

MySQL's default storage engine is InnoDB, which supports transactions, row‑level locking, primary keys, foreign keys, and stores indexes using B+ trees.

InnoDB Storage

In InnoDB, data is stored as an index‑organized table; each index corresponds to a B+ tree. While a disk sector is 512 B and a filesystem block is 4 KB, InnoDB stores data in 16 KB pages.

B+ Tree Index

Unlike MyISAM, InnoDB uses a clustered index where leaf nodes store the row data. The primary‑key index leaf contains the primary key and all remaining columns; secondary index leaves store the index key and the primary‑key value as a pointer.

InnoDB primary‑key index leaf nodes contain the primary key and all other fields. Secondary index leaf nodes store the index key and primary‑key value, acting as a pointer to the row.

Non‑leaf (index) nodes store only the key and a pointer, enabling O(log n) search to quickly locate the data page.

If a row occupies 1 KB, each 16 KB page can hold 16 rows. Assuming a bigint key (8 B) and a fixed 6 B pointer, an index entry is 14 B, so a page can store 16 KB / 14 B ≈ 1170 index entries.

16 * 1024 B / 14 B = 1170.

Therefore, a 2‑level B+ tree can store 1170 * 16 = 18 720 rows; a 3‑level tree can store 1170 * 1170 * 16 ≈ 21 902 400 rows. For a table with 20 million rows, the B+ tree height is three layers (since 20 M < 21.9 M). This calculation assumes each row is 1 KB and each index entry is 14 B.

Summary

This classic interview question reveals InnoDB's storage structure, helping readers understand index organization and data lookup principles.