Understanding B-Tree and Hash Indexes in MySQL

Understanding B-Tree and Hash data structures helps predict query performance differences across MySQL storage engines. The MEMORY engine offers both B-Tree and Hash indexes for selection.

B-Tree Index Features

B-Tree indexes can be used with the operators =, >, >=, <, <=, BETWEEN, and with LIKE when the pattern does not start with a wildcard. Example queries that use the index:

SELECT * FROM tbl_name WHERE key_col LIKE 'Patrick%';
SELECT * FROM tbl_name WHERE key_col LIKE 'Pat%_ck%';

In the first statement only rows where 'Patrick' <= key_col < 'Patricl' are considered; in the second only rows where 'Pat' <= key_col < 'Pau' are considered.

Queries that do not use the index:

SELECT * FROM tbl_name WHERE key_col LIKE '%Patrick%';
SELECT * FROM tbl_name WHERE key_col LIKE other_col;

The first fails because the pattern starts with a wildcard, and the second fails because it does not use a constant.

If you use LIKE '%string%' and the string is longer than three characters, MySQL employs the Turbo Boyer‑Moore algorithm to speed up the search.

Expressions like col_name IS NULL can also use the index on col_name .

An index will be used only if the first column of the index appears in every AND group of the WHERE clause.

Examples of WHERE clauses that use an index:

... WHERE index_part1=1 AND index_part2=2 AND other_column=3

/* index = 1 OR index = 2 */
... WHERE index=1 OR A=10 AND index=2

/* optimized like "index_part1='hello'" */
... WHERE index_part1='hello' AND index_part3=5

/* Can use index on index1 but not on index2 or index3 */
... WHERE index1=1 AND index2=2 OR index1=3 AND index3=3;

Examples of WHERE clauses that do not use an index:

/* index_part1 is not used */
... WHERE index_part2=1 AND index_part3=2

/* Index is not used in both parts of the WHERE clause */
... WHERE index=1 OR A=10

/* No index spans all rows */
... WHERE index_part1=1 OR index_part2=10

Sometimes MySQL will ignore an available index when it estimates that using the index would read most rows, making a full table scan faster; however, if a LIMIT clause restricts the result set, MySQL tends to use the index because fewer rows are returned.

Hash Index Features

Hash indexes differ in several ways:

They can only be used for equality comparisons (=, <=>) and are much faster for those cases, but they cannot be used for range queries such as <, >, BETWEEN.

The optimizer cannot use a hash index to accelerate ORDER BY operations.

MySQL cannot estimate the number of rows between two values with a hash index, which may affect query planning, especially when converting MyISAM or InnoDB tables to MEMORY tables that rely on hash indexes.

Only full keys can be used to locate a row; unlike B‑Tree indexes, prefix keys are not usable.

Source: segmentfault.com (translated from MySQL Reference Manual ).