What is a hash index?

Hash index （hash index） Implementation based on hash table , Only queries that exactly match all columns of the index are valid , For each row of data , The storage engine calculates a hash code for all index columns , The hash code is a smaller value , And the hash codes calculated by the lines with different key values are also different . Hash code index stores all hash codes in the index , At the same time, store the pointer to each data row in the hash table .
adopt Hash Algorithm （ common Hash The algorithm has direct address method 、 Square with the middle method 、 Folding method 、 Division and remainder 、 Random number method ）, Convert database field data to fixed length Hash value , Store with the row pointer of this data Hash The corresponding position of the table ; In case of Hash Collision （ Two different keywords Hash Same value ）, It corresponds to Hash The key is stored as a linked list
Because the index itself only needs to store the corresponding hash value , So the structure of the index is very compact , This also makes hash index lookup very fast . However , Hash index also has its limitations ：

• Hash index only contains hash value and row pointer , Instead of storing field values , So you can't use the values in the index to avoid reading rows , however , Access to rows in memory is very fast , So in most cases, the impact on performance is not obvious .
• Hash index data is not stored in the order of index values , So it can't be used for sorting
• Hash index also does not support partial index column matching lookup , Because the hash index always uses the entire content of the index column to calculate the hash value .
• Hash index only supports equivalent comparison query , Include =、IN()、<=>、 No scope queries are supported .
• Accessing hash index data is very fast , Unless there are many hash conflicts （ Different index column values have the same hash value ）. When there is a hash conflict , The storage engine must traverse all row pointers in the linked list , Compare line by line , Until you find all the right lines .
• If there are many hash conflicts , Some index maintenance operations are also expensive . for example , If at some point the selectivity is low （ There are a lot of hash conflicts ） Create a hash index on the column of , So when you delete a row from the table , The storage engine needs to traverse each row in the linked list corresponding to the hash value , Find and delete the corresponding reference , The more conflicts , The more it costs .
  Because of these restrictions , Hash index is only suitable for some specific situations . And once it's fit for a hash index , The performance improvement it brings will be very significant . for instance , In the application of data warehouse, there is a classic “ Star type ” schema, Many lookup tables need to be associated , Hash index is very suitable for the needs of lookup table .
  except Memory Outside the engine ,NDB The cluster engine also supports unique hashing indexes , And in NDB The role of the cluster engine is very special .
  InnoDB The engine has a special function called “ adaptive hash index ”, When InnoDB Notice that some index values are used very frequently , It will be based in memory on B-Tree Create a hash index above the index , In this way B-Tree Index pages have some of the advantages of hash indexing , For example, fast hash lookup . This is a completely automatic 、 Internal behavior , Users cannot control or configure , But if necessary , This function can be turned off completely .