MySQL interview questions explain how to set hash index

Source of the article ： Learn through http://www.bdgxy.com/

except B-Tree Indexes ,MySQL The following index is also provided ：

• Hash Indexes

Only Memory Engine support , The scene is simple

• R-Tree Indexes

MyISAM A special index type of , Mainly used for geospatial data types

• Full-text

MyISAM A special index of , Mainly used for full-text indexing , from MySQL 5.6 Start InnoDB Full text index support

Indexes / Storage engine MyISAMInnoDBMemoryB-Tree Index support HASH Index not supported... Not supported R-Tree Index support does not support Full-text Index support does not support

The most commonly used index is B-tree Index and Hash Indexes , And only Memory, NDB Two engines support Hash Indexes . Hash Index for key-value Inquire about , adopt Hash Index ratio B-tree Index queries faster . but Hash Index does not support range lookups, for example <><==,>== etc. . Memory Only in "=" It can only be used under the condition of hash Indexes

MySQL stay 8.0 Function index is supported , Before that, only the first part of the column can be indexed , For example, the title title Field , You can only take title Before 10 Character index , This feature greatly reduces the size of the index file , But prefix index also has disadvantages , stay order by and group by Failure during operation .

create index idx_title on film(title(10));

1 characteristic

Only arrays exist , Use one hash Function key Convert to a determined memory location , And then put value In this position of the array . Use hash Naturally, hash conflicts may occur ,MySQL Take zipper method to solve the problem .

Hash The index is based on Hash Table implementation , Only the query conditions match exactly Hash Columns in the index , Can be used hash Indexes . about Hash All columns in the index , The storage engine calculates one for each row hashcode,Hash What is stored in the index is hashcode.

• For example, a table that maintains the ID number and name. , Find the corresponding name according to the ID card number. , Its hash The index is as follows ：

For example, we want to find out ID_card_n4 Corresponding username：

• take ID_card_n4 adopt hash Function calculation A
• Traverse in order , find User4

four ID_card_n The value does not necessarily increase , So even if you add new User, Too fast , Just add after . Of course, the disadvantages are obvious , It's not order , therefore hash The speed of index interval query is very slow . For example, you need to find the ID card number. [ID_card_X, ID_card_Y] All users in the range , Full table scan is required .

2 Hash Defects of index

• You have to find it again
• Partial index lookup is not supported 、 Range lookup
• Hash code may have hash conflict , If hash The algorithm design is not good , Too many collisions , Performance will get worse, too
• The index stores hash value , So only support < = > as well as IN
• Cannot sort by operating index , Because it will pass when it is stored hash Calculation , But it's hard to calculate hash Values and stored values are not necessarily equal , So it can't be sorted
• Full table scan cannot be avoided , It's just because I'm here memory Non unique values are supported in tables hash Indexes , That is, different index keys , There may be the same problem hash value
• Because hash table is a data structure that directly accesses memory storage location according to keywords , Therefore, it is necessary to make use of its principle hash Indexes , All data files need to be added to memory , This is memory intensive
• If all queries are equivalent queries , that hash Really fast , But there's actually more data to look up in scope
• Intelligent processing key value full value matching
• Inquire about Hash Function determines the size of the index key

To make InnoDB or MyISAM Support hash index , It can be implemented by pseudo hash index , Adaptive index .

You can add a field , Storage hash value , take hash Value index , When inserting and updating , Set up triggers , Automatically add calculated hash Go inside the watch .

This structure of hash table is applicable to the scenario with only equivalent query , such as Memcached.

3 Case application

Suppose there is a very, very large watch , For example, users need to log in through the email Retrieve users , If you are directly in email Column index , Except index interval matching , String matching is also needed ,email Short, OK , If it is long, the cost of this query is relatively high . If at this time , stay email Build hash index , Query to int Inquire about , Performance is much faster than string comparison queries .

Hash Algorithm

Build hash index , The first step is to select the hash algorithm ,《 High performance MySQL》 Speaking of CRC32 Algorithm .

INSERT UPDATE SELECT operation

Add... To the table hash The field of the value ：

ALTER TABLE `User` ADD COLUMN email_hash int unsigned NOT NULL DEFAULT 0;

And then there's the UPDATE and INSERT when , Auto update email_hash Field , It is realized by trigger ：

DELIMITER |
CREATE TRIGGER user_hash_insert BEFORE INSERT ON `User` FOR EACH ROW BEGIN
SET NEW.email_hash=crc32(NEW.email);
END;
|
CREATE TRIGGER user_hash_update BEFORE UPDATE ON `User` FOR EACH ROW BEGIN
SET NEW.email_hash=crc32(NEW.email);
END;
|
DELIMITER ;

such SELECT The request will become ：

SELECT `email`, `email_hash` FROM `User` WHERE 
	email_hash = CRC32(“[email protected]”) 
			AND `email`= “[email protected]”;

+----------------------------+------------+
| email                    |  email_hash  |
+----------------------------+------------+
| [email protected] | 2765311122 |
+----------------------------+------------+

AND email = "[email protected]" This is to prevent the data from being inaccurate in hash collision .

This is about MySQL Explain how to set the interview questions Hash That's all for the index article , More about MySQL Set up Hash Index content please search rookie tutorial www.piaodoo.com Previous articles or continue to browse the relevant articles below. I hope you can support rookie tutorials in the future www.piaodoo.com！