Master MySQL Indexes: From Fundamentals to B+ Tree Mechanics

Indexes are a crucial, ordered data structure that can dramatically affect the performance of SQL queries; understanding their theory is essential before attempting any optimization.

1. Essence of Indexes

An index is essentially 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 do not support range queries and are not supported by MySQL InnoDB.

Suitable for precise lookups only.

Range scans are impossible because hash values have no order.

2.2 Binary Tree

Binary trees have the following characteristics:

Time complexity O(n).

Each node has at most two children.

Left child < smaller > than parent, right child > parent.

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

When unbalanced, the tree can degenerate into a chain, increasing traversal cost.

2.4 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.5 B+‑Tree

MySQL primarily uses B+‑trees for indexes, which have several advantages:

All data records reside in leaf nodes, while internal nodes store only keys, reducing tree height.

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

Fewer levels than B‑trees, so queries are faster.

Search cost is uniform because every lookup reaches a leaf.

Leaves form a sorted linked list, improving cache locality.

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

3. Primary Key Directory

MySQL stores rows in fixed‑size data pages that are linked together. Each data page is sorted by the primary key (or an internal ROW_ID if no primary key exists). The smallest primary key of each page, together with the page number, forms the primary key directory.

4. Index Pages

When the number of data pages grows, the primary key directory becomes large. MySQL therefore introduces an additional layer called index pages, which store the page number and the smallest primary key for each data page. Index pages themselves are organized hierarchically.

5. Index Page Layers

If an index page still contains too many entries, it splits and creates a higher‑level index page, forming a multi‑level structure similar to a B+‑tree.

6. Clustered Index (Primary Key Index)

The primary key index is a clustered index: the leaf nodes of the B+‑tree are the actual data pages, so searching the tree directly yields the full row.

Clustered index is built on the primary key structure in MySQL.

7. Non‑Primary (Secondary) Indexes

Secondary indexes are also implemented as separate B+‑trees. Each secondary index stores the indexed columns plus the primary key, but not the other columns.

When a query selects only the indexed columns, the result can be returned directly from the secondary index without accessing the clustered index.

If the query requests additional columns, MySQL must perform a "back‑table" lookup: it uses the primary key from the secondary index to locate the full row in the clustered index. SELECT name FROM student WHERE name='wx' This query can be satisfied entirely from the secondary index (no back‑table). SELECT * FROM student WHERE name='wx' Because the secondary index does not contain the other columns, MySQL first finds the matching primary key, then reads the full row from the clustered index – the back‑table step.

For a composite index (e.g., name+age), MySQL orders entries by name, then age, and finally the primary key. The index stores only these fields plus the primary key.

8. Maintenance of Secondary Indexes

When inserting or updating rows, MySQL updates each relevant B+‑tree: first sorting by the first indexed column, then the next, and finally the primary key. Only the indexed columns and the primary key are stored in the secondary index pages.