一、定义

索引是一种数据结构，存储表中特定列的值并进行排序，方便查询这个特定列，就好比一本书的目录，可以更快的根据目录查找所需的内容。

索引的优点

通过创建唯一性索引，可以保证数据库表中每一行数据的唯一性。
可以大大加快数据的检索速度，避免进行全表的数据扫描，大大减少遍历匹配的行数，这也是创建索引的最主要的原因。
可以加速表和表之间的连接，特别是在实现数据的参考完整性方面特别有意义。
在使用分组和排序子句进行数据检索时，同样可以显著减少查询中分组和排序的时间。
通过使用索引，可以在查询的过程中，使用优化隐藏器，提高系统的性能。

索引的缺点

创建索引和维护索引要耗费时间，这种时间随着数据量的增加而增加。
索引需要占物理空间，除了数据表占数据空间之外，每一个索引还要占一定的物理空间，如果要建立聚簇索引，那么需要的空间就会更大。
当对表中的数据进行增加、删除和修改的时候，索引也要动态的维护，这样就降低了数据的维护速度。

在哪些列建立索引

在经常需要搜索的列上，可以加快搜索的速度；
在作为主键的列上，强制该列的唯一性和组织表中数据的排列结构；
在经常用在连接的列上，这些列主要是一些外键，可以加快连接的速度；
在经常需要根据范围进行搜索的列上创建索引，因为索引已经排序，其指定的范围是连续的；
在经常需要排序的列上创建索引，因为索引已经排序，这样查询可以利用索引的排序，加快排序查询时间；
在经常使用在WHERE子句中的列上面创建索引，加快条件的判断速度。

不在哪些列建索引？

对于那些在查询中很少使用或者参考的列不应该创建索引。这是因为，既然这些列很少使用到，因此有索引或者无索引，并不能提高查询速度。相反，由于增加了索引，反而降低了系统的维护速度和增大了空间需求。
对于那些只有很少数据值的列也不应该增加索引。这是因为，由于这些列的取值很少，例如人事表的性别列，在查询的结果中，结果集的数据行占了表中数据行的很大比例，即需要在表中搜索的数据行的比例很大。增加索引，并不能明显加快检索速度。
对于那些定义为text, image和bit数据类型的列不应该增加索引。这是因为，这些列的数据量要么相当大，要么取值很少。
当修改性能远远大于检索性能时，不应该创建索引。这是因为，修改性能和检索性能是互相矛盾的。当增加索引时，会提高检索性能，但是会降低修改性能。当减少索引时，会提高修改性能，降低检索性能。因此，当修改性能远远大于检索性能时，不应该创建索引。

二、索引的数据结构

常见的索引的数据结构有：B+Tree、Hash索引、FullText索引、R-Tree索引。

Hash 索引

1. 概述：

MySQL 中，只有Memory存储引擎支持Hash索引，是Memory表的默认索引类型。hash 索引把数据的索引以 hash 值形式组织起来，因此检索效率非常高，可以一次定位，不像B-/+Tree索引需要进行从根节点到叶节点的多次 IO 操作。

2. Hash 索引的缺点：

① Hash 索引仅仅能满足等值的查询，不能满足范围查询。因为数据在经过 Hash 算法后，其大小关系就可能发生变化。 ② Hash 索引不能被排序。同样是因为数据经过 Hash 算法后，大小关系就可能发生变化，排序是没有意义的。

③ Hash 索引不能避免表数据的扫描。因为发生 Hash 碰撞时，仅仅比较 Hash 值是不够的，需要比较实际的值以判定是否符合要求。

④ Hash 索引在发生大量 Hash 值相同的情况时性能不一定比 B-Tree 索引高。因为碰撞情况会导致多次的表数据的扫描，造成整体性能的低下，可以通过采用合适的 Hash 算法一定程度解决这个问题。

⑤ Hash 索引不能使用部分索引键查询。因为当使用组合索引情况时，是把多个数据库列数据合并后再计算 Hash 值，所以对单独列数据计算 Hash 值是没有意义的。

FullText 索引

1. 概述：

全文索引，目前 MySQL 中只有MyISAM存储引擎支持，并且只有char、varchar、text 类型支持。它用于替代效率较低的like 模糊匹配操作，而且可以通过多字段组合的全文索引一次性全模糊匹配多个字段。

2. 存储结构：

同样使用B-Tree存放索引数据，但使用的是特定的算法，将字段数据分割后再进行索引（一般每 4 个字节一次分割），索引文件存储的是分割前的索引字符串集合，与分割后的索引信息，对应 Btree 结构的节点存储的是分割后的词信息以及它在分割前的索引字符串集合中的位置。

B-/+Tree 索引

B+Tree 是 mysql 使用最频繁的一个索引数据结构，是 Innodb 和 Myisam 存储引擎模式的索引类型。相对 Hash 索引，B+树在查找单条记录的速度比不上 Hash 索引，但是更适合排序等操作。

1. B+Tree 索引的优点：

带顺序访问指针的 B+Tree：B+Tree 所有索引数据都在叶子结点上，并且增加了顺序访问指针,每个叶子节点都有指向相邻叶子节点的指针。这样做是为了提高区间查询效率，例如查询 key 为从 18 到 49 的所有数据记录，当找到 18 后，只需顺着节点和指针顺序遍历就可以一次性访问到所有数据节点，极大提到了区间查询效率。
大大减少磁盘 I/O 读取次数。

三、MySQL索引的实现

在 MySQL 中，索引属于存储引擎级别的概念，不同存储引擎对索引的实现方式是不同的，本部分主要讨论 MyISAM 和 InnoDB 两个存储引擎的索引实现方式。

MyISAM 索引的实现

1. 主键索引

MyISAM 引擎使用 B+Tree 作为索引结构，叶节点的 data 域存放的是数据记录的地址。下图是 MyISAM 索引的原理图：

这里设表一共有三列，假设我们以 Col1 为主键，则上图是一个 MyISAM 表的主索引（Primary key）示意。可以看出 MyISAM 的索引文件仅仅保存数据记录的地址。

2. 辅助索引

在MyISAM中，主索引和辅助索引（Secondary key）在结构上没有任何区别，只是主索引要求 key 是唯一的，而辅助索引的 key 可以重复。如果我们在 Col2 上建立一个辅助索引，则此索引的结构如下图所示：

同样也是一颗 B+Tree，data 域保存数据记录的地址。因此，MyISAM 中索引检索的算法为首先按照 B+Tree 搜索算法搜索索引，如果指定的 Key 存在，则取出其 data 域的值，然后以 data 域的值为地址，读取相应数据记录。
MyISAM 的索引方式也叫做“非聚集”的，之所以这么称呼是为了与 InnoDB 的聚集索引区分。

InnoDB 索引的实现

虽然 InnoDB 也使用 B+Tree 作为索引结构，但具体实现方式却不相同。

1. 主键索引

与 MyISAM 第一个重大区别是 InnoDB 的数据文件本身就是索引文件。从上文知道，MyISAM 索引文件和数据文件是分离的，索引文件仅保存数据记录的地址。而在 InnoDB 中，表数据文件本身就是按 B+Tree 组织的一个索引结构，这棵树的叶节点 data 域保存了完整的数据记录。这个索引的 key 是数据表的主键，因此 InnoDB 表数据文件本身就是主索引。

上图是 InnoDB 主索引（同时也是数据文件）的示意图，可以看到叶节点包含了完整的数据记录。这种索引叫做聚集索引。因为 InnoDB 的数据文件本身要按主键聚集，所以 InnoDB 要求表必须有主键（MyISAM 可以没有），如果没有显式指定，则 MySQL 系统会自动选择一个可以唯一标识数据记录的列作为主键，如果不存在这种列，则 MySQL 自动为 InnoDB 表生成一个隐含字段作为主键，这个字段长度为 6 个字节，类型为长整形。

2. 辅助索引

第二个与 MyISAM 索引的不同是 InnoDB 的辅助索引 data 域存储相应记录主键的值而不是地址。换句话说，InnoDB 的所有辅助索引都引用主键作为 data 域。例如，下图为定义在 Col3 上的一个辅助索引：

这里以英文字符的 ASCII 码作为比较准则。聚集索引这种实现方式使得按主键的搜索十分高效，但是辅助索引搜索需要检索两遍索引：首先检索辅助索引获得主键，然后用主键到主索引中检索获得记录。
InnoDB 表是基于聚簇索引建立的。因此 InnoDB 的索引能提供一种非常快速的主键查找性能。不过，它的辅助索引也会包含主键列，所以，如果主键使用过长的字段，将会导致其他辅助索变得更大。如果想在表上定义、很多索引，则争取尽量把主键定义得小一些。InnoDB 不会压缩索引。

MySQL优化之索引（index）