MySQL Index Interview Guide: From B+ Trees to Index Design

Module 1: B+‑Tree Structure

Indexes are stored on disk in InnoDB’s .ibd files; each table has one .ibd file that contains both data and indexes. The basic unit of a B+‑tree is a 16 KB page. InnoDB reads pages into the Buffer Pool, so a shallow tree reduces disk I/O.

Key characteristics

All data reside in leaf pages; internal pages store only keys and pointers. A 16 KB page can hold about 1 170 bigint‑key entries (8 bytes key + 6 bytes pointer).

Leaf pages are linked by a doubly‑linked list, enabling efficient range scans without revisiting upper levels.

Compared with a red‑black tree (≈27 levels for 100 M rows) or a B‑tree, a B+‑tree with three levels can store roughly 2 million rows (1170 × 1170 × 16) while requiring only three disk reads, which is why MySQL chooses B+‑trees.

B+‑tree balances minimal disk I/O and fast range queries, the fundamental reason MySQL uses it.

Module 2: Index Organization

Clustered index

InnoDB’s primary key is a clustered index; the leaf nodes contain the full row data. A table has exactly one clustered index, defaulting to the primary key. If no explicit primary key exists, InnoDB picks the first non‑null unique index or creates a hidden 6‑byte rowid.

Secondary index

Secondary (non‑clustered) indexes store only the indexed columns plus the primary key. Queries must first locate the primary key in the secondary leaf, then fetch the full row from the clustered index—a process called “row lookup” or “back‑lookup”.

Covering index

If all columns required by a query are present in the secondary index, MySQL can return results directly from the index (EXPLAIN Extra shows Using index), eliminating the back‑lookup.

Composite index ordering

A composite index (a,b,c) is ordered first by a, then b, then c. This ordering defines the “left‑most prefix” rule: the index can be used only if the query predicates start with the leftmost column(s).

Module 3: Index Query and Failure

Index Merge

When a WHERE clause contains multiple indexed columns, the optimizer may merge single‑column indexes. Types include Intersection (AND), Union (OR), and Sort‑Union. EXPLAIN type = index_merge and Extra shows Using intersect(...) or Using union(...).

Eight common index‑failure scenarios

LIKE with a leading wildcard ( '%abc') prevents index use; a trailing wildcard ( 'abc%') can use the index.

Applying functions to indexed columns (e.g., YEAR(col)) disables index usage; rewrite as a range on the raw column.

Implicit type conversion (e.g., comparing a VARCHAR index to a numeric literal) forces conversion on the indexed column, causing failure.

Violating the left‑most prefix (querying only b in an (a,b,c) index).

Range condition on the first column makes subsequent columns unusable.

OR conditions where one side lacks an index cause the optimizer to fall back to a full scan.

Negation operators (!=, NOT IN, <>) often lead to full scans because many rows match.

IS NOT NULL usually matches most rows, so the optimizer prefers a full scan.

For each case, the article shows concrete SQL examples and the corresponding EXPLAIN output.

Module 4: Index Design

When to create an index

High‑frequency WHERE columns.

Columns used in ORDER BY / GROUP BY.

JOIN ON columns.

Columns that must be unique.

High‑selectivity columns (e.g., user_id, phone).

When not to create an index

Very small tables.

Columns updated extremely often.

Low‑selectivity columns (e.g., gender).

Redundant indexes (already covered by a composite index).

Very long VARCHAR columns without a prefix.

Cost of indexes

Additional disk space for each B+‑tree.

Write overhead: INSERT/UPDATE/DELETE must maintain every related index.

Optimizer cost: more indexes increase planning time and may cause mis‑selection.

Auto‑increment primary key

Sequential inserts avoid page splits, keep secondary indexes small, and improve Buffer Pool locality.

Prefix indexes

Index only the first N characters of a long VARCHAR to reduce size, but they cannot be used for ORDER BY or as covering indexes.

NULL handling

NULLable indexed columns complicate optimizer logic and often prevent index usage; prefer NOT NULL with sensible defaults.

Adding indexes to large tables

In MySQL 8.0, Instant DDL speeds metadata changes but index creation still rebuilds the structure. Tools such as pt-online-schema-change or gh‑ost allow online index addition without blocking writes.

Unique indexes

Enforce uniqueness and provide faster lookups (optimizer knows at most one row). Insertion of duplicate values raises a “Duplicate entry” error.

Conclusion

Understanding the B+‑tree internals, InnoDB’s clustered and secondary index layout, and the eight typical failure patterns equips candidates to answer most MySQL index interview questions and to design efficient indexes in practice.