What is the difference between B-Tree index and Hash index in MySQL?

The difference between B-Tree index and Hash index in MySQL: 1. B-Tree index supports the leftmost prefix matching principle, but Hash index does not support it; 2. Both MyISAM and InnoDB support B- Tree index, while Hash index is only supported by Memory and NDB engine indexes.

Hash index

The particularity of the Hash index structure, its retrieval efficiency is very high, and the index retrieval can be done once Positioning, unlike the B-Tree index, which requires multiple IO accesses from the root node to the branch node, and finally to the page node, so the query efficiency of the Hash index is much higher than that of the B-Tree index.

Many people may have questions again. Since the efficiency of Hash index is much higher than that of B-Tree, why don't everyone use Hash index but also use B-Tree index? Everything has two sides, and the same goes for Hash indexes. Although Hash indexes are highly efficient, the Hash indexes themselves also bring many limitations and disadvantages due to their particularity, mainly as follows.

(1) Hash index can only satisfy "=","IN" and "<=>" queries, and range queries cannot be used.

Since the Hash index compares the Hash value after Hash operation, it can only be used for equal value filtering and cannot be used for range-based filtering, because the Hash value after processing by the corresponding Hash algorithm The size relationship is not guaranteed to be exactly the same as before the Hash operation.

(2) Hash index cannot be used to avoid data sorting operations.

Since the Hash index stores the Hash value after Hash calculation, and the size relationship of the Hash value is not necessarily exactly the same as the key value before the Hash operation, so the database cannot use the index data to avoid any Sorting operation;

(3) Hash index cannot be queried using part of the index key.

For the combined index, when the Hash index calculates the Hash value, the combined index keys are merged and then the Hash value is calculated together, instead of calculating the Hash value separately, so the previous one or several index keys of the combined index are used. When querying, the Hash index cannot be used.

(4) Hash index cannot avoid table scan at any time.

As we know before, Hash index is to store the Hash value of the Hash operation result and the corresponding row pointer information in a Hash table after Hash operation is performed on the index key. Since different index keys have the same Hash value , so even if you get the number of records that satisfy a certain Hash key value, you cannot directly complete the query from the Hash index. You still have to make corresponding comparisons by accessing the actual data in the table and get the corresponding results.

(5) When a Hash index encounters a large number of equal hash values, its performance will not necessarily be higher than that of the B-Tree index.

For index keys with low selectivity, if you create a Hash index, there will be a large number of record pointer information stored in the same Hash value. In this way, it will be very troublesome to locate a certain record, and it will waste multiple accesses to the table data, resulting in low overall performance.

B-Tree index

B-Tree index is the most frequently used index type in the MySQL database. All other storage engines except the Archive storage engine are Supports B-Tree indexes. This is not only true in MySQL, but in fact in many other database management systems, B-Tree index is also the most important index type. This is mainly because the storage structure of B-Tree index plays an important role in the data inspection of the database.

Suo Zhong has a very good performance.

Generally speaking, most of the physical files of the B-Tree index in MySQL are stored in the Balance Tree structure, that is, all the actual required data is stored in the Leaf Node of the Tree and can be accessed anywhere. The length of the shortest path of a Leaf Node is exactly the same, so we all call it a B-Tree index. Of course, various databases (or various storage engines of MySQL) may store their own B-Tree indexes. The storage structure will be slightly modified. For example, the actual storage structure used by the B-Tree index of the Innodb storage engine is actually a B Tree, which is a very small modification based on the B-Tree data structure, on each

Leaf Node. In addition to storing the relevant information of the index key, the pointer information pointing to the next LeafNode adjacent to the Leaf Node is also stored. This is mainly to speed up the efficiency of retrieving multiple adjacent Leaf Nodes.

Recommended tutorial: "MySQL Tutorial"

The above is the detailed content of What is the difference between B-Tree index and Hash index in MySQL?. For more information, please follow other related articles on the PHP Chinese website!