Why MySQL Indexes Matter: From Basics to B+Tree Mastery

1. What Is an Index

Official definition: a data structure that improves MySQL query efficiency by allowing fast row retrieval, similar to a book's table of contents.

1.1 How an Index Works

Without an index, a query like SELECT * FROM user WHERE id = 40 requires a full table scan. With an index, MySQL can perform a binary search on the index to locate the row quickly.

Index advantages:
1. Greatly speeds up data queries.
Index disadvantages:
1. Consumes database resources to maintain.
2. Takes disk space.
3. Slows down inserts/updates because the index must be updated.

Despite the drawbacks, the speed gain for large datasets outweighs the maintenance cost.

2. Types of Indexes

1. Primary key index – automatically created for the primary key; InnoDB uses a clustered index.
2. Ordinary index – built on regular columns, no restrictions, used to accelerate queries.
3. Composite index – built on multiple columns; none of the indexed columns may be NULL.
4. Full‑text index (MySQL 5.7 and earlier, provided by MyISAM) – indexes large text columns for keyword search.

3. B+Tree

Example SQL execution shows MySQL automatically orders rows using a B+Tree structure, which can be visualized in the following diagram:

The storage layout resembles a linked list where each page points to the next, enabling fast lookup via page directories.

When searching for id = 2, the page directory points to the first page, and the pointer P allows sequential access to the desired row with a single I/O operation.

Even with massive data volumes, the B+Tree’s leaf‑only data storage keeps tree depth shallow (typically ≤3 levels), reducing I/O compared to a B‑Tree where every node stores data.

Key Differences Between B+Tree and B‑Tree

1. B+Tree leaf nodes store only key values.
2. All leaf nodes have a pointer to the next leaf.
3. Data resides only in leaf nodes; B‑Tree stores data in internal nodes as well.
InnoDB page size is 16 KB; primary keys are usually INT (4 bytes) or BIGINT (8 bytes).

4. Clustered vs. Non‑Clustered Indexes

Clustered index stores row data together with the index; its leaf nodes contain the full rows. Non‑clustered (auxiliary) indexes store only the primary‑key values in leaf nodes, requiring a second lookup to fetch the row.

In practice, most user‑defined indexes are auxiliary (non‑clustered) indexes that point to the primary key, a pattern known as “back‑table lookup”.

Clustered indexes offer faster data access and efficient range queries but depend on insert order; therefore, auto‑incrementing primary keys are recommended to avoid page splits.