InnoDB Index Build Process and Fill Factor in MySQL 5.7+

Index Build Process

From MySQL 5.7 onward, InnoDB changed the way secondary indexes are built, adopting a bottom‑up method instead of the earlier top‑down approach.

This article demonstrates the process with an example and explains how to set a more appropriate value for innodb_fill_factor.

Phases of Index Construction on a Populated Table

Read phase – read from the clustered index and create secondary‑index entries.

Merge‑sort phase.

Insert phase – insert the sorted records into the secondary index.

Before version 5.6 MySQL built secondary indexes one row at a time (a “top‑down” method). The search for the insertion point started at the root of the B‑tree and proceeded down to the leaf page, incurring high overhead for locating the position and handling page splits.

Since 5.7, the insertion phase uses “sorted index build” (also called “bulk index load”). In this method the index is built “bottom‑up”: leaf pages are constructed first, then non‑leaf levels up to the root.

Example Scenarios for Sorted Index Build

ALTER TABLE t1 ADD INDEX (or CREATE INDEX)

ALTER TABLE t1 ADD FULLTEXT INDEX

ALTER TABLE t1 ADD COLUMN, ALGORITHM=INPLACE

OPTIMIZE TABLE t1

For the last two cases, ALTER creates an intermediate table, and the intermediate table’s indexes (primary and secondary) are built using the sorted‑index method.

Algorithm (Simplified)

Create a page at level 0 and a cursor for that page.

Insert rows into the page until it is full.

When the page fills, create a sibling page (do not insert into it yet).

Commit the current page (mini‑transaction) and release its latch.

Create a node pointer (minimum key of the child page, child page number) and insert it into the parent page at the next higher level.

If the parent page does not exist, MySQL creates it and a cursor for it.

Insert the node pointer into the newly created parent page.

Link the sibling pages at level 0 and move the cursor to the sibling.

Repeat the process for subsequent rows.

For simplicity the algorithm omits details about compressed pages and external BLOB handling.

Bottom‑Up Index Construction Example

Assume a maximum of three records per leaf and non‑leaf page.

<ol>
  <li><code>CREATE TABLE t1 (a INT PRIMARY KEY, b INT, c BLOB);</code></li>
  <li><code>INSERT INTO t1 VALUES (1, 11, 'hello111');</code></li>
  <li><code>INSERT INTO t1 VALUES (2, 22, 'hello222');</code></li>
  <li><code>INSERT INTO t1 VALUES (3, 33, 'hello333');</code></li>
  <li><code>INSERT INTO t1 VALUES (4, 44, 'hello444');</code></li>
  <li><code>INSERT INTO t1 VALUES (5, 55, 'hello555');</code></li>
  <li><code>INSERT INTO t1 VALUES (6, 66, 'hello666');</code></li>
  <li><code>INSERT INTO t1 VALUES (7, 77, 'hello777');</code></li>
  <li><code>INSERT INTO t1 VALUES (8, 88, 'hello888');</code></li>
  <li><code>INSERT INTO t1 VALUES (9, 99, 'hello999');</code></li>
  <li><code>INSERT INTO t1 VALUES (10, 1010, 'hello101010');</code></li>
  <li><code>ALTER TABLE t1 ADD INDEX k1(b);</code></li>
</ol>

InnoDB appends the primary‑key column to secondary index entries, so index k1 stores records as (b, a). After the sort phase the index contains:

(11,1), (22,2), (33,3), (44,4), (55,5), (66,6), (77,7), (88,8), (99,9), (1010,10)

Initial Insert Phase

Starting with record (11,1):

Create a leaf‑level page (level 0).

Create a cursor pointing to that page.

All subsequent inserts go to this page until it is full.

The cursor currently points to page 5; the next insert will use this page.

Inserts (22,2) and (33,3) fill the remaining slots in page 5.

When inserting (44,4) page 5 is full, so a sibling page 6 is created, a node pointer ((11,1),5) is inserted into a new parent page 7, and the cursor moves to page 6 where (44,4) is stored.

Subsequent records (55,5) and (66,6) are inserted into page 6, while (77,7) causes a node pointer ((44,4),8) to be added to parent page 7 and the record to be placed in sibling page 8.

Records (88,8) and (99,9) fit into page 8, and (1010,10) creates a new leaf page 9 and a node pointer ((77,7),8) is inserted into the parent page 7.

At the end a complete B‑tree index built from the bottom up is obtained.

Index Fill Factor

The global variable innodb_fill_factor controls how much space is left free in B‑tree pages during index creation. The default value is 100, meaning the whole page (except the header) is used. For clustered indexes the fill factor is implicitly 100, leaving 1/16 of the page (≈6.25 %) free for future DML.

A value of 80 tells MySQL to fill pages to 80 % and reserve 20 % for future updates. Setting the factor to 100 leaves no space for later inserts into secondary indexes, which can cause page splits and extra merges if DML occurs after the index is built. Values between 80 and 90 are generally recommended.

Very low values (below 50) waste disk space and increase the number of pages, which can degrade statistics sampling and lead the optimizer to choose sub‑optimal plans.

Advantages of Sorted Index Build

No page splits (except on compressed tables) and merges.

No repeated searches for insertion points.

Insertions are not redo‑logged (except for page allocation), reducing redo‑log pressure.

Disadvantages

Insert performance is reduced while ALTER is running (see Bug #82940, fixed in later releases).