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

Background and Question

The author recounts a personal experience of creating a MySQL table that eventually stored 100 million rows, far exceeding the commonly cited recommendation of 2 million rows per table. An intern asks why the table wasn’t sharded, prompting a technical deep‑dive.

Theoretical Maximum Row Count Based on Primary Key

The maximum number of rows a table can hold is limited by the range of its primary‑key column. For an INT (32‑bit unsigned) the limit is 2^32‑1 ≈ 21 billion rows; for a BIGINT it is 2^64‑1, which is practically unreachable because disk space runs out first. Using a TINYINT (8‑bit unsigned) caps the table at 255 rows.

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

When the primary key is defined as TINYINT:

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

Inserting a row with id=256 fails with:

mysql> INSERT INTO `tmp` (`id`, `name`, `age`) VALUES (256, '', 60);
ERROR 1264 (22003): Out of range value for column 'id' at row 1

Thus a TINYINT primary key restricts the table to a maximum of 255 rows.

Other Factors Affecting Row Count

Beyond the primary‑key range, the total number of rows is influenced by disk space, the size of each row, and the structure of the InnoDB index pages.

Index Structure: B+‑Tree

InnoDB stores data in 16 KB pages. Each page contains a header, footer, a page directory, and the actual records. The index is a B+‑tree where leaf pages hold the full rows and non‑leaf pages store only the primary‑key and a pointer to the child page.

Each 16 KB page reserves about 128 B for header/footer and ~1 KB for the directory, leaving roughly 15 KB for entries. A non‑leaf entry consists of an 8‑byte BIGINT primary key and a 4‑byte page offset, i.e., 12 B. Therefore a non‑leaf page can point to about 15 KB / 12 B ≈ 1 280 child pages (fan‑out ≈ 1280).

Calculating Total Rows Supported by a B+‑Tree

The total number of rows a B+‑tree can hold is: (x ^ (z‑1)) * y x : fan‑out (≈ 1280)

y : number of rows a leaf page can store

z : number of tree levels

Assuming each row occupies 1 KB, a leaf page can store about 15 rows (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 “2 kw” rule of thumb.

Impact of Row Size on Capacity

If each row is only 250 B, a leaf page can hold about 60 rows (y = 60). With a three‑level B+‑tree the capacity becomes: (1280 ^ (3‑1)) * 60 ≈ 1 × 10⁸ rows, explaining why a table with 100 million rows can still be queried with at most three page reads.

Comparison with B‑Tree

Traditional B‑trees store rows in both leaf and non‑leaf nodes, reducing fan‑out. For the same 16 KB page size and 1 KB rows, a B‑tree can point to only about 15 child pages, leading to many more levels. To store ~2 kw rows a B‑tree would need ≥ 6 levels, requiring up to six disk I/Os per lookup, whereas a B+‑tree needs only three.

Conclusion

B+‑tree leaf pages store actual rows; non‑leaf pages store only primary‑key and child‑page pointers.

Typical B+‑trees have two to three levels; with a fan‑out of ~1280 they can comfortably hold > 2 kw rows while keeping lookup I/Os to 1‑3.

For the same data volume, B‑trees require more levels and thus more I/Os, making B+‑trees the preferred index structure in MySQL.

The 2 kw recommendation is a guideline; exceeding it may increase tree depth and affect query performance.

Absolute limits are also set by primary‑key range and available disk space.

References

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