How MySQL Uses B-Tree Indexes for Faster Queries

This article explains how MySQL utilizes B-Tree (specifically B+Tree) indexes to dramatically accelerate data retrieval operations. We will explore the structural design of these indexes, how they minimize disk I/O, the step-by-step traversal process during query execution, and why they are highly efficient for both point lookups and range scans.

Understanding the B-Tree Structure in MySQL

MySQL, particularly through its default InnoDB storage engine, implements a variation of the B-Tree called the B+Tree. In a standard B-Tree, keys and data can be stored in both internal and leaf nodes. In a B+Tree, all actual data rows or pointers to data are stored exclusively in the leaf nodes, while the internal nodes only store search keys and child page pointers.

This structure offers two primary advantages: * High Fan-Out: Because internal nodes do not store actual data, they can hold a massive number of keys. This allows the tree to remain short and wide, typically requiring only 3 to 4 levels even for millions of rows. * Sequential Leaf Links: Leaf nodes are linked together in a doubly-linked list. This enables highly efficient sequential traversal without needing to backtrack through parent nodes.

How Data Retrieval Works

When a query executes with a WHERE clause matching an indexed column, MySQL performs a search starting from the root node.

1. Root Node Evaluation: The database engine reads the root node and compares the search key against the keys in the node to determine which child pointer to follow.
2. Branch Navigation: It traverses down through the intermediate branch nodes, repeating the comparison process to narrow down the search space.
3. Leaf Node Retrieval: Once it reaches the leaf node, MySQL locates the exact key.

Because the tree is balanced, this traversal takes \(O(\log N)\) time, meaning a search that would otherwise require scanning millions of records (a full table scan) can be completed in just 3 or 4 page reads.

Clustered vs. Secondary Indexes

MySQL utilizes B-Tree indexes in two distinct ways:

• Clustered Indexes (Primary Key): The leaf nodes of a clustered index contain the actual physical row data. Every table in InnoDB has one clustered index. Finding a key here means immediate access to the entire row.
• Secondary Indexes: The leaf nodes of a secondary index contain the indexed column values and the corresponding primary key value. When searching via a secondary index, MySQL finds the primary key in the secondary B-Tree and then performs a second lookup in the clustered index B-Tree to retrieve the full row.

Efficiency in Range Queries and Sorting

Beyond point lookups, B-Tree indexes are exceptionally efficient for range queries (such as WHERE age BETWEEN 20 AND 30) and sorting (ORDER BY). Because the leaf nodes are physically ordered and linked sequentially, MySQL only needs to locate the first key in the range and then traverse the doubly-linked list horizontally until it hits the end of the range, bypassing the need to traverse the tree structure repeatedly.