How Many Rows Can an InnoDB B+ Tree Store? A Deep Dive into Page Size and Tree Height

InnoDB stores data in pages of 16KB, which are the smallest storage unit for the engine. A disk sector is 512 bytes, a filesystem block is typically 4KB, and InnoDB pages are fixed at 16KB. The article first explains these storage hierarchies with illustrative diagrams.

Each page can hold multiple rows; assuming a row size of 1KB, a page can store about 16 rows. Non‑leaf pages store key‑pointer pairs. With a primary key of BIGINT (8 bytes) and an InnoDB pointer of 6 bytes, each entry occupies 14 bytes, allowing roughly 1,170 entries per page.

Using these numbers, a B+ tree of height 2 (root + leaf) can store 1,170 × 16 ≈ 18,720 rows. A height 3 tree stores 1,170 × 1,170 × 16 ≈ 21,902,400 rows, which is why InnoDB trees of 1–3 levels can comfortably handle tens of millions of rows with only 1–3 I/O operations per lookup.

The root page of a primary‑key index is always page number 3 in the tablespace file. The page level (height‑1) is stored at offset 64 within that page. By reading the tablespace file at offset 16384 × 3 + 64 (49,216 bytes) with hexdump, you can obtain the page level and thus the tree height.

Examples using the TPC‑H benchmark tables show:

lineitem: ~6 million rows, tree height 3

customer: 150 k rows, tree height 3

region: 5 rows, tree height 1

Even with large differences in row count, the tree height remains low, keeping lookup I/O minimal.

Finally, the article revisits a common interview question: why MySQL uses B+ trees instead of B trees? Because B trees store data in both leaf and internal nodes, reducing the fan‑out and increasing tree height, which leads to more I/O. B+ trees keep data only in leaves, maximizing fan‑out and minimizing depth.

In summary, InnoDB’s B+ tree can store roughly 20 million rows with a three‑level tree, and the tree height can be derived directly from the tablespace metadata.