Why a MySQL Table Can Hold 100 Million Rows Without Slowing Down

1. How Many Rows Can a Single MySQL Table Actually Hold?

Many developers hear that a single MySQL table should not exceed about 2 million rows, otherwise performance degrades sharply. The author disproves this by creating a user table with a tinyint primary key and inserting 255 rows, then shows that the limit is actually dictated by the data type of the primary key.

CREATE TABLE `user` (
  `id` int(10) unsigned NOT NULL AUTO_INCREMENT COMMENT '主键',
  `name` varchar(100) NOT NULL DEFAULT '' COMMENT '名字',
  `age` int(11) NOT NULL DEFAULT '0' COMMENT '年龄',
  PRIMARY KEY (`id`),
  KEY `idx_age` (`age`)
) ENGINE=InnoDB AUTO_INCREMENT=100037 DEFAULT CHARSET=utf8;

If the primary key is an int (32‑bit), the table can theoretically hold up to 2^32‑1 ≈ 2.1 billion rows. Using bigint raises the ceiling to 2^64‑1, but disk capacity becomes the bottleneck long before that.

CREATE TABLE `user` (
  `id` tinyint(2) unsigned NOT NULL AUTO_INCREMENT COMMENT '主键',
  `name` varchar(100) NOT NULL DEFAULT '' COMMENT '名字',
  `age` int(11) NOT NULL DEFAULT '0' COMMENT '年龄',
  PRIMARY KEY (`id`),
  KEY `idx_age` (`age`)
) ENGINE=InnoDB AUTO_INCREMENT=0 DEFAULT CHARSET=utf8;

With a tinyint primary key the table is limited to 255 rows; inserting id=256 triggers ERROR 1264 (22003): Out of range value for column 'id'.

2. Index Structure: The B+‑Tree

InnoDB stores data in 16 KB pages inside an .ibd file (the table’s tablespace). Each page contains a header, a footer, a page directory, and the actual records. Records are split across many pages; each page is identified by a page number (offset) and linked via previous/next pointers.

The page header also stores a checksum to protect against partial writes.

To speed up look‑ups, InnoDB builds a B+‑tree index on the primary key. The leaf pages hold the full records, while internal (non‑leaf) pages store only the primary‑key value and a pointer to the child page. This structure enables binary search, reducing lookup complexity from O(n) to O(log n).

Typical B+‑tree layout (two‑level example):

When the tree grows to three levels, the same principle applies, but an extra level of internal pages is added.

3. Calculating the Maximum Number of Records

Assume each page can store x pointers to child pages (fan‑out) and each leaf page can store y records. For a B+‑tree of height z, the total record capacity is: (x ^ (z‑1)) * y In InnoDB, a 16 KB page leaves about 15 KB for data after accounting for headers and footers. With a 12‑byte index entry (8‑byte bigint primary key + 4‑byte page offset), a page can point to roughly 1 280 child pages ( x≈1280). If a leaf record occupies 1 KB, a leaf page holds about 15 records ( y≈15).

For a two‑level tree ( z=2): (1280 ^ (2‑1)) * 15 ≈ 2 × 10⁴ rows.

For a three‑level tree ( z=3): (1280 ^ (3‑1)) * 15 ≈ 2.5 × 10⁴ rows, which matches the commonly quoted “2 w” (≈20 k) recommendation.

If each record is only 250 bytes, a leaf page can hold about 60 records, and a three‑level tree can store roughly 1 × 10⁸ rows, explaining why a table with 100 million rows can still query quickly.

4. B‑Tree vs. B+‑Tree

MySQL uses B+‑trees for indexes. A classic B‑tree stores data in both leaf and internal nodes, which reduces the fan‑out because internal nodes also contain full rows. Assuming the same 16 KB page size, a B‑tree’s internal node can hold about 15 rows, leading to a much smaller fan‑out and deeper trees.

The total capacity of a B‑tree follows the geometric series 15 + 15² + 15³ + … + 15^z. To store ~20 k rows, a B‑tree would need at least six levels, resulting in up to six disk I/Os per lookup, whereas a B+‑tree needs only 1‑3 I/Os.

Thus, B+‑trees are more efficient for MySQL indexes.

5. Summary

The theoretical row limit of a MySQL table is governed by primary‑key size, page size, and the B+‑tree index structure, not by an arbitrary “2 w” rule. A three‑level B+‑tree can comfortably hold tens of millions of rows with only a few disk I/Os per query. B+‑trees outperform B‑trees in both storage efficiency and lookup speed, which is why they are the default index type in InnoDB.

References

《MYSQL内核：INNODB存储引擎 卷1》