Mastering MySQL B-Tree Indexes: Structure, Query Types, and Limitations

MySQL uses B‑Tree (specifically B+Tree) as the default index structure because it provides ordered storage, balanced height, and low I/O cost for both point lookups and range scans.

Storage structure

A B‑Tree index stores the indexed column values in sorted order. All leaf pages are at the same depth, so the number of page reads to locate any key is bounded by the tree height. The index entries contain the indexed column values and a pointer to the corresponding row.

CREATE TABLE customer (
  id INT,
  last_name VARCHAR(30),
  first_name VARCHAR(30),
  birth_date DATE,
  gender CHAR(1),
  KEY idx1_customer (last_name, first_name, birth_date)
);

The index idx1_customer stores last_name , first_name and birth_date for every row.

Query patterns that can use a B‑Tree index

1. Full‑value match (all indexed columns)

EXPLAIN SELECT * FROM customer
WHERE first_name='George' AND last_name='Bush' AND birth_date='1960-08-08'\G

Index is used; the optimizer can locate the row with a single key lookup.

2. Left‑most prefix match

EXPLAIN SELECT * FROM customer WHERE last_name='Bush'\G

Index is used as a range scan on the first column.

3. Column‑prefix match (LIKE with a leading constant)

EXPLAIN SELECT * FROM customer WHERE last_name LIKE 'B%'\G

Index is used; the optimizer converts the pattern to a range on last_name .

4. Range match

EXPLAIN SELECT * FROM customer WHERE last_name BETWEEN 'Allen' AND 'Bush'\G

Index is used as a range scan.

5. Combined exact + range match

Exact match on the first column and range (or prefix) on the second column.

EXPLAIN SELECT * FROM customer WHERE last_name='Bush' AND first_name LIKE 'G%'\G

6. Covering index (index‑only scan)

EXPLAIN SELECT last_name FROM customer WHERE last_name='Bush'\G

All required columns are in the index, so the table rows are never accessed (index‑only scan).

Limitations of B‑Tree indexes

Left‑most rule: The optimizer can only use the index if the query predicates start with the left‑most indexed column. Example that fails:

EXPLAIN SELECT * FROM customer WHERE first_name='George'\G

No column skipping: If a column in the index is omitted, columns to its right cannot be used. Example:

EXPLAIN SELECT * FROM customer WHERE last_name='Bush' AND birth_date='1960-08-08'\G

Only last_name can be used.

Range stops further columns: Once a range condition (LIKE, <, >, BETWEEN) appears, any columns to its right are ignored. Example:

EXPLAIN SELECT * FROM customer WHERE last_name LIKE 'B%' AND first_name='George'\G

The index is used only for last_name.

Why B‑Tree is preferred over other structures

Hash indexes: Provide O(1) point lookups but lack ordering, making range scans and ORDER BY impossible; they also incur higher I/O for collisions.

Binary trees: Not self‑balancing; tree height depends on data distribution, leading to unpredictable I/O cost.

Red‑black trees: Self‑balancing but still taller than B‑Trees for large data sets, resulting in more page reads.

Why an auto‑increment primary key is recommended

In a B+Tree, pages are ordered by key value. An auto‑increment key grows monotonically, so new rows are always appended to the rightmost leaf page. This minimizes page splits and data movement, yielding better insert performance and reduced fragmentation.