Why InnoDB Needs a Primary Key and How B‑Tree Indexes Work

1. B‑Tree Basics

B‑Tree (multi‑way search tree) is a balanced data structure that reduces the number of disk accesses needed to locate a record, making it ideal for database indexes. Most modern databases, including MySQL, use a variant called B+Tree, which stores all keys in leaf nodes and links them together.

Properties of an M‑order B‑Tree

Root node must have at least two children (if tree height > 1).

Non‑root, non‑leaf nodes have a number of children in the range [ceil(M/2), M].

All leaf nodes appear on the same level and do not store data records.

Each node contains n keys K1…Kn and n+1 child pointers P0…Pn, with keys ordered K1 < K2 < … < Kn.

Insertion Operations

When inserting a new element:

If the target leaf node has free space, insert the key in sorted order.

If the leaf node is full, split it: half of the keys move to a new node, and the middle key is promoted to the parent.

Example insertion sequence [3,14,7,1,8,5,11,17,13,6,23,12,20,26,4,16,18,24,25,19] is illustrated step‑by‑step with the following images:

... (subsequent steps continue with similar images for each insertion) ...

Deletion Operations

Deletion is more complex. The algorithm proceeds as follows:

Locate the key to delete. If it exists, remove it from its node.

If the node falls below the minimum occupancy ceil(M/2)-1, check sibling nodes.

If a sibling has extra keys, borrow one.

If siblings are also minimal, merge the under‑full node with a sibling and adjust the parent.

Repeated splits and merges are expensive operations for index files.

2. B+Tree Overview

MySQL indexes are implemented as B+Trees, a variation of B‑Trees designed for file‑system efficiency. Key differences:

Non‑leaf nodes store the same number of child pointers as keys.

Internal nodes keep the smallest key of each subtree.

All leaf nodes are linked together via a sibling pointer.

All actual keys appear in leaf nodes.

Typical B+Tree (max 4 keys per node) is shown below:

3. MySQL Index Implementation

Indexes are built in the storage engine layer. Different engines implement indexes differently; the article focuses on InnoDB.

InnoDB Primary (Clustered) Index

InnoDB stores table data in an .ibd file organized as a B+Tree. The leaf nodes contain the full row data, making the primary index a clustered index. Every InnoDB table must have a primary key; if none is defined, MySQL creates a hidden 6‑byte integer key.

Example of a students table with a primary key id and a secondary index on name:

The primary index B+Tree looks like:

Secondary Index

Secondary (non‑clustered) indexes store only the indexed column values in leaf nodes; each leaf entry points to the primary key of the corresponding row.

Thus, a query using a secondary index performs two lookups: first the secondary index to obtain the primary key, then the primary index to fetch the full row.

4. InnoDB Improvements to B+Tree Splitting

Standard B‑Tree splitting divides a full node 50/50, which leads to many splits and low page utilization. InnoDB optimizes for monotonic inserts (ascending or descending) by using a different strategy:

Insert the new element into the leaf if space permits.

If the leaf is full, check the parent node. If the parent has space, promote the middle key to the parent and create a new child node, avoiding a split of the leaf.

If the parent is also full, then perform a split at the parent level.

Illustration with a 5‑order B+Tree inserting 10, 11, 14, 15, 17:

Inserting 10 fits in the rightmost leaf. Inserting 11 would normally trigger a 50% split, but because the parent has free space, the middle key is promoted to the parent, creating a new child without splitting the leaf. Subsequent inserts follow the same optimized path, dramatically reducing split frequency and improving page utilization.

For random inserts, InnoDB still falls back to the 50% split strategy, but it maintains a “last insert position” and a flag indicating whether inserts are monotonic, allowing it to choose the appropriate method.

5. Why Use Monotonically Increasing Primary Keys?

Enables the optimized split strategy, reducing the number of costly node splits.

Improves index page space utilization, leading to better storage efficiency.

Ensures that new rows are always appended to the rightmost leaf, minimizing page reorganizations.

All secondary indexes reference the primary key, so a short, increasing primary key keeps secondary indexes compact.

Conclusion

Understanding B‑Tree and B+Tree structures clarifies why InnoDB mandates a primary key, why that key should be short and monotonically increasing, and how InnoDB’s optimized splitting algorithm reduces index maintenance overhead. Armed with this knowledge, developers can design and tune MySQL indexes more effectively.