How InnoDB Indexes Work: From Data Pages to B+ Trees

Search Without an Index

Before introducing indexes, we need to understand how records are found when no index exists. For simplicity we discuss only exact‑match conditions (WHERE column = value).

SELECT [column_list] FROM table_name WHERE column_name = xxx;

Search Within a Single Page

If the table contains few rows that fit into one page, there are two cases:

Using the primary key as the search condition The page directory allows a binary search to locate the slot, then the records in that slot are scanned to find the target row.

Using a non‑primary‑key column Because the page directory does not contain non‑primary‑key columns, the engine must traverse the single‑linked list of records sequentially, which is very inefficient.

Search Across Many Pages

When a table stores many rows across multiple pages, the search consists of two steps:

Locate the page that may contain the record.

Search within that page using the method described above.

Since we cannot quickly locate the correct page, we must walk the double‑linked list of pages from the first page, applying the same intra‑page search at each step. Scanning all pages is extremely slow for large tables.

Index

To avoid scanning all pages, we build a directory for pages—an index. Each directory entry contains the smallest primary‑key value in the page (key) and the page number (page_no). The directory entries themselves are stored in data pages, reusing the same page format as user records but with a different record_type value.

Creating a Sample Table

mysql> CREATE TABLE index_demo(
    c1 INT,
    c2 INT,
    c3 CHAR(1),
    PRIMARY KEY(c1)
) ROW_FORMAT=Compact;

The table has two INT columns and one CHAR(1) column, with c1 as the primary key.

Simplified Row Diagram

Only the following parts of a record are shown:

record_type : 0 = ordinary record, 1 = directory entry, 2 = minimum record, 3 = maximum record.

next_type : offset to the next record (illustrated with arrows).

Column values : c1 (orange), c2 (blue), c3 (red).

Other information : hidden columns and extra metadata (omitted for brevity).

A Simple Index Scheme

Assume each data page can hold at most three records. Inserting three rows into index_demo yields a single page (page 10) with records ordered by primary key:

INSERT INTO index_demo VALUES(1,4,'u'),(3,9,'d'),(5,3,'y');

When inserting a fourth row with primary key 4, the engine must allocate a new page (page 28) because page 10 is full, and then move the record with primary key 5 to the new page to maintain the rule “the primary‑key value of the next page must be greater than the maximum primary‑key value of the previous page.”

Directory Entries

Each directory entry stores:

key : the smallest primary‑key value in the page.

page_no : the page number.

These entries are stored in dedicated pages (e.g., page 30). The record_type of a directory entry is 1, while ordinary records have record_type 0.

Multi‑Level Directory (B+ Tree)

When many directory pages exist, a higher‑level directory page (e.g., page 33) stores pointers to lower‑level directory pages, forming a hierarchical structure identical to a B+‑tree. The leaf level (level 0) contains the actual user records; inner levels contain only directory entries.

Clustered Index

The B+‑tree described above is a clustered index: it orders pages and records by primary‑key value, and the leaf nodes store complete user records. In InnoDB the clustered index is created automatically for the primary key.

Secondary Index

A secondary index uses a non‑primary column (e.g., c2) as the sorting key. Its leaf nodes store only the indexed column and the primary key. To retrieve the full row, the engine must perform a “back‑lookup” (or “row lookup”) using the primary key in the clustered index.

Composite (Combined) Index

A composite index orders first by c2 and then by c3. The leaf nodes contain c2, c3, and the primary key. Only one B+‑tree is built for the composite index, unlike creating separate indexes on c2 and c3.

MyISAM Indexing

MyISAM stores data and indexes separately. The data file keeps rows in insertion order, and the primary‑key index is a B+‑tree whose leaf nodes store (primary_key, row_number). To fetch a row, MyISAM first uses the index to obtain the row number, then reads the data file—effectively a secondary index. All MyISAM indexes are secondary indexes.

Creating and Dropping Indexes in MySQL

InnoDB and MyISAM automatically create indexes for primary keys and UNIQUE columns. To add an index on other columns:

ALTER TABLE table_name ADD INDEX idx_name (column1, column2);

To drop an index: ALTER TABLE table_name DROP INDEX idx_name; Example of creating a table with a composite index on c2 and c3:

CREATE TABLE index_demo(
    c1 INT,
    c2 INT,
    c3 CHAR(1),
    PRIMARY KEY(c1),
    INDEX idx_c2_c3 (c2, c3)
);

And dropping that index:

ALTER TABLE index_demo DROP INDEX idx_c2_c3;

Summary

In InnoDB, searching within a single page is fast with the page directory when the primary key is used; otherwise a full scan of the record list is required.

Without any index, the engine must traverse the double‑linked list of pages and the single‑linked list of records, which is extremely slow.

InnoDB indexes are B+‑trees. The leaf level stores complete rows (clustered index) or (indexed_column, primary_key) pairs (secondary index). The inner levels store directory entries.

MyISAM stores data and indexes separately; all its indexes are secondary indexes that require a back‑lookup to fetch the full row.