Understanding InnoDB B+ Tree Indexes: Structure and Real‑World Use Cases

Why Indexes Are Needed

InnoDB stores records in pages linked by a doubly‑linked list, which makes full‑table scans necessary when no index exists. Primary‑key lookups can use a binary search within a page only if the page number is known; non‑primary‑key queries require scanning every record. As table size grows to millions of rows, this approach becomes unacceptable, creating a need for an index that can jump directly to the target pages.

How an Index Evolves into a B+ Tree

The simplest idea is a separate directory page that stores the smallest primary‑key value and the page number for each data page, allowing a binary search to locate a record. This design fails because a directory can exceed one page and because frequent inserts/deletes would require costly re‑ordering of directory entries.

InnoDB solves this by reusing the same page structure used for user records to store directory entries as special records marked with record_type = 1. When a directory page fills, it splits and creates a higher‑level directory page, recursively forming an inverted tree— the B+ tree.

The simplified diagram (each page holds 2‑3 records) shows parent‑child pointers (solid arrows) and the doubly‑linked list within a level (dashed arrows).

Key conclusions : The leaf level (level 0) stores the actual user rows; upper levels store directory entries (internal nodes). The root page number never changes after creation, so the system only needs to remember the root to reach any data. Secondary‑index internal nodes store a triple index column + primary key + page number to distinguish rows with identical index values. Each page must contain at least two records, otherwise the tree degrades to a linked list.

Assuming a leaf node holds 100 rows and an internal node holds 1,000 entries, a three‑level B+ tree can address 100 million rows, and four levels can handle trillions, which explains why index lookups require only a few I/O operations.

Clustered Index vs. Secondary Index

In InnoDB each index is a separate B+ tree. The difference lies in what the leaf nodes store:

Clustered index : leaf nodes contain the full user record (all columns). InnoDB creates it automatically; there is at most one per table.

Secondary index : leaf nodes store index column + primary key. Multiple secondary indexes can be defined with CREATE INDEX. Because the leaf does not contain the full row, retrieving the complete record requires a second lookup on the clustered index—this extra step is called a “row lookup” or “back‑lookup”.

Note: In InnoDB, the index is the data; the clustered index’s leaf nodes are the actual table rows.

Side note – MyISAM : MyISAM stores data and index files separately. All indexes, including the primary key, keep only index column + row offset , so every query must perform a back‑lookup, effectively making every index a secondary index.

Indexes Are Not Free

Creating an index incurs two costs:

Space : each index adds a full B+ tree, consuming additional pages.

Time : inserts, updates, and deletes must maintain the tree’s order, potentially causing page splits and record moves, which degrades write performance.

Therefore, deciding whether to index a column requires evaluating whether the index can actually be used in the workload.

Scenarios Where a B+ Tree Index Is Useful

Consider a three‑column composite index

KEY idx_name_birthday_phone_number (name, birthday, phone_number)

. The index can be used in the following cases:

Full‑value match : All indexed columns appear in the WHERE clause, regardless of order.

Left‑most prefix : Queries reference the leftmost contiguous columns (e.g., name or name, birthday). Skipping a middle column prevents the later columns from being used.

Prefix match on strings : Conditions like name LIKE 'As%' can use the index, while leading‑wildcard patterns such as LIKE '%As%' cannot.

Range queries : Only the leftmost column involved in a range predicate can benefit from the index; subsequent columns are ignored.

Exact + range combination : Equality matches on leading columns followed by a range on the next column can still use the index.

Sorting : If the ORDER BY column order matches the index column order (and all directions are the same), the sort can be satisfied by the index, avoiding an extra filesort.

Grouping : When GROUP BY column order aligns with the index, the grouping can be performed without additional in‑memory work.

Cost of Back‑Lookup and Covering Indexes

Scanning a secondary index involves sequential I/O, but each back‑lookup to the clustered index is random I/O because primary‑key values are not contiguous. When many rows require back‑lookup, the optimizer may abandon the index in favor of a full table scan. Adding LIMIT can reduce the number of back‑lookups, making the index path more attractive.

To eliminate back‑lookups entirely, use a covering index: include all columns needed by the query in the index so that the query can be satisfied from the secondary index alone, avoiding the extra fetch from the clustered index.

Practical Tips for Choosing and Designing Indexes

Create indexes only on columns that appear in WHERE, join conditions, ORDER BY, or GROUP BY. Columns used solely in the SELECT list do not need indexes.

Prefer columns with high cardinality; low‑cardinality columns (e.g., gender, status) provide little filtering benefit and may increase back‑lookup rates.

Choose the smallest possible data type for indexed columns (e.g., INT instead of BIGINT) because the primary key is stored in every secondary index leaf.

For long string columns, index only a prefix (e.g., name(10)) to save space and speed comparisons, but be aware that prefix indexes cannot support ordering when the prefix is identical.

Indexes are ineffective if the indexed column is wrapped in a function or expression (e.g., my_col * 2 < 4).

Use auto‑incrementing primary keys; random inserts cause frequent page splits, whereas sequential inserts append to the end of the last page, improving stability.

Periodically check for redundant or duplicate indexes (e.g., a separate index on name when a composite index (name, birthday) already exists) and drop them to reduce maintenance overhead.

Understanding InnoDB indexes hinges on the core idea that a B+ tree grows from a simple page directory: the root page never changes, secondary indexes carry the primary key, back‑lookups occur when the full row is needed, and the left‑most prefix rule follows naturally from the tree’s structure. Once this reasoning is clear, deciding whether an index can be applied becomes a matter of logical deduction rather than memorization.