索引对于加快查询是非常重要的，合理使用索引能够显著提高查询速度。

MySQL中索引的实现

MySQL中索引的实现技术分两种：B-Tree索引和Hash索引。

B-Tree索引

B-Tree索引使用B+树实现。B+树一种多路查找树（如下图），是通过二叉查找树，再由平衡二叉树，B树（又名B-树）演化而来的，B+树中的B不是代表二叉（binary），而是代表平衡（balance），因为B+树是从最早的平衡二叉树演化而来，但是B+树不是一个二叉树，是多叉树。

Hash索引

Hash索引的查找速度理论上是O(1)，所以它比B-Tree索引快得多（B-Tree索引速度为O(logN)，N为索引值数量，和索引字段及记录行数有关）。但由于它更快，它的使用限制也比较多：

• 哈希索引只包含哈希值和行指针，而不存储字段值，所以不能使用索引中的值来避免读取行（即不能使用哈希索引来做覆盖索引扫描），不过，访问内存中的行的速度很快（因为memory引擎的数据都保存在内存里），所以大部分情况下这一点对性能的影响并不明显。
• 哈希索引数据并不是按照索引列的值顺序存储的，所以也就无法用于排序
• 哈希索引也不支持部分索引列匹配查找，因为哈希索引始终是使用索引的全部列值内容来计算哈希值的。如：数据列（a,b）上建立哈希索引，如果只查询数据列a，则无法使用该索引。
• 哈希索引只支持等值比较查询，如：=, in, <=>(注意，<>和<=>是不同的操作)，不支持任何范围查询（必须给定具体的where条件值来计算hash值，所以不支持范围查询）。
• 访问哈希索引的数据非常快，除非有很多哈希冲突，当出现哈希冲突的时候，存储引擎必须遍历链表中所有的行指针，逐行进行比较，直到找到所有符合条件的行。
• 如果哈希冲突很多的话，一些索引维护操作的代价也很高，如：如果在某个选择性很低的列上建立哈希索引（即很多重复值的列），那么当从表中删除一行时，存储引擎需要遍历对应哈希值的链表中的每一行，找到并删除对应的引用，冲突越多，代价越大。

所以在MySQL中，只有HEAP/MEMORY表引擎才显式支持Hash索引。我们一般用到的都是B-Tree索引。

这里只对B+树和Hash表做简单介绍，详细内容可以查看数据结构教材或者文章末尾的参考文章。

聚簇索引与非聚簇索引

聚餐索引：将数据存储和索引节点放到一起，找到索引也就找到了数据。InnoDB引擎使用这种方式。
非聚簇索引：将数据存储和索引分开存放，索引节点指向了数据的对应行。MyIASM引擎使用这种方式。

注意: 对于InnoDB来说,

1. 主键索引既存储索引值，又在叶子中存储行的数据
2. 如果没有主键(Primary key), 则会Unique key做主键
3. 如果没有Unique key，则系统生成一个内部的rowid做主键
4. 在InnoDB中，主键的索引结构中，既存储了主键值，又存储了行数据，这种结构称为”聚簇索引”

聚簇索引：
优势: 根据主键查询条目比较少时，不用回行(数据就在主键节点下)
劣势: 如果碰到不规则数据插入时，造成频繁的页分裂（想想平衡多叉树的插入）。

聚簇索引与非聚簇索引的具体讲解请查看文章末尾的第4篇查考文章。

索引优化策略：
对于InnoDB而言，因为节点下有数据文件，因此节点的分裂将会比较慢。
对于InnoDB的主键，尽量用整型，而且是递增的整型。
如果是无规律的数据插入，将会产生的页的分裂，影响速度，所以应该使用MyISAM表。

索引覆盖

索引覆盖是指：如果查询的列恰好是索引的一部分，那么查询只需要在索引文件上进行，不需要回行到磁盘再找数据。这种查询速度非常快,称为”索引覆盖”。我们应该尽量利用索引覆盖加快速度。

例题，现有一张表的部分结构如下：

create table A (
   id varchar(64) primary key,
   ver int not null,
   ...
   index key(id, ver),
   ...
) ...

问题：在(id,ver)上有联合索引，表中有10000条数据。

1. 为什么 select id from A order by id 特别慢？
2. 而 select id from A order by id,ver 非常快？

表中还有几个很长的字段text(3000)。id, (id,ver) 都有索引, select id 应该都产生”索引覆盖”的效果，为什么前者慢，而后者快？

思路：从innodb聚簇与myisam索引的不同、索引覆盖，这2个角度来考虑。
分析：对于myisam，索引都是指向磁盘上的位置(索引不存储其他列的数据,统统指到磁盘去)。而对于innodb表, id是主键,主键的叶子有其数据, (id,ver)联合索引没有数据,只是再次指向主键)。因此:

1. 表如果是myisam引擎，2个语句，速度不会有明显差异。
2. innodb表因为聚簇索引，id索引要在磁盘上跨N多块，导致速度慢。
3. 即使innodb引擎，如果没有那几个text长列，2个语句的速度也不会有明显差异。

理想的索引

如何建立理想的索引，可以参考如下原则：

1. 选择查询频繁高的字段。查询频繁高索引越有效。
2. 选择存储长度小的字段。存储长度直接影响索引文件的大小，影响增删改的速度，并间接影响查询速度(占用内存多)，所以越小越快。
3. 选择区分度高的字段，或者说字段取值越唯一越好。
4. 选择尽量能覆盖常用查询字段的多列字段。这能够利用前面所说的索引覆盖，不用回行取数据，从而加快速度。

什么是区分度高呢？例如有100万用户，性别字段基本上男、女各为50万，那么就可以说性别字段的区分度比较低。也就是某个字段的一个取值对应的记录数越少（最好是一个值只对应一个字段，那么可以使用primary key或unique key），则这个字段区分度越高。

那么对于比较长的列如何建立索引？针对列中的值，从左往右截取部分，来建索引。

1. 截的越短, 重复度越高，区分度越小, 索引效果越不好。
2. 截的越长, 重复度越低，区分度越高, 索引效果越好，但带来的影响也越大——增删改变慢，并间影响查询速度。

所以, 我们要在 区分度 + 长度 两者上，取得一个平衡。惯用手法: 截取不同长度，并测试其区分度，SQL语句如下：

select count(distinct left(col_name, N))/count(*) from tab_name;

我们可以使用上面的SQL语句计算区分度百分比，使N从1开始取值查看区分度和长度的变化，然后选取合适的N。对于一般的系统应用，区别度能达到0.1，索引的性能就可以接受。

对于左前缀不易区分的列，如URL列前面基本都是http://和https://。这种我们可以将字段翻转一下存放然后建立索引，或者将字段散列为整数之后的字段作为索引（如使用crc32函数将url散列为整数，保证这个整数位一个字段，然后使用这个字段做索引）。

索引与排序

索引不但能够加快where语句，也能够加快order by排序语句。排序可能的情况:

1. 对于覆盖索引，在InnoDB引擎中，沿着索引字段排序，也是自然有序的。不需要额外排序, 这种情况叫using index。
2. 对于覆盖索引，对于MyISAM引擎，如果按某索引字段排序。如id，但取出的字段中，有未索引字段, myisam的做法，不是索引->回行。而是先取出所有行，再进行排序。（using filesort）
3. 没有使用索引，先取出数据，形成临时表然后排序。(using filesort，使用文件排序，但文件可能在磁盘上，也可能在内存中)。

我们的争取目标——取出来的数据本身就是有序的! 只利用索引来排序（using index）。

重复索引与冗余索引

重复索引是指：如已经有了索引为index(a,b,c)，还有index(a)，index(a,b)等为前者的前缀，则称index(a)，index(a,b)为重复索引，重复索引没有任何帮助，只会增大索引文件，拖慢更新速度，需要去掉。实际上可以认为index(a,b,c)中已经包含了index(a)，index(a,b)。

冗余索引是指：2个索引所覆盖的列有重叠, 称为冗余索引。合理使用冗余索引可以优化查询，推荐使用，冗余索引比较常见。

索引碎片

在长期的数据更改过程中（增删改操作，查询操作不会）， 索引文件和数据文件都将产生空洞，形成难以利用的磁盘碎片。（类似OS内存管理里面的内存碎片）。我们可以通过一个nop操作(不产生对数据实质影响的操作), 来进行碎片整理。

innodb引擎 , 可以 alter table xxx engine innodb

还可以使用 ptimize table tab_name

注意: 修复表的数据及索引碎片，就会把所有的数据文件重新整理一遍，使之对齐。这个过程，如果表的行数比较多，会非常耗费资源和时间。所以，不能频繁的修复。

如果表的增删改操作很频率，可以按周/月为周期来修复。如果不频繁，可以以更长的周期来做修复。

参考文章

• MySQL索引是怎么实现的？ - 仰望星空脚踏实地 - CSDN博客
• B树，B-树和B+树的区别 - 简书
• mysql btree与hash索引的适用场景和限制 - xiaoboluo768 - 博客园
• 聚簇索引与非聚簇索引（也叫二级索引） - 简书