Mastering MySQL Indexes: B‑Tree, B+Tree, and Optimization Strategies

Abstract

This article uses MySQL as a case study to discuss various topics related to database indexes. MySQL supports multiple storage engines, each providing different index types such as B‑Tree, hash, and full‑text indexes. To avoid confusion, the focus is on B‑Tree indexes, which are the most commonly used in MySQL.

Data Structure and Algorithm Foundations

Nature of an Index

MySQL defines an index as a data structure that helps retrieve data efficiently. In essence, an index is a specialized data structure that enables faster search algorithms like binary search or tree‑based search, which operate on organized structures rather than raw tables.

Example: a binary search tree can map index keys to physical record addresses, allowing O(log₂n) lookup time.

B‑Tree and B+Tree

Most database and file systems use B‑Tree or its variant B+Tree for indexing. The article first describes B‑Tree from a data‑structure perspective, listing its properties (degree d, height h, node composition, ordering, etc.).

Typical B‑Tree search algorithm:

BTree_Search(node, key)
{
    if (node == null) return null;
    foreach (node.key)
    {
        if (node.key[i] == key) return node.data[i];
        if (node.key[i] > key) return BTree_Search(point[i]->node);
    }
    return BTree_Search(point[i+1]->node);
}

data = BTree_Search(root, my_key);

B‑Tree offers logarithmic search complexity and, with a large branching factor, usually requires only a few node accesses.

B+Tree differs by storing only keys in internal nodes and full records in leaf nodes, allowing a higher branching factor and better suitability for disk‑based indexes.

Why Use B‑Tree/B+Tree

Indexes reside on disk and must minimize I/O operations. B‑Tree/B+Tree nodes are sized to match a disk page, so each node can be loaded with a single I/O. High branching factor reduces tree height, further decreasing I/O.

MySQL Index Implementations

MyISAM

MyISAM uses B+Tree where leaf nodes store the physical address of the data record. Primary and secondary indexes share the same structure; the primary key must be unique, while secondary keys may contain duplicates.

InnoDB

InnoDB also uses B+Tree, but the table data itself is organized as a clustered index (primary key). Leaf nodes contain complete rows, making the primary key both the data storage and the index. Secondary indexes store the primary key value instead of a record address, requiring a two‑step lookup.

Index Usage Strategies and Optimization

Effective index use relies on the left‑most prefix rule for composite indexes. Various scenarios illustrate when an index can be fully used, partially used, or not used at all (e.g., missing the leftmost column, range queries, functions in predicates).

Index selectivity is crucial; low‑selectivity columns (e.g., titles with few distinct values) should not be indexed individually. Prefix indexes can improve selectivity while reducing index size, though they cannot support ORDER BY, GROUP BY, or covering indexes.

For InnoDB, using an auto‑increment surrogate primary key yields sequential inserts that keep pages compact and minimize page splits, whereas random primary keys cause frequent page reorganizations and fragmentation.

Conclusion

The article provides a theoretical foundation for MySQL indexing, explains why B‑Tree/B+Tree are preferred, compares MyISAM and InnoDB implementations, and offers practical guidelines for index design, selectivity assessment, prefix indexing, and primary‑key selection to achieve high‑performance query execution.