什么是索引？

索引是辅助存储引擎高效获取数据的一种数据结构。
MySQL索引 - 图1
很多人形象的说索引就是数据的目录，便于存储引擎快速的定位数据。

索引的分类

从数据结构的角度对索引进行分类：

  • B+tree（多路平衡查找树）
  • Hash
  • Full-texts索引

从物理存储的角度对索引进行分类：

  • 聚簇索引
  • 二级索引（辅助索引）

从索引字段特性角度分类：

  • 主键索引
  • 唯一索引
  • 普通索引
  • 前缀索引

从组成索引的字段个数角度分类：

  • 单列索引
  • 联合索引（复合索引）

    数据结构角度看索引

    下表是MySQL常见的存储引擎InnoDB，MyISAM和Memory分别支持的索引类型：

 InnoDB MyISAM Memory
B+tree索引 Yes Yes Yes
Hash索引 No No Yes
Full-text索引 Yes Yes No

在实际使用中，InnoDB作为MySQL建表时默认的存储引擎。对上表进行横向查看可以了解到，B+tree是MySQL中被存储引擎采用最多的索引类型。
这里浅尝辄止的谈一下B+tree 与 Hash和红黑树的区别。

B+tree和B-tree

1970年，R.Bayer和E.Mccreight提出了一种适用于外查找的平衡多叉树——B-树，磁盘管理系统中的目录管理，以及数据库系统中的索引组织多数采用B-Tree这种数据结构。
B+tree是B-Tree的一个变种。（哦，对了，B-tree念B树，它不叫B减树。。。）
MySQL索引 - 图2

  1. B+tree只在叶子节点存储数据，而B-tree非叶子节点也存储数据。
  2. 因此，B+tree单个节点的数量更小，在相同的磁盘IO下能查询更多的节点。
  3. 另外B+tree叶子节点采用单链表链接，键值按顺序排列，适合MySQL中常见的基于范围的顺序检索场景，而B-tree无法做到这一点。（MySQL数据库中innodb引擎索引的B+Tree的叶子节点是双向链表连接）

    B+tree和红黑树

    MySQL索引 - 图3
    对于有N个叶子节点的B+tree，搜索复杂度为O(logdN)，d是指degree是指B+tree的度，表示节点允许的最大子节点个数为d个，在实际的运用中d值是大于100的，即使数据达到千万级别时候B+tree的高度依然维持在3-4左右，保证了3-4次磁盘I/O就能查到目标数据。
    MySQL索引 - 图4
    从上图中可以看出红黑树是二叉树，节点的子节点个数最多为2个，意味着其搜索复杂度为O(logN)，比B+树高出不少，因此红黑树检索到目标数据所需经理的磁盘I/O次数更多。

    B+tree索引与Hash表

    范围查询是MySQL数据库中常见的场景，而Hash表不适合做范围查询，Hash表更适合做等值查询，另外Hash表还存在Hash函数选择和Hash值冲突等问题。
    因为这些原因，B+tree索引要比Hash表索引有更广的适用场景。

    物理存储角度看索引

    MySQL中的两种常用存储引擎对索引的处理方式差别较大。

    InnoDB的索引

    首先看一下InnoDB存储引擎中的索引，InnoDB表的索引按照叶子节点存储的是否为完整表数据分为聚簇[cù]索引和二级索引。
    MySQL索引 - 图5 全表数据就是存储在聚簇索引中的。聚簇索引以外的其它索引叫做二级索引。
    InnoDB表要求必须有聚簇索引，默认在主键字段上建立聚簇索引，在没有主键字段的情况下，表的第一个NOT NULL 的唯一索引将被建立为聚簇索引，在前两者都没有的情况下，InnoDB将自动生成一个隐式自增id列并在此列上创建聚簇索引。
    MySQL索引 - 图6
    从图中可以看到，聚簇索引的每个叶子节点存储了一行完整的表数据，叶子节点间采用单向链表按id列递增连接，可以方便的进行顺序检索。

接着来看二级索引。在name字段上添加二级索引index_name：
MySQL索引 - 图7
图中可以看出二级索引的叶子节点并不存储一行完整的表数据，而是存储了聚簇索引所在列的值，也就是表中的主键id的值。

说了聚簇索引和二级索引，肯定要提到回表查询。
由于二级索引的叶子节点不存储完整的表数据，所以当通过二级索引查询到聚簇索引的列值后，还需要回到聚簇索引也就是表数据本身进一步获取数据。
需要注意的是通过二级索引查询时，回表不是必须的过程，当Query的所有字段在二级索引中就能找到时，就不需要回表，MySQL称此时的二级索引为覆盖索引或称触发了索引覆盖。

  1. select id,name from workers where name='吕归尘';
  3. --这句sql只查询了id，和name,二级索引就已经包含了Query所以需要的所有字段，就无需回表查询。

MyISAM的索引

说完了InnoDB的索引，接下来看MyISAM的索引，以MyISAM存储引擎存储的表不存在聚簇索引。
MySQL索引 - 图8

MyISAM索引B+tree示意图

MyISAM表中的主键索引和非主键索引的结构是一样的，从上图中可以看到。他们的叶子节点是不存储表数据的，节点中存放的是表数据的地址，所以MyISAM表可以没有主键。
MyISAM表的数据和索引是分开的，是单独存放的。
MyISAM表中的主键索引和非主键索引的区别仅在于主键索引B+tree上的key必须符合主键的限制，
非主键索引B+tree上的key只要符合相应字段的特性就可以了。

索引字段特性角度看索引

主键索引

  • 建立在主键字段上的索引
  • 一张表最多只有一个主键索引
  • 索引列值不允许为null

  • 通常在创建表的时候一起创建

    唯一索引

  • 建立在UNIQUE字段上的索引就是唯一索引

  • 一张表可以有多个唯一索引，索引列值允许为null

    1. create table persons
    2. (
    3.    id   int(11) not null auto_increment comment '主键id',
    4.    eno  int(11) comment '工号',
    5.    eid  int(11) comment '身份证号',
    6.    veid int(11) comment '虚拟身份证号',
    7.    name varchar(16) comment '名字',
    8.    primary key (id) comment '主键索引',
    9.    UNIQUE key (eno) comment 'eno唯一索引',
    10.    UNIQUE key (eid) comment 'eid唯一索引'
    11. ) engine = InnoDB
    12.  auto_increment = 1000
    13.  default charset = utf8;
    15. alter table persons
    16.    add unique index index_veid (veid) comment 'veid唯一索引';

    通过show index from persons;命令可以看到已经成功创建了三个唯一索引。

    普通索引

    主键索引和唯一索引对字段的要求是要求字段为主键或unique字段，而那些建立在普通字段上的索引叫做普通索引，既不要求字段为主键也不要求字段为unique。

    前缀索引

    前缀索引是指对字符类型字段的前几个字符或对二进制类型字段的前几个bytes建立的索引，而不是在整个字段上建索引。
    例如，可以对persons表中的name(varchar(16))字段中name的前5个字符建立索引。

    1. create index index_name on persons (name(5)) comment '前缀索引';
    2. show index from persons;

    前缀索引可以建立在类型为

  • char

  • varchar
  • binary
  • varbinary

的列上，可以大大减少索引占用的存储空间，也能提升索引的查询效率。

索引列的个数角度看索引

  • 建立在单个列上的索引为单列索引
  • 建立在多列上的称为联合索引（复合索引）
    1. create index index_id_name on workers(id,name) comment '组合索引';
    这条语句在演示表workers中建立id，name这两个字段的联合索引。
    借助show index命令查看索引的详细信息 操作后结果如下：
    MySQL索引 - 图9
    虽然详细信息当中列出了两条关于联合索引的条目，但并不表示联合索引是建立了多个索引，联合索引是一个索引结构，这两个条目表示的是组合索引中字段的具体信息，按建立索引时的书写顺序排序。
    同样来看下联合索引的B+tree示意图：
    MySQL索引 - 图10
    从图中看到组合索引的非叶子节点保存了两个字段的值作为B+tree的key值，当B+tree上插入数据时，先按字段id比较，在id相同的情况下按name字段比较。

分析为什么B+树更适合做索引

我们可以先看看B+树在B树结构之上的改进，B+树在B树的基础之上最重要的改进就是非叶子结点只存储关键字和下一层的索引，不存储Data域，只在叶子结点存储Data域，且为所有叶子结点增加一个链指针，使所有叶结点构成一个有序链表，因此当我们需要有序遍历所有关键字时，直接从最小关键字的叶子结点开始遍历即可。
(注：Data域可以存放具体数据或者是数据的地址，区别在下面详述)
一、非叶子结点不存储Data域的好处：

  1. 非叶子结点不存储Data域，只是起着目录的作用，使得每一个非叶子结点可以存放更多的关键字和下一层结点的指针。数据库是存储在磁盘上的，我们读取数据是从磁盘读取到内存中，我们在进行磁盘预读取时，是以块(也可称作数据页)的单位进行数据读取，我们在检索B/B+树的结点时，每次以块为单位将一个结点读取到内存中，若一块磁盘包含了树结点以外的数据，就造成了浪费，因此我们需要使每一个结点的容量大小正好或者接近一块磁盘(数据页，一般是16k)的大小。于是我们在构建B+/B树时，树的阶数其实就取决于一块磁盘中能容纳多少个关键字以及相关的索引和Data域。B+树的非叶子结点不存储Data域，因此它可以存储更多个关键字和下一层结点的指针，因此B+树会比B树更矮胖。若我需要查找的关键字正好在叶子结点，因为B+树比B树更矮，B+树所进行的I/O次数更少，因为途中经过每一层，我们都需要进行一次I/O读取一个结点，B+树会更矮，途径的层数会更少。
  2. 使得B+树查询速度更稳定，B+树所有关键字数据地址都存在叶子节点上，所以每次查找的次数都相同所以查询速度要比B树更稳定。

二、所有叶结点构成一个有序链表的好处：

  1. B+树便于区间查找（这点才是B+树作为索引的关键），我们进行数据库查询大多为区间查询，B+树天然具备排序功能，B+树所有的叶子结点构成了一个有序链表，在查询大小区间的数据时候更方便，B+树查询，只需通过头结点往下找到第一个叶子结点，然后在叶子结点的链表上就行遍历即可完成区间查询。而且B+树叶子结点是以索引字段大小顺序进行排序的，索引字段大小相邻的数据位置也相邻，因此通过遍历叶子结点链表只需要进行少量I/O读取就能将所有数据都获取。而B树的索引字段大小相邻近的结点可能隔得很远，要想进行区间查询需要不停的进行中序遍历，相邻的元素可能在内存中不相邻，所以缓存命中性没有B+树好。
  2. B+树全结点遍历更快：B+树遍历整棵树只需要遍历所有的叶子节点即可，而不需要像B树一样需要进行中序遍历，这有利于数据库做全表扫描。

    索引下推

    索引下推就是只有符合条件再进行回表，对索引中包含的字段先进行判断，不符合条件的跳过。减少了不必要的回表操作。
    在使用索引下推的情况下，如果存在某些被索引的列有判断条件时，MySQL服务器将这一部分判断条件传递给存储引擎，然后由存储引擎通过判断索引是否符合MySQL服务器传递的条件，只有当索引符合条件时才会将数据检索出来返回给MySQL服务器 。

索引下推的下推其实就是指将部分上层（服务层）负责的事情，交给了下层（引擎层）去处理。
我们来具体看一下，在没有使用ICP（索引下推）的情况下，MySQL的查询：

  • 存储引擎读取索引记录；
  • 根据索引中的主键值，定位并读取完整的行记录；
  • 存储引擎把记录交给Server层去检测该记录是否满足WHERE条件。

使用ICP的情况下，查询过程：

  • 存储引擎读取索引记录（不是完整的行记录）；
  • 判断WHERE条件部分能否用索引中的列来做检查，条件不满足，则处理下一行索引记录；
  • 条件满足，使用索引中的主键去定位并读取完整的行记录（就是所谓的回表）；
  • 存储引擎把记录交给Server层，Server层检测该记录是否满足WHERE条件的其余部分。

    参考文档