Understanding MySQL Indexes: From Binary Search Trees to B+ Trees and Clustered vs. Non‑Clustered Indexes

Indexes are data structures that help quickly locate rows in large tables; in MySQL they are primarily implemented as B+‑trees. The article starts by introducing binary search trees, where each node stores a key and data, and demonstrates a lookup example for id=12.

It then shows how an unbalanced binary search tree can degenerate into a linked list, leading to inefficient searches, and motivates the need for balanced trees (AVL trees) that keep the height low.

Next, the article describes B‑trees, which store multiple keys per node to reduce tree height and disk I/O, and explains why storing more keys per node is advantageous for disk‑based storage.

The discussion moves to B+‑trees, the optimized form used by InnoDB, where only leaf nodes store the actual row data while internal nodes store only keys, allowing higher fan‑out, shallower trees, and efficient range queries.

It then differentiates clustered (primary key) indexes, where the table data is stored in the leaf nodes of the B+‑tree, from non‑clustered indexes, which store the primary key in leaf nodes and require an additional lookup (the “back‑table” operation) to retrieve full rows.

Practical lookup procedures are illustrated for both clustered and non‑clustered indexes, showing how the engine traverses root, intermediate, and leaf pages, loads pages from disk as needed, and stops when the search range is exhausted.

The article concludes that MySQL’s use of B+‑tree indexes makes data retrieval fast and that, in InnoDB, “data is index and index is data.” References to MySQL books and online articles are provided.