How Many Rows Can a Single InnoDB B+ Tree Store? A Deep Dive

Introduction

The core question is how many rows a single InnoDB B+‑tree can hold. A quick answer is about 20 million rows, and the article walks through the reasoning by examining InnoDB’s storage structures and index organization.

Storage Units in MySQL

Data storage starts with the smallest unit: the disk sector (512 bytes). Filesystems allocate blocks (typically 4 KB). InnoDB introduces its own unit, the page , which is 16 KB by default.

All InnoDB data files (the *.ibd files) are multiples of 16 KB.

Page Size and Row Capacity

Assuming a row occupies roughly 1 KB, a single 16 KB page can store about 16 rows.

In a B+‑tree, leaf pages store the actual rows, while internal pages store key‑value pairs plus pointers.

B+‑Tree Organization

Data records are sorted by primary key and placed in leaf pages. Internal pages contain sorted keys and 6‑byte pointers (the InnoDB pointer size) plus the 8‑byte primary‑key value, totaling 14 bytes per entry.

Thus an internal page can hold 16384 / 14 ≈ 1170 pointers.

Calculating Row Capacity

For a B+‑tree of height 2 (root + leaf level):

Number of leaf pages reachable = 1170 (pointers from the root).

Rows per leaf page = 16.

Total rows ≈ 1170 × 16 = 18 720.

For height 3 (root → internal → leaf):

Rows ≈ 1170 × 1170 × 16 = 21 902 400, easily supporting tens of millions of rows.

Determining B+‑Tree Height from Page Metadata

In InnoDB’s tablespace, the root page of the primary‑key index is always page number 3. At offset 64 within that page, the page level is stored. The tree height equals page level + 1.

Example query to locate index metadata:

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 on a sample database shows that the customer and lineitem tables have root page number 3 and page levels of 2, giving a tree height of 3. The region table has page level 0, so its tree height is 1.

Practical Verification with Hexdump

By calculating the byte offset ( 16384 × 3 + 64 = 49216) and using hexdump on the tablespace file, the stored page level can be read directly, confirming the height.

Interview Insight: Why B+‑Tree?

Unlike B‑trees, B+‑trees store only keys in internal nodes, allowing many more pointers per node (higher fan‑out) and thus shallower trees. Fewer levels mean fewer I/O operations per lookup, which is why MySQL’s primary‑key indexes use B+‑trees.

Conclusion

By understanding page size, row size, and node capacity, we see that a typical InnoDB B+‑tree can comfortably store tens of millions of rows with a height of 1–3, resulting in only 1–3 I/O operations for primary‑key lookups. The analysis also highlights the practical steps to inspect index height directly from the tablespace.