索引是一种数据结构,可以帮助我们快速的进行数据的查找。

索引的分类

从存储结构上来划分

• BTree索引（B-Tree或B+Tree索引）
• Hash索引
• full-test全文索引
• R-Tree索引

从应用层次来分

• 普通索引：即一个索引只包含单个列，一个表可以有多个单列索引
• 唯一索引：索引列的值必须唯一，但允许有空值
• 复合索引：即一个索引包含多个列

根据中数据的物理顺序与键值的逻辑（索引）顺序关系

• 聚集索引：表数据按照索引的顺序来存储的，也就是说索引项的顺序与表中记录的物理顺序一致。对于聚集索引，叶子结点即存储了真实的数据行，不再有另外单独的数据页。 在一张表上最多只能创建一个聚集索引，因为真实数据的物理顺序只能有一种。

• 非聚集索引：表数据存储顺序与索引顺序无关。对于非聚集索引，叶结点包含索引字段值及指向数据页数据行的逻辑指针，其行数量与数据表行数据量一致。

索引的数据结构和具体存储引擎的实现有关, 在MySQL中使用较多的索引有Hash索引,B+树索引等,而我们经常使用的InnoDB存储引擎的默认索引实现为:B+树索引。

Hash索引

基于哈希表实现，只有精确匹配索引所有列的查询才有效，对于每一行数据，存储引擎都会对所有的索引列计算一个哈希码（hash code），并且Hash索引将所有的哈希码存储在索引中，同时在索引表中保存指向每个数据行的指针。

在MySQL中，只有 Memory 引擎显式支持哈希索引。这也是 Memory 引擎表的默认索引。

Hash索引的特点：

• hash索引是基于hash表实现的，只有查询条件精确匹配hash索引中的所有列的时候，才能用到hash索引。
• 对于hash索引中的所有列，存储引擎都会为每一行计算一个hash码，hash索引中存储的就是hash码。
• hash索引包括键值、hash码和指针。

Hash索引的限制

因为hash索引本身只需要存储对应的hash值，所以索引的结构十分紧凑，这也让hash索引查找的速度非常快。然而，hash索引也是存在其限制的。

• Hash索引必须进行二次查找: 使用哈市索引两次查找，第一次找到相应的行，第二次读取数据，但是被频繁访问到的行一般会缓存在内存中，这点对数据库性能的影响不大。
• Hash索引不能用于外排序：hash索引存储的是hash码而不是键值，所以无法用于外排序
• Hash索引不支持部分索引查找也不支持范围查找，只能用到等值查询，不能范围和模糊查询
• Hash索引中的hash码的计算可能存在hash冲突：当出现hash冲突的时候，存储引擎必须遍历整个链表中的所有行指针，逐行比较，直到找到所有的符合条件的行，若hash冲突很多的话，一些索引的维护代价机会很高，所以说hash索引不适用于选择性很差的列上（重复值很多）。

B+树索引

B+树底层实现是多路平衡查找树.对于每一次的查询都是从根节点出发,查找到叶子节点方可以获得所查键值,然后根据查询判断是否需要回表查询数据。

B+索引有几个关键特征：

• 在叶子节点一层，所有记录的主键按照从小到大的顺序排列，并且形成了一个双向链表。叶子节点的每一个Key指向一条记录。
• 非叶子节点取的是叶子节点里面Key的最小值。这意味着所有非叶子节点的Key都是冗余的叶子节点。同一层的非叶子节点也互相串联，形成了一个双向链表。

在MyISAM引擎中的实现

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

在InnoDB中的实现

MyISAM索引文件和数据文件是分离的，索引文件仅保存数据记录的地址。而在InnoDB中，表数据文件本身就是按B+Tree组织的一个索引结构，这棵树的叶节点data域保存了完整的数据记录。

基于这样一个数据结构，要实现下面的几个特性就很容易了：

• 范围查询：比如要查主键在[1,17]之间的记录。二次查询，先查找1所在的叶子节点的记录位置，再查找17所在的叶子节点记录的位置（就是16所处的位置），然后顺序地从1遍历链表直到16所在的位置。
• 前缀匹配模糊查询：假设主键是一个字符串类型，要查询where Key like abc%，其实可以转化成一个范围查询Key in [abc,abcz]。当然，如果是后缀匹配模糊查询，或者诸如where Key like %abc%这样的中间匹配，则没有办法转化成范围查询，只能挨个遍历。
• 排序与分页：叶子节点天然是排序好的，支持排序和分页。

另外，基于B+树的特性，会发现对于offset这种特性，其实是用不到索引的。比如每页显示10条数据，要展示第101页，通常会写成select xxx where xxx limit 1000, 10，从offset =1000的位置开始取10条。

虽然只取了10条数据，但实际上数据库要把前面的1000条数据都遍历才能知道offset = 1000的位置在哪。对于这种情况，合理的办法是不要用offset，而是把offset = 1000的位置换算成某个max_id，然后用where语句实现，就变成了select xxx where xxx and id> max_id limit 10，这样就可以利用B+树的特性，快速定位到max_id所在的位置，即是offset=1000所在的位置。

常见问题

为什么建议自增长主键作为索引

结合B+Tree的特点，自增主键是连续的，在插入过程中尽量减少页分裂，即使要进行页分裂，也只会分裂很少一部分。并且能减少数据的移动，每次插入都是插入到最后。总之就是减少分裂和移动的频率。

插入连续的数据：

插入非连续的数据

最左前缀原则

例如对于下面这个表:

如果我们按照 name 字段来建立索引的话，采用B+树的结构，大概的索引结构如下:

如果我们要进行模糊查找，查找name 以“张"开头的所有人的ID，即 sql 语句为：

select `ID ` from `table` where `name` like '张%';

由于在B+树结构的索引中，索引项是按照索引定义里面出现的字段顺序排序的，索引在查找的时候，可以快速定位到 ID 为 100的张一，然后直接向右遍历所有张开头的人，直到条件不满足为止。

也就是说，我们找到第一个满足条件的人之后，直接向右遍历就可以了，由于索引是有序的，所有满足条件的人都会聚集在一起。

而这种定位到最左边，然后向右遍历寻找，就是我们所说的最左前缀原则。

主键索引和非主键索引

对于下面这个表,ID是主键,K为非主键索引:

主键索引和非主键索引的示意图如下：

其中R代表一整行的值。

从图中不难看出，主键索引和非主键索引的区别是：非主键索引的叶子节点存放的是主键的值，而主键索引的叶子节点存放的是整行数据，其中非主键索引也被称为二级索引，而主键索引也被称为聚簇索引。

根据这两种结构我们来进行下查询，看看他们在查询上有什么区别。

1、如果查询语句是 select * from table where ID = 100,即主键查询的方式，则只需要搜索 ID 这棵 B+树。

2、如果查询语句是 select * from table where k = 1，即非主键的查询方式，则先搜索k索引树，得到ID=100,再到ID索引树搜索一次，这个过程也被称为回表。