How Many Rows Can a MySQL InnoDB B+ Tree Store?

Interview Question

The interview question asks: "How many rows can an InnoDB B+ tree store?" The short answer is about 20 million rows, and the article explains how this number is derived.

Storage Units in InnoDB

Data is stored on disk in sectors (512 bytes) and file‑system blocks (4 KB). InnoDB uses its own smallest storage unit called a page , which is 16 KB by default.

How Many Rows Fit in a Page

If a row is roughly 1 KB, a 16 KB page can hold about 16 rows.

How Many Pointers Fit in a Non‑Leaf Page

A primary‑key value (bigint) is 8 bytes and an InnoDB pointer is 6 bytes, totaling 14 bytes per entry. A page can therefore store 16384 / 14 ≈ 1170 pointers.

Rows per B+ Tree at Different Heights

For a tree of height 2 (root + leaf), the capacity is 1170 × 16 ≈ 18 720 rows.

For a tree of height 3, the capacity is 1170 × 1170 × 16 ≈ 21 902 400 rows.

Thus a B+ tree with height 1‑3 can easily accommodate tens of millions of rows, and each lookup requires only 1‑3 page reads (I/O operations).

Determining B+ Tree Height

The root page of a primary‑key index is always page number 3. The page level stored at offset 64 in this page indicates the tree height: height = page level + 1.

SELECT b.name, a.name, index_id, type, a.space, a.PAGE_NO
FROM information_schema.INNODB_SYS_INDEXES a,
     information_schema.INNODB_SYS_TABLES b
WHERE a.table_id = b.table_id AND a.space <> 0;

Running this query shows that the customer and lineitem tables have root page number 3, while secondary indexes start at page 4.

Using hexdump on the tablespace file at offset 49152 + 64 (i.e., 49216) reveals the page level values: region table level 0 (height 1), lineitem level 2 (height 3), customer level 2 (height 3).

Why MySQL Uses B+ Trees

In a B‑tree, both leaf and internal nodes store data, reducing the number of pointers per node and increasing tree height, which leads to more I/O. B+ trees store only keys and pointers in internal nodes, maximizing fan‑out and keeping lookup I/O low.

Conclusion

The article walks through the principles of InnoDB’s index‑organized tables, shows how to compute the row capacity of a B+ tree, demonstrates how to retrieve the tree height from the tablespace, and explains why B+ trees are preferred for MySQL indexing.