MySQL中的索引----哈希索引
该系统采用哈希表作为基础架构实现哈希索引功能，在处理精确匹配查询时具有高度的有效性。对于每条记录而言，数据库管理系统都会根据其所有索引字段生成对应的哈希值。这些数值通常具有较短长度，并且能够唯一标识不同的键值对。该方法通过将所有计算出的哈希值组织存放在特定的数据结构中，并结合指针机制实现了高效的查询操作。
该Memory engine supports non-unique hash indexes, meaning that if multiple columns share the same hash value, the index will store multiple record pointers in a chain pointing to the same hash bucket. For example, consider the following table:
CREATE TABLE testhash (
fname VARCHAR(50) NOT NULL,
lname VARCHAR(50) NOT NULL,
KEY USING HASH(fname)
) ENGINE=MEMORY; //指定存储引擎表中有以下数据：
+-------+-----------+
|fname|lname|
+-------+-----------+
|Arjen|Lentz|
|---|---|
|Peter|Zaitsev|
|Vadim|Tkachenko|
+-------+-----------+假设索引基于设想的哈希函数f（）运算，则该函数能够生成以下数值：
f(\text{Arjen}) = 2323，
f(\text{Baron}) = 7437，
f(\text{Peter}) = 8784，
f(\text{Vadim}) = 2458。
其哈希索引的数据结构如下：
| 槽（Slot） | 值（Value） |
|---|---|
| 2323 | 指向第1行的指针 |
| 2458 | 指向第4行的指针 |
| 7437 | 指向第2行的指针 |
| 8784 | 指向第3行的指针 |
注意到每个槽的编号是顺序的，但是数据行不是。现在看一下如下查询：
mysql> select lname from testhash where fname='Peter';MySQL通过计算'Peter'这一字符串生成其相应的哈希值，并利用该数值来确定需要访问的具体记录位置。当执行f('Peter')运算得到结果8784后，在索引结构中搜索该数值即可确定指向第3行的位置。最终需要验证第3行的实际数据是否与'Peter'一致。这一过程依赖于Memory引擎所采用的链表结构来处理哈希冲突问题。由于索引仅存储对应的哈希信息而非原始数据内容，则使得其在构建和查询时均具备极高的效率优势；然而这种设计也带来了一定的空间占用限制以及潜在的时间复杂度问题需要加以注意和优化处理
- 哈希索引仅包含哈希值和行指针而不存储字段值因此无法通过索引中的值来跳过读取特定行。不过由于内存访问速度较快对性能的影响通常不大。
- 哈希索引的数据并非按其键值顺序存储因此也无法用于排序操作。
- 哈希索引不支持基于部分列组合的查询因为构建时会综合所有选定列的数据来生成键值。
- 哈希索引仅限于等值比较操作包括= IN() 以及无序比较操作例如WHERE price LIKE '%100'。
- 在正常情况下访问哈希索引的速度非常快除非发生大量哈希冲突即不同的键值却生成相同的中间码导致必须遍历整个链表以找到符合条件的结果。
- 如果遇到大量的哈希冲突某些高级维护操作的成本也会显著增加例如在选择度极低但冲突率较高的字段上建立哈希索引删除操作时需要遍历对应的链表逐一清除相关引用从而带来较高的执行代价。
创建自定义哈希索引
为自定义索引设计一个方案：基于B-Tree构建一个伪哈希索引结构，虽然本质上与传统索引不同，其查找机制仍基于B-Tree数据结构。该伪哈希索引采用哈希值而非原始键值进行查找操作（主要原因在于原始索引可能过长导致比较不便或占用过多存储空间）。在WHERE子句中需明确定义该哈希函数的具体实现以完成查找逻辑。
为了高效管理大量链接，在现有数据库设计中如果将该字符串作为唯一键，则内存占用过高。因此建议放弃原有索引并创建一个新字段url_crc用于存储哈希值。我们可以利用crc32函数计算出对应的数值，并在构建新表时应同时生成唯一约束以减少冗余计算。代码如下：
#建一个表，将url作为索引列
mysql> create table pseudohash (
-> id int unsigned NOT NULL auto_increment,
-> url varchar(255) NOT NULL,
-> url_crc int unsigned NOT NULL DEFAULT 0,
-> PRIMARY KEY(id)
-> );然后创建触发器，让其在插入或者更新表的时候自动更新url_crc列
#改变一下语句执行的分隔符
mysql> DELIMITER //
#创建触发器
mysql> CREATE TRIGGER pseudohash_crc_ins BEFORE INSERT ON pseudohash FOR EACH ROW BEGIN
-> SET NEW.url_crc=crc32(NEW.url);
-> END;
-> //
mysql> CREATE TRIGGER pseudohash BEFORE UPDATE ON pseudohash FOR EACH ROW BEGIN
-> SET NEW.url_crc=crc32(NEW.url);
-> END;
-> //
#改为原来的分隔符
mysql> DELIMITER ;每当进行更新操作时，“哈希索引”的内容也会随之更新。然而我们不能将这一列直接用作索引列因为这可能导致频繁发生的哈希冲突问题从而引发错误。在执行查询语句时需要按照如下方式书写MySQL优化器将会利用高度优化且占用空间极小的基于URL CRC值的索引结构来进行高效的查找操作：
mysql> SELECT * FROM pseudohash WHERE url="http://www.mysql.com/"
-> AND url_crc=CRC32("http://www.mysql.com/");在进行查询操作时应尽量避免出现冲突问题，在WHERE子句中必须包含哈希值以及对应的列名。如果只需获取非具体数据（例如统计总记录数），则无需提供对应列的信息。可以直接基于CRC32()计算出的哈希值进行WHERE条件筛选。