[TOC] # 简介 索引有很多类型,可以为不同的场景提供更好的性能.在mysql中,索引是存储引擎层面而不是服务器层实现. 所以,并没有统一的索引标准,不同存储引擎的索引的工作方式并不一样,也不是所有的存储引擎都支持所有类型的索引.即使多个存储引擎支持同一种类型的索引,其底层的实现也可能不同 # B-Tree索引 大多数mysql都支持这种索引 不过底层的存储引擎也可能使用不同的存储结构,例如,NDB集群存储引擎内部实际上使用了T-Tree结构存储这种索引,即使其名字是BTREE,Innodb则使用B+Tree 存储引擎以不同方式使用B-Tree索引,性能也各有不同,各有优劣.例如:myisam使用前缀压缩技术使得索引更小,但是Innodb则按照原数据格式进行存储 再如myisam索引通过数据的物理位置引用被索引的行,而Innodb则根据主键引用被索引的行 B-Tree通常意味着所有的值都是按顺序存储的,并且每一个叶子页到根的距离相同  建立在B-Tree结构(从技术上来说是B+Tree)上的索引 假设有如下数据表 ~~~ create table People ( last_name varchar(50) not null, first_name varchar(50) not null, dob date not null, gender enum('m','f') not null, key(last_name, first_name, dob) ); ~~~ 下面是B-Tree索引的限制 * 如果不是按照索引的最左列开始查找,则无法使用索引.例如上面例子中,查找 first_name, dob,因为这不是罪左数据列 * 不能跳过索引中的列,也就是说前面所述的索引无法用于跳过first_name * 如果查询中有某个列的范围查询,其右边所有列都无法使用索引优化查找. ~~~ where last_name='Smith' and first_name like 'J%' and dob='1976-12-23' ~~~ 这个查询只能使用索引的前两列,因为这里like是一个范围条件 索引列的顺序是多么重要,这些限制都和索引列的顺序有关.在优化性能的时候,可能需要使用相同的列但顺序不同的索引来满足不同类型的查询需求 # 哈希索引 哈希索引基于哈希表实现,只有精确匹配索引所有列的查询才有效. 对于每一行数据,存储引擎都会对所有的索引列计算一个哈希码(hash code),哈希码是一个较小的值,并且不同键值的行计算出来的哈希码也不一样.哈希索引将所有的哈希码存储在索引中,同时在哈希表中保存指向每个数据行的指针 在mysql中,只有memory引擎显示支持哈希索引.这也是memory引擎表的默认索引类型.memory引擎同时也支持B-Tree索引.值得一提的是,memory引擎是支持非唯一哈希索引的,这在数据库世界里面是比较与众不同的 如果多个列的哈希值相同,索引会以链表的方式存放多个记录的指针到同一个哈希条目中 下面来看个例子 ~~~ create table testhash ( fname varchar(50) not null, lname varchar(50) not null, key using hash(fname) )engine=memory; ~~~ 表中包含了如下的数据  假设索引使用假象的哈希函数f(),他返回下面的值(都是示例数据,非真实数据)  则哈希索引的数据结构如下  注意每个槽的编号是顺序的,但是数据行不是.现在,来看如下查询 ~~~ select lname from testhash where fname = 'Peter'; ~~~ mysql先计算'Peter'的哈希值,并使用该值寻找对应的记录指针,因为f('Peter') = 8784,所以mysql在索引中查找8784,可以找到指向第三方的指针,最后一步是比较第三行的值是否为'Peter',以确保就是要查找的行 因为索引自身只需存储对应的哈希值,所以索引的结构十分紧凑,这也让哈希索引查找的速度非常快.然而,哈希索引也有它的限制 * 哈希索引只包含哈希值和行指针,而不存储字段值,所以不能使用索引中的值来避免读取行.不过,访问内存中的行的速度很快,所以大部分情况下这一点对性能影响并不明显 * 哈希索引数据并不是按照索引值顺序存储,所以也就无法用于排序 * 哈希索引也不支持部分索引列匹配查找,因为哈希索引始终是使用索引列的全部内容来计算哈希值的.例如,在数据列(A,B)上建立哈希索引,如果查询只有数据列A,则无法使用该索引 * 哈希索引只支持等值比较查询,包括=,IN(),<=>,(注意<>和<=>是不同操作).也不支持任何范围查询,例如`where price > 100` * 访问哈希索引的数据非常快,除非有很多哈希冲突(不同的索引列值却有相同的哈希值).当出现哈希冲突的时候,存储引擎必须遍历链表中的所有行指针,逐行进行比较,直到找到符合条件的行 * 如果哈希冲突很多的话,一些索引维护操作的代价也会很高.例如,如果在某个选择性很低(哈希冲突很多)的列上建立哈希索引,那么当从表中删除一行时,存储引擎需要遍历对应哈希值的链表中的每一行,找到并删除对应行的引用,冲突越多,代价越大 因为这些限制,哈希索引只适用于某些特定的场合.而一旦适合哈希索引,则它带来的性能提升将非常显著.举个例子,在数据仓库应用中有一种经典的"星型" schema,需要关联很多查找表,哈希索引就非常适合查找表的需求 除了memory引擎外,NDB集群引擎也支持唯一哈希索引,且在NDB集群引擎中作用非常特殊 Innodb引擎有一个特殊的功能叫做"自适应哈希索引".当Innodb注意到某些索引值被使用得非常频繁时,他会在内存中基于B-Tree索引之上再创建一个哈希索引,这样就让B-Tree索引也具有哈希索引的一些优点,比如快速的哈希查找.这是一个完全自动的,内部的行为,用户无法控制或者配置,不过如果有必要,完全可以关闭该功能 创建自定义哈希索引,如果存储引擎不支持哈希索引,则可以模拟像Innodb一样创建哈希索引,这可以享受一些哈希索引的便利,例如只需要很小的索引就可以为超长的键创建索引 思路很简单:在B-Tree基础上创建一个伪哈希索引.这和真正的哈希索引不是一回事,因为还是使用B-Tree进行查找,但是他使用哈希值而不是键本身进行索引查找.你需要做的就是在查询的where子句中手动指定使用的哈希函数 下面是一个实例,例如需要存储大量的URL,并需要根据URL进行搜索查找,如果使用B-Tree来存储URL,存储的内容就会很大,因为URL本身很长.正常情况下会有如下查询 ~~~ select id from url where url = "http://www.mysql.com" ~~~ 若删除原来URL列上的索引,而新增一个被索引的url_crc列,使用CRC32做哈希,就可以使用下面的方式查询 ~~~ select id from url where url="http://www.mysql.com" and url_crc=CRC32("http://www.mysql.com"); ~~~ 这样做的性能会非常高,因为mysql优化器会使用这个选择性很高而体积很小的基于url_crc列的索引来完成查找(在上面的案列中,索引值为1560514994).即使有多个记录相同的索引值,查找仍然很快,只需要根据哈希值做快速的整数比较就能找到索引条目,然后一一比较返回对应的行.另外一种方式就是对完整的URL字符串做索引,那样会非常慢 这样实现的缺陷是需要维护哈希值.可以手动维护,也可以使用触发器实现.下面的案列演示了触发器如何在插入和更新时维护url_crc列.首先创建如下表  然后创建触发器.先临时修改一下语句分割符,这样就可以在触发器定义中使用分号  剩下的就是验证一下触发器如何维护哈希索引  如果采用这种方式,记住不要使用sha1()和md5()作为哈希函数.因为这两个函数计算出来的哈希值是非常长的字符串,会浪费大量的空间,比较时也会更慢.sha1()和md5()是强加密函数,设计目标是最大限度消除冲突,但这里并不需要达到这样高的要求.简单哈希函数的冲突在一个可以接受的范围,同时又能够提供更好的性能 如果数据表非常大,CRC32()会出现大量的哈希冲突,则可以考虑自己实现一个简单的64位哈希函数. 这个自定义函数要返回整数而不是字符串.一个简单的方法可以使用MD5()函数的返回值的一部分来作为自定义哈希函数.这可能比自己写一个哈希算法的性能要差,不过这样实现最简单  处理哈希冲突,当使用哈希索引进行查询的时候,必须在where子句中包含常量值 ~~~ select id from url where url_crc=CRC32("http://www.mysql.com") and url="http://www.mysql.com"; ~~~ 一旦出现哈希冲突,另一个字符串的哈希值也恰好是1560514994,则下面的查询是无法正确工作 ~~~ select id from url where url_crc=CRC32("http://www.mysql.com"); ~~~ 因为所谓的"生日悖论",出现哈希冲突的概念的增长速度可能比想象的要快得多.CRC32()返回的是32位的整数,当索引有9300条记录时出现冲突的概率是1%.例如我们将/usr/share/dict/words中的词导入数据表并进行CRC32()计算,最后会有98569行这就已经出现一次哈希冲突,冲突让下面的查询返回了多条记录  正确的写法应该如下  要避免冲突问题,必须在where条件中带入哈希值和对应列值.如果不是想查询具体值,例如只是统计记录数(不精确的),则可以不带入列值,直接使用CRC32()的哈希值查询即可.还可以使用如FNV64()函数作为哈希函数,哈希值64位,速度快,而且冲突比CRC32()要少很多