Shulou(Shulou.com)06/01 Report--

Is there any difference between B-Tree index and Hash index in MySQL? Many novices are not very clear about this. In order to help you solve this problem, the following editor will explain it in detail. People with this need can come and learn. I hope you can gain something.

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.

2. Both MyISAM and InnoDB support B-Tree indexes, while Hash indexes are only supported by Memory and NDB engine indexes.

Hash index

Hash, generally translated as "hash", is also transliterated as "hash", that is, the input of any length (also known as pre-mapping, pre-image) is transformed into a fixed-length output by hashing algorithm, which is the hash value. This transformation is a compressed mapping, that is, the space of the hash value is usually much smaller than that of the input, and different inputs may be hashed into the same output, so it is not possible to determine the input value uniquely from the hash value. To put it simply, it is a function that compresses a message of any length into a message digest of a fixed length.

Many people may wonder again, since Hash indexes are much more efficient than B-Tree, why don't everyone use Hash indexes instead of B-Tree indexes? Everything has two sides, and so is Hash index. although Hash index is efficient, Hash index itself brings a lot of limitations and disadvantages because of its particularity.

(1) Hash indexes can only satisfy "=", "IN" and "" queries, but cannot use range queries.

Because the Hash index compares the Hash value after the Hash operation, it can only be used for equivalent filtering, not for range-based filtering, because the size relationship of the Hash value processed by the corresponding Hash algorithm cannot be guaranteed to be exactly the same as before the Hash operation.

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

Because the Hash index stores the Hash value after Hash calculation, and the size relationship of the hash value is not necessarily the same as the key value before the Hash operation, the database cannot use the index data to avoid any sort operation.

(3) Hash indexes cannot be queried by partial index keys.

For a composite index, the Hash index calculates the Hash value by combining the index keys and then calculating the Hash value together, rather than calculating the Hash value separately, so the Hash index cannot be utilized when querying through one or more of the first index keys of the composite index.

(4) Hash indexes can not avoid table scans at any time.

As we already know, the Hash index stores the Hash value of the Hash operation result and the corresponding row pointer information in a Hash table after the index key is calculated through Hash. Because different index keys have the same Hash value, even if you take the number of records that meet a certain Hash key value, you can not directly complete the query from the Hash index, or you have to access the actual data in the table to compare and get the corresponding results.

(5) when a large number of hash values are equal, the performance of Hash index is not necessarily higher than that of B-Tree index.

For index keys with low selectivity, if you create a Hash index, there will be a large amount of record pointer information associated with the same Hash value. In this way, it will be very troublesome to locate a record, which will waste many visits to table data, resulting in poor overall performance.

B-Tree index

B-tree (multipath search tree, not binary) is a common data structure. The use of B-tree structure can significantly reduce the intermediate process of locating records, thus speeding up access speed. According to the translation, B is usually regarded as the abbreviation of Balance. This data structure is generally used for the index of the database, and the comprehensive efficiency is high.

Generally speaking, most of the physical files of the B-Tree index in MySQL are stored in the structure of Balance Tree, that is, all the actual data are stored in the Leaf Node of Tree, and the length of the shortest path to any Leaf Node is exactly the same, so we all call it the B-Tree index. It is possible that various databases (or MySQL's various storage engines) will slightly modify the storage structure when storing their own B-Tree indexes. For example, the actual storage structure used by the B-Tree index of the Innodb storage engine is actually B+Tree, that is, a small modification has been made on the basis of the B-Tree data structure.

The LeafNode not only stores the relevant information of the index key, but also stores the pointer information to the next LeafNode adjacent to the LeafNode, which is mainly to speed up the efficiency of retrieving multiple adjacent LeafNode.

Is it helpful for you to read the above content? If you want to know more about the relevant knowledge or read more related articles, please follow the industry information channel, thank you for your support.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.