索引（在MySQL中也叫做键（key))是存储引擎用于快速找到记录的一种数据结构。这是索引的基本功能。 索引优化应该是对查询性能优化最有效的手段了，索引能够轻易将查询性能提高几个数量级，“最优”的索引有时比一个“好的”索引性能要好两个数量级。创建一个真正“最优”的索引经常需要重写查询。 索引可以包含一个或多个列的值，如果索引包含多个列，那么列的顺序也十分重要，因为MySQL只能高效地使用索引的最左前缀列。创建一个包含两个列的索引，和创建两个只包含一个列的索引是大不相同的。
索引的类型
在MySQL中，索引是在存储引擎层而不是服务器层实现的。所以，并没有统一的标准，不同存储引擎的索引的工作方式并不一样，也不是所有的存储引擎都支持所有类型的索引。即使多个存储引擎支持同一种类型的索引，其底层实现也可能不同。 下面我们看看MySQL支持的索引类型，以及它们的优缺点。
B-Tree索引
当人们谈论索引的时候，如果没有特别指明类型，那多半说的是B-Tree索引，它使用B-Tree数据结构来存储数据（实际上很多存储引擎使用的是B+Tree，即每一个叶子节点都包含指向下一个叶子节点的指针，从而方便叶子节点的范围遍历。）。大多数MySQL引擎都支持这种索引。Archive引擎是一个例外：5.1之前Archive不支持任何索引，直到5.1开始支持单个自增列（AUTO_INCREMENT）的索引。 B-Tree通常意味着所有的值都是按顺序存储的，并且每一个叶子页到根的距离相同。如图大致反映了InnoDB索引是如何工作的。
B-Tree索引能够加快访问数据的速度，因为存储引擎不再需要进行全表扫描来获取需要的数据，取而代之的是从索引的根节点开始进行搜索。根节点的槽中存放了指向子节点的指针，存储引擎根据这些指针向下层查找。通过比较节点页的值 和要查找的值可以找到合适的指针进入下层子节点，这些指针实际上定义了子节点页中值的上限和下限。最终存储引擎要么是找到对应的值，要么该记录不存在。叶子节点比较特别，它们的指针指向的是被索引的数据，而不是其他的节点页（不同引擎的指针类型不同）。上图仅绘制了一个节点和其他对应的叶子节点，其实在根节点和叶子节点之间可能有很多层节点页。树的深度和表的大小直接关系。 B-Tree对索引列是顺序组织存储的，所以很适合查找范围数据。例如，在一个基于文本域的索引树上，按字母顺序传递连续的值进行查找是非常合适的，所以像“找出所有以I到K开头的名字”这样的查找效率会非常高。 假设有如下数据表：
CREATE TABLE people
last_name varchar(50) not null,
first_name varchar(5) not null,
dob date not null,
gender enum('m','f') not null,
key(last_name,first_name,dob)
);
对于表中的每一行数据，索引中包含了last_name、first_name和dob列的值，下图显示了该索引是如何组织数据存储的。
请注意，索引对多个值进行排序的依据是CREATE TABLE语句中定义索引时列的顺序。看一下最后两个条目，两个人的姓和名都一样，则根据他们的出生日期来排序。 可以使用B-Tree索引的查询类型。B-Tree索引适用于全键值、键值范围或键前缀查找。其中键前缀查找只适用于根据最左前缀的查找。 前面所述的索引对如下类型的查询有效。
全值匹配 指的是和索引中的所有列进行匹配，例如前面提到的索引可用于查找姓名为Cuba Allen、出生于1960-01-01的人。 匹配最左前缀 前面提到的索引可用于查找所有姓为Allen的人，即只使用索引的第一列。 匹配列前缀 也可以只匹配某一列的值的开头部分。例如前面提到的索引可用于查找所有以J开头的姓的人。这里也只使用了索引的第一列。 匹配范围值 例如前面提到的索引可用于查找姓在Allen和Barrymore之间的人。这里也只使用了索引的第一列。 精确匹配某一列并范围匹配到另外一列 前面提到的索引也可用于查找所有姓为Allen，并且名字是字母K开头（比如Kim、Karl等）的人。即第一列last_name全匹配，第二列first_name范围匹配。 只访问索引的查询 B-Tree通常可以支持“只访问索引的查询”，即查询只需要访问索引，而无须访问数据行。
因为索引树的节点是有序的，所以除了按值查找之外，索引还可以用于查询中的ORDER BY操作（按顺序查找）。一般来说，如果B-Tree可以按照某种方式查找到值，那么也可以按照这种方式用于排序。所以，如果ORDER BY子句满足前面列出的几种查询类型，则这个索引也可以满足对应的排序需求。
下面是一些关于B-Tree索引的限制： 如果不是按照索引的最左列开始查找，则无法使用索引。例如上面例子中的索引无法用于查找名字为Bill的人，也无法查找某个特定生日的人，因为这两列都不是最左数据列。类似地，也无法查找姓氏以某个字母结尾的人。 不能跳过索引中的列，也就是说，前面所述的索引无法用于查找姓为Smith并且在某个特定日期出生的人，如果不指定名（first_name),则MySQL只能使用索引的第一列。 如果查询中有某个列的范围查询，则其右边所有列都无法使用索引优化查找。例如有查询where last_name='Smith' and first_name like 'J%' and dob='1976-12-23',这个查询只能使用索引的前两列，因为这里like是一个范围条件（但是服务器可以把其余列用于其他目的）。如果范围查询列值的数量有限，那么可以通过用多个等于条件来代替范围条件。
到这里读者应该可以明白，前面提到的索引列的顺序是多么的重要：这些限制都和索引列的顺序有头。在优化性能的时候，可能需要使用相同的列但是顺序不同的索引来满足不同类型的查询需求。
哈希索引
（hash index）是基于哈希表实现，只有精确匹配索引所有列的查询才有效。对每一行数据，存储引擎都会对所有的索引列计算一个哈希码(hash code)，哈希码是一个较小的值，并且不同键值的行计算出来的哈希码也不一样。哈希索引所有的哈希码存储在索引中，同时在哈希表中保存指向每个数据行的指针。 在MySQL中，只有Memory引擎显式支持哈希索引。这也是Memory引擎表的默认索引类型，Memory引擎同时也支持B-Tree索引。值得一提的是，Memory引擎是支持非唯一哈希索引的，这在数据库世界里面是比较与众不同的。如果多个列的哈希值相同，索引会以链表的方式存放多个记录指针到同一个哈希条目中。
InnoDB引擎有一个特殊的功能叫做“自适合哈希索引(adaptive hash index)"。当InnoDB注意到某些索引值被使用的非常频繁时，它会在内存中基于B-Tree索引之上再创建一个哈希索引，这样就让B-Tree索引也具有哈希索引的一些优点，比如快速的哈希查找。这是一个完全自动的、内部的行为，用户无法控制或者配置，不过如果有必要，完全可以关闭该功能。
创建自定义哈希索引。
如果存储引擎不支持哈希索引，则可以模拟像InnoDB一样创建哈希索引，这可以享受一些哈希索引的便利，例如只需要很小的索引就可以为超长的键创建索引。
思路很简单：在B-Tree基础上创建一个伪哈希索引。这和真正的哈希索引不是一回事，因为使用B-Tree进行查找，但是它使用哈希值而不是键本身进行索引查找。你需要做的就是在查询的where子句中手动指定使用哈希函数。
下面是一个实例，例如需要存储大量的URL，并需要根据URL进行搜索查找。如果使用B-Tree来存储URL，存储的内容就会很大，因为URL本身都很长。正常情况下会有如下查询：
mysql>select id from url where url="http://www.mitnick.fun";
若删除原来的URL列上的索引，而新增一个被索引的url_crc列，使用CRC32做哈希，就可以使用下面的方式查询：
mysql>select id from url where url="http://www.mitnick.fun" and url_crc=CRC32("http://www.mitnick.fun");
这样做的性能会非常高，因为MySQL优化器会使用这个选择性很高而体积很小的基于url_crc列的索引来完成查找（在上面的案例中，索引值为1293670212）。即使有多个记录有相同的索引值，查找仍然很快，只需要根据哈希值做快速的整数比较就能找到索引条目，然后一一比较返回对应的行。另外一种方式就是对完整的URL字符串做索引，那样会非常慢。
这样实现的缺陷是需要维护哈希值。可以手动维护，也可以使用触发器实现。下面的案例演示了触发器如何在插入和更新时维护url_crc列。
首先创建如下表：
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)
);
然后创建触发器。先临时修改一下语句分隔符，这样就可以在触发器定义中使用分号：
delimiter //
create trigger pseudohash_crc_ins before insert on pseudohash for each row begin
set new.url_crc=crc32(new.url);
end;
//
create trigger pseudohash_crc_upd before update on pseudohash for each row begin
set new.url_crc=crc32(new.url);
end;
//
delimiter ;
剩下的工作就是验证一下触发器如何维护哈希索引：
mysql>insert into pseudohash(url) values('http://www.lamnick.com');
mysql>select * from pseudohash;
mysql>update pseudohash set url='http://www.mitnick.fun/php/397' where id=1;
mysql>select * from pseudohash;
如果采用这种方式，记住不要使用sha1()和md5()作为哈希函数。因为这两个函数计算出来的哈希值是非常长的字符串，会浪费大量空间，比较时也会更慢。sha1()和md5()是强加密函数，设计目标是最大限度消除冲突，但这里并不需要这样高的要求。签单哈希函数的冲突在一个可以接受的范围，同时又能够提供更好的性能。
如果数据表非常大，crc32()会出现大量的哈希冲突，则可以考虑自己实现一个简单的64位哈希函数。这个自定义函数要返回整数，而不是字符串。一个简单的办法可以使用md5()函数返回值的一部分来作为自定义哈希函数。这可能比自己写一个哈希算法的性能要差，不过这样实现最简单：
mysql>select conv(right(md5('http://www.lamnick.com/'),16),16,10) as hash64;
处理哈希冲突。当使用哈希索引进行查询的时候，必须在where子句中包含常量值：
mysql>select id from url where url="http://www.mitnick.fun" and url_crc=CRC32("http://www.mitnick.fun");
一旦出现哈希冲突，另一个字符串的哈希值也刚好是1293670212，则下面的查询是无法正确工作的。
mysql>select id from url wher url_crc=CRC32("http://www.mitnick.fun");
出现哈希冲突的概率的增长速度可能比想象的要快得多。crc32()返回的是32位整数，当索引有93000条记录时出现冲突的概率是1%。要避免冲突问题，必须在where条件中带入哈希值和对应列值。如果不是想查询具体值，例如只是统计记录数（不精确的），则可以不带入列值，直接使用crc32()的哈希值查询即可。
还可以使用如FNV64()函数作为哈希函数，这是移植自percona server的函数，可以以插件的方式在任何MySQL版本中使用，哈希值为64位，速度快，且冲突比crc32()要少很多。
全文索引
一种特殊类型的索引，它查找的是文本中的关键词，耍不是直接比较索引中的值。全文搜索和其他几类索引的匹配方式完全不一样。它有许多需要注意的细节，如停用词，词干和复数，布尔搜索等。全文索引更类似于搜索引擎做的事情，而不是简单的where条件匹配。 在相同列上同时创建全文索引和基于值的B-Tree索引不会有冲突，全文索引适用于match against操作，而不是普通的where条件操作。
转载请注明：MitNick » 001MySQL创建高性能的索引-索引基础
