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

How many rows can an InnoDB B+ tree store?

InnoDB’s B+ tree can hold about 20 million rows. The calculation starts from the storage units used by the engine: a disk sector is 512 bytes, a filesystem block is 4 KB, and InnoDB’s minimal unit – a page – is 16 KB.

All InnoDB data files (the *.ibd files) are multiples of 16 KB. The default page size is 16 KB, but it can be changed with the innodb_page_size variable:

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

If a row occupies roughly 1 KB, a single page can store 16 rows (16 KB / 1 KB). To locate a row, InnoDB organizes the data with a B+ tree: leaf pages store the rows, while non‑leaf pages store key‑value pairs and pointers to child pages.

For example, the query SELECT * FROM user WHERE id = 5; uses the primary‑key B+ tree. Starting from the root page (page number 3), a binary search on the non‑leaf pages finds the pointer to the leaf page that contains the desired row.

In a B+ tree of height 2 (root + leaf), the total number of records equals the number of pointers in the root multiplied by the number of rows per leaf page. Assuming a 1 KB row size, each leaf page holds 16 rows.

Each non‑leaf entry consists of an 8‑byte BIGINT primary‑key and a 6‑byte pointer, totaling 14 bytes. A 16 KB page can therefore store 16384 / 14 ≈ 1170 entries, i.e., 1170 pointers.

Thus a height‑2 B+ tree can store 1170 × 16 ≈ 18 720 rows. A height‑3 tree stores 1170 × 1170 × 16 ≈ 21 902 400 rows, which explains why InnoDB B+ trees with heights of 1‑3 can comfortably handle tens of millions of rows with only 1‑3 I/O operations per lookup.

How to determine the B+‑tree height?

In InnoDB the root page of the primary‑key index always has page number 3 . At offset 64 within that page the page level is stored; the tree height equals page level + 1. You can verify this with the metadata tables:

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 shows that the customer and lineitem tables have root page number 3, while secondary indexes use page number 4.

By examining the file offset 16384 × 3 + 64 = 49216 with a hex‑dump tool, you can read the two‑byte page level value. For example, the lineitem table has page level 2 (height 3), the region table has page level 0 (height 1), and the customer table also has page level 2 (height 3).

Despite the lineitem table containing over 6 million rows and the customer table only 150 k rows, both have a B+‑tree height of 3, meaning they require the same number of I/O operations for a primary‑key lookup.

Interview question: Why does MySQL use B+ trees for indexes?

The simple answer is that B‑trees store data in both leaf and non‑leaf nodes, reducing the number of pointers per non‑leaf node (lower fan‑out) and forcing the tree to be taller, which increases I/O. B+ trees keep all data in leaf nodes, maximizing fan‑out and keeping the tree shallow.

Conclusion

The article walks through the fundamentals of InnoDB’s index‑organized tables, shows how to calculate the maximum number of rows a B+ tree can hold, explains how to read the tree height from the page metadata, and clarifies why B+ trees provide efficient primary‑key lookups in MySQL.