How Many Rows Can an InnoDB B+ Tree Store?

1. How many rows can an InnoDB B+ tree store?

InnoDB B+ trees can store roughly 20 million rows; this figure is derived from the engine’s storage structures and page organization.

2. Understanding the smallest storage units

Disk sectors are 512 bytes, file‑system blocks are typically 4 KB, and InnoDB pages are 16 KB.

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

In MySQL the default InnoDB page size is 16 KB, configurable via parameters.

If a row occupies 1 KB, a single page can hold 16 rows.

3. How B+ trees organize data

Rows are sorted by primary key and stored in leaf pages; non‑leaf pages store key‑value pairs and pointers to child pages, forming an index‑organized table.

Example query:

select * from user where id=5 ;

Result row:

| 5 | zhao2 | 27 |

4. Calculating the number of rows per tree

Assuming a tree height of 2 (root + leaf), the total records equal root‑node pointer count × rows per leaf page .

With a 1 KB row, a leaf page holds 16 rows.

Each non‑leaf entry stores an 8‑byte bigint primary key and a 6‑byte pointer (14 bytes total). A 16 KB page can therefore hold 16384 / 14 ≈ 1170 pointers.

Thus a height‑2 tree can store 1170 × 16 = 18 720 rows.

A height‑3 tree can store 1170 × 1170 × 16 ≈ 21 902 400 rows.

In practice InnoDB B+ trees are usually 1–3 levels high, supporting tens of millions of rows with only 1–3 I/O operations per lookup.

5. Determining the B+ tree height

The root page of the primary‑key index is always page number 3. At offset 64 within this page, the two‑byte "page level" value is stored; tree height = page level + 1.

Using hexdump on the tablespace file confirms page levels for various tables (e.g., lineitem: level 2 → height 3, region: level 0 → height 1).

6. Summary

InnoDB pages are the minimal storage unit; leaf pages store rows, non‑leaf pages store keys and pointers. A height‑2 B+ tree can hold about 18 k rows, a height‑3 tree about 21 million rows, which explains why most tables achieve high query performance with only a few I/O operations.

7. Interview question recap

MySQL uses B+ trees instead of B trees because B+ trees keep data only in leaf nodes, allowing a higher fan‑out and shallower trees, which reduces I/O and improves query speed.