Understanding MySQL Indexes: Principles, Types, and B+Tree Structure

Indexes are a core topic in MySQL interviews and everyday development because they directly affect the speed of a system. Before optimizing, it is essential to understand the underlying principles and theoretical foundations of indexes.

1. The Essence of an Index

An index is a sorted data structure, similar to a dictionary's table of contents, that allows fast lookup of rows.

2. Types of Indexes

2.1 Hash Index

Hash indexes provide O(1) lookup for exact matches but are not supported by InnoDB and cannot handle range queries.

Suitable for precise equality searches; unsuitable for range scans.

2.2 Binary Tree

Classic binary trees have the following characteristics:

Time complexity O(n).

Each node has at most two children.

Left child < smaller than > the node, right child > the node.

In extreme cases a binary tree can become a linked list, degrading performance.

2.3 B‑Tree (2‑3 Tree)

B‑trees store both key and data in each node; large data values can reduce the number of keys per node, increasing tree height and I/O.

2.4 B+‑Tree

All data records are stored in leaf nodes; internal nodes store only keys, reducing tree height.

Leaf nodes are linked in order, enabling fast range scans.

Search depth is consistent, giving stable query performance.

Leaf nodes form an ordered linked list, improving cache locality.

Full‑table scans can be performed by traversing only leaf nodes.

The B+‑tree is the primary index structure used by MySQL.

3. Primary‑Key Directory

MySQL stores rows in data pages, each page containing rows sorted by the primary key (or an internal ROW_ID). Data pages are linked by a double‑linked list, and a primary‑key directory maps the smallest key of each page to its page number.

4. Index Pages

When the primary‑key directory becomes large, MySQL introduces an additional level called an index page, which stores page numbers and the smallest primary key of each data page. Index pages themselves can be split into higher‑level index pages, forming a multi‑level hierarchy.

5. Layered Index Pages

If an index page grows too large, it is split, and a higher‑level index page is created. This process repeats, creating a tree‑like structure that ultimately resembles a B+‑tree.

6. Non‑Primary (Secondary) Indexes

Secondary indexes are also maintained as B+‑trees. Each secondary index stores the indexed columns plus the primary key, but not the other columns. Queries that request only the indexed columns can be satisfied directly from the secondary index (covering index). When additional columns are needed, MySQL must perform a “back‑table” lookup: it uses the primary key from the secondary index to locate the full row in the primary‑key (clustered) B+‑tree.

SELECT name FROM student WHERE name='wx';

This query can be answered using the secondary index without a back‑table lookup.

SELECT * FROM student WHERE name='wx';

Because the query requests columns not stored in the secondary index, MySQL first finds the matching primary key via the secondary index, then retrieves the full row from the clustered index (the back‑table operation).

7. Maintenance of Secondary Indexes

When maintaining a composite secondary index (e.g., name + address + age), MySQL orders entries by the first column, then the second, then the third, and finally by the primary key. Only the indexed columns and the primary key are stored in the secondary B+‑tree.

Recommended reading:

You Call This Thing a Token?

One‑Click High Availability and Distributed Coordination System Design

Understanding Microkernel Architecture