Comparison of B-trees and hash indexes (code example)

The content of this article is about the comparison between B-tree and hash index (code example). It has certain reference value. Friends in need can refer to it. I hope it will be useful to you. Helps.

Foreword: Understanding B-trees and hash data structures helps predict the execution of queries on these storage engines that use different index data structures, especially for the MEMORY storage engine, which allows you to Choose B-tree or hash as the storage engine for the index.

1. B-tree Index Features

B-tree index can be used in the comparison of columns using expressions =, >, >=, <, <=, or BETWEEN keyword. Indexes can also be used for comparisons if LIKE or to LIKE is used and is a constant string that does not begin with a wildcard character.

1. For example, the following SELECT statement will 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 'Patrick' <= key_col < 'Patricl', in the second statement' Pat' <= key_col < 'Pau'

2. The following SELECT statement does not use an index:

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 starts with a wildcard character. In the second statement, the LIKE value is not a constant.

If a string query like '%string%' and longer than three characters is used, MySQL will use the Turbo Boyer-Moore algorithm to initialize the model, and using this model to match will be faster.

Any index that does not span all AND levels in the WHERE clause is not used to optimize the query. In other words, in order to be able to use the index, the index's prefix must be used in each AND group.

3. The following WHERE clauses use indexes:

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;

4. These WHERE clauses do not use indexes:

    /* 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 indexes, even if there is an index. . One reason this can happen is that the optimizer estimates that using the index will require MySQL to access a very large proportion of the rows in the table. (In this case, the table scan may be much faster because it requires fewer searches.) However, if a query like LIMIT is only used to retrieve certain rows, then MySQL will use the index anyway, Because it's faster to find how many rows are returned in the results.

2. Hash Index Features

Hash indexes are somewhat different from the features just discussed:

They are only used when using = or < =>(This symbol is explained at the end of the article) operator for equality comparison (but very fast). They are not used with comparison operators, such as

The optimizer cannot use hash indexes to speed up ORDER BY operations. (Such an index cannot be used to search for the next entry in sequence.)

MySQL cannot determine approximately how many rows there are between two values ​​(used by the range optimizer to decide which index to use). If you change a MyISAM or InnoDB table to a hash-indexed MEMORY table, some queries may be affected.

Only the entire key is available for search rows. (With a B-tree index, any leftmost prefix of the key can be used to find the row.)

Appendix

Explanation of the difference between = and <=>:

Same points: Like the regular = operator, two values ​​are compared, and the result is 0 (not equal) or 1 (equal). In other words: 'A'<=>'B' gets 0 And 'a'<=>'a' gets 1, both are comparisons of values.
Difference: The value of NULL has no meaning. Therefore, the = operator cannot treat NULL as a valid result. So: please use <=>,'a' <=> NULL gives 0 NULL<=> NULL gives 1. Contrary to the = operator, the rule for the = operator is 'a'=NULL, and the result is NULL. Even NULL = NULL, the result is NULL. By the way, almost all operators and functions on MySQL work this way, because comparison with NULL is basically meaningless.

Use When the two operands may contain NULL, you need a consistent statement, then you can use <=>.

This article is all here It’s over. For more other exciting content, you can pay attention to the MySQL Video Tutorial column on the PHP Chinese website!

The above is the detailed content of Comparison of B-trees and hash indexes (code example). For more information, please follow other related articles on the PHP Chinese website!