8.3.9 Comparison of B-Tree and Hash IndexesB-树索引和散列索引的比较

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-树和散列数据结构有助于预测不同查询在索引中使用这些数据结构的不同存储引擎上的执行情况,特别是对于允许您选择B-树或散列索引的MEMORY存储引擎。

B-Tree Index CharacteristicsB-树索引特征

A B-tree index can be used for column comparisons in expressions that use the =, >, >=, <, <=, or BETWEEN operators. B树索引可用于使用=>>=<<=BETWEEN运算符的表达式中的列比较。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. 如果LIKE的参数是不以通配符开头的常量字符串,则该索引也可用于LIKE比较。For example, the following SELECT statements use indexes:例如,以下SELECT语句使用索引:

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 with 'Patrick' <= key_col < 'Patricl' are considered. 在第一条语句中,只有带有'Patrick' <= key_col < 'Patricl'的行会被考虑。In the second statement, only rows with 'Pat' <= key_col < 'Pau' are considered.在第二条语句中,只有带有'Pat' <= key_col < 'Pau'的行会被考虑。

The following SELECT statements do not use indexes:以下SELECT语句不使用索引:

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

In the first statement, the LIKE value begins with a wildcard character. 在第一条语句中,LIKE值以通配符开头。In the second statement, the LIKE value is not a constant.在第二条语句中,LIKE值不是常量。

If you use ... LIKE '%string%' 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.如果使用... LIKE '%string%',并且string长于三个字符,则MySQL使用Turbo Boyer-Moore 算法来初始化用于字符串的模式,然后使用此模式来更快地执行搜索。

A search using col_name IS NULL employs indexes if col_name is indexed.如果col_name已编制索引,则使用col_name IS NULL的搜索将使用索引。

Any index that does not span all AND levels in the WHERE clause is not used to optimize the query. 任何不跨WHERE子句中的所有AND级别的索引都不会用于优化查询。In other words, to be able to use an index, a prefix of the index must be used in every AND group.换句话说,为了能够使用索引,必须在每个AND组中使用索引的前缀。

The following WHERE clauses use indexes:以下WHERE子句使用索引:

... 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;

These WHERE clauses do not use indexes:这些WHERE子句不使用索引:

    /* 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 does not use an index, even if one is available. 有时MySQL不使用索引,即使有可用的索引。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. 出现这种情况的一种情况是,优化器估计使用索引需要MySQL访问表中很大比例的行。(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.但是,如果这样的查询使用LIMIT只检索一些行,MySQL还是会使用索引,因为它可以更快地找到结果中要返回的几行。

Hash Index Characteristics散列索引特性

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. 它们不用于可以找到一系列值的比较运算符,如&lt;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.依赖这种类型的单值查找的系统称为“键值存储”;要将MySQL用于此类应用程序,请尽可能使用哈希索引。

  • The optimizer cannot use a hash index to speed up ORDER BY operations. 优化器不能使用散列索引来加速ORDER BY操作。(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). MySQL无法确定两个值之间大约有多少行(这由范围优化器用来决定使用哪个索引)。This may affect some queries if you change a MyISAM or InnoDB table to a hash-indexed MEMORY table.如果将MyISAMInnoDB表更改为哈希索引MEMORY表,这可能会影响某些查询。

  • 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.)(对于B树索引,可以使用键的任何最左侧前缀查找行。)