Why MySQL Tables Stall After 20 Million Rows and How B‑Link Trees Fix It

During a recent interview a candidate claimed to store 50 million user‑action rows in MySQL by sharding the data into three tables each day, sparking the common belief that a single MySQL table should stay below 20 million rows for acceptable performance.

Hypothesis 1: Is the index depth the culprit?

MySQL uses 16 KB pages (≈15 KB usable). With an 8‑byte primary key and a 4‑byte page offset, each non‑leaf index entry occupies 12 bytes, allowing about 1 280 entries per index page. Assuming 1 KB per row, three B+Tree levels can hold roughly 24.5 million rows before the tree depth grows from three to four, so index depth does not increase until that point. Modern SSDs (IOPS > 10 k) and server memory (TB‑scale) further diminish any I/O impact from deeper trees.

Hypothesis 2: Does SMO (Structure‑Modification‑Operation) limit concurrency?

InnoDB stores data in an index‑organized table (IOT) using a B+Tree. SMO operations (splits, merges) modify multiple nodes and are not atomic, requiring lock coordination.

Method 1 – Optimistic lock

The root and intermediate nodes acquire shared (S) locks; if the leaf modification does not change the tree structure, an exclusive (X) lock on the leaf suffices.

Method 2 – Pessimistic lock

If a leaf change triggers SMO, InnoDB takes a global SX lock on the root and X locks on all nodes that may be modified, forcing other SMO operations to wait until the current one finishes.

Consequently, simple primary‑key lookups are fast, but heavy write workloads suffer severe bottlenecks because the root‑level SX lock serializes SMO operations.

Solution: B‑Link Tree

B‑Link Tree reduces lock granularity by adding a right‑sibling link pointer and a high‑key field to each internal node. During SMO, only the affected level is locked; once that level finishes, the lock is released before moving up, allowing concurrent writes.

GaussDB adopts this B‑Link Tree structure, eliminating the root‑level lock and dramatically improving write concurrency.

InnoDB IOTs trigger SMO more often

With a 16 KB page and ~1 KB rows, an IOT leaf holds only about 16 rows, leading to low fan‑out and frequent SMO events. Heap‑organized tables store row pointers instead of full rows, increasing leaf capacity and reducing SMO frequency.

Performance comparison

Two 8U 32G servers were set up: MySQL (B+Tree + IOT) versus GaussDB (B‑Link Tree + heap‑organized table). Both loaded a 10 GB base table with 10 million rows (1 KB each) and then inserted another 10 million rows concurrently.

Results show GaussDB’s TPS scales steadily with increasing concurrency, while MySQL’s TPS plateaus, confirming the SMO lock bottleneck.

In summary, MySQL’s inability to handle massive concurrent writes stems from its index‑level locking protocol and the use of index‑organized tables, making it best suited for simple primary‑key lookups. Databases like GaussDB that employ B‑Link Trees and heap‑organized tables perform better for large‑scale, write‑intensive workloads.