Rechercher dans le manuel MySQL
8.3.9 Comparison of B-Tree and Hash Indexes
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 MEMORY
storage engine
that lets you choose B-tree or hash indexes.
B-Tree Index Characteristics
A B-tree index can be used for column comparisons in
expressions that use the
=
,
>
,
>=
,
<
,
<=
,
or 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:
In the first statement, only rows with 'Patrick'
<=
are considered. In the second statement,
only rows with key_col
<
'Patricl''Pat' <=
are
considered.
key_col
< 'Pau'
The following SELECT
statements
do not use indexes:
In the first statement, the LIKE
value begins with a wildcard character. In the second
statement, the LIKE
value is not
a constant.
If you use ... LIKE
'%
and
string
%'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
employs indexes if
col_name
IS
NULLcol_name
is indexed.
Any index that does not span all
AND
levels in the
WHERE
clause is not used to optimize the
query. In other words, to be able to use an index, a prefix of
the index must be used in every
AND
group.
The following WHERE
clauses use indexes:
- /* index = 1 OR index = 2 */
- /* optimized like "index_part1='hello'" */
- /* Can use index on index1 but not on index2 or index3 */
These WHERE
clauses do
not use indexes:
- /* index_part1 is not used */
- /* Index is not used in both parts of the WHERE clause */
- /* No index spans all rows */
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
=
or<=>
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
ORDER 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 change a
MyISAM
orInnoDB
table to a hash-indexedMEMORY
table.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.)
Document created the 26/06/2006, last modified the 26/10/2018
Source of the printed document:https://www.gaudry.be/en/mysql-rf-index-btree-hash.html
The infobrol is a personal site whose content is my sole responsibility. The text is available under CreativeCommons license (BY-NC-SA). More info on the terms of use and the author.
References
These references and links indicate documents consulted during the writing of this page, or which may provide additional information, but the authors of these sources can not be held responsible for the content of this page.
The author This site is solely responsible for the way in which the various concepts, and the freedoms that are taken with the reference works, are presented here. Remember that you must cross multiple source information to reduce the risk of errors.