Why B‑Tree vs B+Tree Indexes Matter in MySQL Performance

1. Comparison of MySQL Storage Engines

MySQL supports several storage engines. All engines except Archive provide B‑Tree indexes. Archive added index support in MySQL 5.1, but only for a single AUTO_INCREMENT column.

2. B‑Tree and B+Tree Concepts

B‑Tree (binary search tree) has at most two children per non‑leaf node, stores one key per node, and directs left/right pointers based on key comparison. In MySQL, B‑Tree indexes are the default for all engines except Archive.

Most DBMS implement the index as a B+Tree . In InnoDB the index is a B+Tree: leaf nodes contain the indexed keys and a pointer to the next leaf, enabling fast sequential scans.

B‑Tree characteristics : balanced height, binary search within each node, automatic level control.

B+Tree differences : all keys reside in leaf nodes (dense index); internal nodes store only guide keys (sparse index). Leaf nodes are linked, which makes ordered range queries efficient.

3. B+Tree Index Principles

A B+Tree stores several data items and pointers in each disk block. Non‑leaf blocks keep only guide keys (e.g., 17, 35); the actual row data lives in leaf blocks.

Search algorithm:

Load the root block into memory.

Perform a binary search on the guide keys to select the appropriate child pointer.

Repeat until the leaf block containing the target key is reached.

Example: locating the value 29 requires three I/O operations (root → intermediate → leaf), whereas a full table scan would need one I/O per row.

Key observations:

The tree height h ≈ log_{m+1}(N), where N is the number of rows and m is the number of items per disk block. Larger blocks (greater m) reduce height and I/O.

Leaf nodes store the actual row data; internal nodes store only index keys.

Composite indexes obey the left‑most‑match rule: the index can be used only for the leftmost columns in the defined order.

4. Principles for Building Effective Indexes

Left‑most prefix matching : MySQL scans the index from left to right until a range condition (>, <, BETWEEN, LIKE) stops the match.

Equality and IN predicates can be reordered : the optimizer rearranges equality conditions to fit the index.

Choose high‑cardinality columns : columns with a high distinct‑value ratio reduce the number of scanned rows.

Avoid functions on indexed columns : expressions such as FROM_UNIXTIME(create_time) prevent index usage. Rewrite as create_time = UNIX_TIMESTAMP('2014‑05‑29').

Prefer extending existing indexes over creating new ones when possible.

Understanding these concepts helps design indexes that dramatically reduce I/O and improve query performance in MySQL.