Understanding the B-tree and hash data structures can help predict how different queries perform on different
storage engines that use these data structures in their indexes, particularly for the
storage engine that lets you choose B-tree or hash indexes.
A B-tree index can be used for column comparisons in expressions that use the
BETWEEN operators. The index also can be used for
LIKE comparisons if the argument to
LIKE is a constant string that does not start with a wildcard character. For
example, the following
SELECT statements use indexes:
SELECT * FROM
key_colLIKE 'Patrick%';SELECT * FROM
In the first statement, only rows with
'Patrick' <= are considered. In the second statement, only rows with
key_col < 'Pau'
statements do not use indexes:
SELECT * FROM
key_colLIKE '%Patrick%';SELECT * FROM
If you use
... LIKE '% and
string is longer than three characters, MySQL uses the Turbo Boyer-Moore algorithm to initialize the pattern for the string and then uses
this pattern to perform the search more quickly.
A search using
col_name IS NULL
col_name is indexed.
WHERE clauses use indexes:
index= 1 OR
index= 2 */... WHERE
index=1 OR A=10 AND
index=2 /* optimized like "
index_part1='hello'" */... WHERE
index_part3=5 /* Can use index on
index1but not on
WHERE clauses do not use indexes:
index_part1is not used */... WHERE
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
Sometimes MySQL does not use an index, even if one is available. One circumstance under which this occurs is
when the optimizer estimates that using the index would require MySQL to access a very large percentage of the
rows in the table. (In this case, a table scan is likely to be much faster because it requires fewer seeks.)
However, if such a query uses
LIMIT to retrieve only some of the rows, MySQL uses
an index anyway, because it can much more quickly find the few rows to return in the result.
Hash indexes have somewhat different characteristics from those just discussed:
They are used only for equality comparisons that use the
<=> operators (but are very fast). They are not used for comparison operators such as
< that find a range of values. Systems that rely on this type of
single-value lookup are known as "key-value stores"; to use MySQL for such applications, use hash
indexes wherever possible.
The optimizer cannot use a hash index to speed up
BY operations. (This type of index cannot be used to search for the next entry in order.)
MySQL cannot determine approximately how many rows there are between two values
(this is used by the range optimizer to decide which index to use). This may affect some queries if you
MyISAM table to a hash-indexed
Only whole keys can be used to search for a row. (With a B-tree index, any leftmost prefix of the key can be used to find rows.)