Unlocking MySQL Indexes: How B+ Trees Boost Query Performance

MySQL Index Implementation

Previous article covered B+ tree principles. MySQL uses B+ trees for indexes in InnoDB and MyISAM engines.

InnoDB Indexes

Two types: primary (clustered) and secondary (non‑clustered) indexes.

Primary index: Each table has one primary key index stored as a B+ tree; leaf nodes contain the primary key value and the full row data.

If no primary key is defined, MySQL adds a hidden 4‑byte rowid and builds a clustered index on it.

Secondary index: A table can have multiple secondary indexes; leaf nodes store the indexed column values and the primary key of the row. Non‑leaf nodes store only the indexed column values.

Non‑clustered indexes are further classified as:

Single‑column index – an index on one column.

Composite (multi‑column) index – an index on multiple columns.

Unique index – indexed column values must be unique (one NULL allowed).

MyISAM Indexes

MyISAM also uses B+ trees but only non‑clustered indexes. The leaf nodes of the primary key and secondary key trees point to the actual table rows, so searching via a secondary key does not require accessing the primary key tree.

Data Retrieval Process

In InnoDB, querying by primary key requires a single index lookup. Querying by a secondary key (e.g., name) requires two steps: first locate the row id in the secondary index, then fetch the row from the primary index (a “back‑lookup”).

In MyISAM, the process involves finding the record address from the secondary index and then reading the row directly.

Performance test on a table with 5 million rows shows a full‑table scan for a name query takes 2.239 s and scans 4,952,492 rows, while adding an index on empname reduces the query time to 0.001 s and scans only 22 rows.

Index Management

Creating an index:

CREATE [UNIQUE] INDEX index_name ON t_name (c_name[length]);

Altering a table to add an index:

ALTER TABLE t_name ADD [UNIQUE] INDEX index_name ON (c_name[length]);

Dropping an index: DROP INDEX index_name ON t_name; Viewing indexes: SHOW INDEX FROM t_name; Example with an emp table (5 million rows) demonstrates creating an index on empname, observing the dramatic performance improvement, and then dropping the index.

Choosing Index Length

Shorter index prefixes allow more entries per disk page, improving I/O efficiency, but the prefix must provide sufficient selectivity. For fields like email, a 10‑character prefix is often enough; for empname, a 6‑character prefix balances size and discrimination.

A simple heuristic to evaluate prefix selectivity is:

SELECT COUNT(DISTINCT LEFT(c_name, prefix_len)) / COUNT(*) FROM t_name;

Higher ratios indicate better discrimination.

Summary

Indexes should be used on tables with low write frequency and high read frequency, on columns with high cardinality, with appropriate length (not necessarily the shortest), and preferably covering the most common queries.