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

A Question?

How many rows can a single InnoDB B+ tree hold? The short answer is about 20 million rows. To understand this we first review InnoDB’s index data structure and storage organization.

Computers store data in minimum units. The smallest disk unit is a sector (512 bytes), a filesystem block is typically 4 KB, and InnoDB’s smallest unit is a page of 16 KB.

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

In MySQL the default InnoDB page size is 16 KB, but it can be changed:

mysql> show variables like 'innodb_page_size';
+------------------+-------+
| Variable_name    | Value |
+------------------+-------+
| innodb_page_size | 16384 |
+------------------+-------+
1 row in set (0.00 sec)

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

Data is organized with a B+ tree: leaf nodes store rows, non‑leaf nodes store key‑value pairs and pointers.

Rows are sorted by primary key and placed in different pages. Non‑leaf pages contain N key‑pointer pairs. This structure is called an index‑organized table.

To find a row, e.g. SELECT * FROM user WHERE id=5;, the engine starts at the root page (page number 3), performs a binary search to locate the leaf page, then reads the data page.

5

zhao2

27

Key points:

The smallest storage unit in InnoDB is a page, which can hold data or key‑pointer pairs. Leaf nodes store data, non‑leaf nodes store keys and pointers.

Index‑organized tables use binary search on non‑leaf nodes to locate the correct data page.

Assuming a B+ tree of height 2 (one root and leaf nodes), the total record count equals the number of pointers in the root multiplied by the number of rows per leaf.

With a 1 KB row size, a leaf page holds 16 rows. A non‑leaf page can store (16 KB / 14 bytes) ≈ 1170 pointers (8‑byte bigint key + 6‑byte pointer). Therefore a height‑2 tree can store 1170 × 16 ≈ 18 720 rows.

A height‑3 tree stores 1170 × 1170 × 16 ≈ 21 902 400 rows, showing that a B+ tree of height 1‑3 can accommodate tens of millions of rows, and each lookup requires only 1‑3 I/O operations.

The root page is always page number 3; the page level stored at offset 64 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 the query on a sample database shows that the primary‑key index root page number is 3, while secondary indexes start at page 4.

Hexdump of the page level at offset 49152 + 64 confirms the heights: linetemp table level 2 (height 3), region table level 0 (height 1), customer table level 2 (height 3).

Summary

The lineitem table with ~6 million rows has a B+ tree height of 3; the customer table with ~150 k rows also has height 3, meaning both require only three I/O operations for primary‑key lookups. A table with ten million rows would still have height 3, while a table with only five rows (region) has height 1.

Interview Question

Why does MySQL use B+ trees for indexes instead of B trees? Because B trees store data in both leaf and non‑leaf nodes, reducing the fan‑out and increasing tree height, which leads to more I/O operations.

Conclusion

This article started with a question, explained the principles of InnoDB index‑organized tables, demonstrated how queries work, and answered the interview question with practical evidence. It omits some details such as page fill factor and auxiliary fields.

References

Jiang Chengyao, MySQL Technical Internals: InnoDB Storage Engine

Jiang Chengyao, InnoDB index height guide