Mysql索引

索引的本质

MySQL官方对索引的定义为：索引（Index）是帮助MySQL高效获取数据的数据结构。提取句子主干，就可以得到索引的本质：索引是数据结构。

我们知道，数据库查询是数据库的最主要功能之一。我们都希望查询数据的速度能尽可能的快，因此数据库系统的设计者会从查询算法的角度进行优化。最基本的查询算法当然是顺序查找（linear search），这种复杂度为O(n)的算法在数据量很大时显然是糟糕的，好在计算机科学的发展提供了很多更优秀的查找算法，例如二分查找（binary search）、二叉树查找（binary tree search）等。如果稍微分析一下会发现，每种查找算法都只能应用于特定的数据结构之上，例如二分查找要求被检索数据有序，而二叉树查找只能应用于二叉查找树上，但是数据本身的组织结构不可能完全满足各种数据结构（例如，理论上不可能同时将两列都按顺序进行组织），所以，在数据之外，数据库系统还维护着满足特定查找算法的数据结构，这些数据结构以某种方式引用（指向）数据，这样就可以在这些数据结构上实现高级查找算法。这种数据结构，就是索引。

举个例子

上图展示了一种可能的索引方式。左边是数据表，一共有两列七条记录，最左边的是数据记录的物理地址（注意逻辑上相邻的记录在磁盘上也并不是一定物理相邻的）。为了加快Col2的查找，可以维护一个右边所示的二叉查找树，每个节点分别包含索引键值和一个指向对应数据记录物理地址的指针，这样就可以运用二叉查找在(O(log_2n))的复杂度内获取到相应数据。

虽然这是一个货真价实的索引，但是实际的数据库系统几乎没有使用二叉查找树或其进化品种红黑树（red-black tree）实现的，原因会在下文介绍。

Mysql存储引擎

Mysql存储引擎有多种，比如Memory等，此处主要讲解MyISAM和InnoDB

• MyISAM
  它不支持事务，也不支持外键，尤其是访问速度快，对事务完整性没有要求或者以SELECT、INSERT为主的应用基本都可以使用这个引擎来创建表。
• InnoDB
  InnoDB存储引擎提供了具有提交、回滚和崩溃恢复能力的事务安全。但是对比MyISAM的存储引擎，InnoDB写的处理效率差一些并且会占用更多的磁盘空间以保留数据和索引。
• MyISAM是非事务安全型的，而InnoDB是事务安全型的。
• MyISAM锁的粒度是表级，而InnoDB支持行级锁定。
• MyISAM支持全文类型索引，而InnoDB不支持全文索引。
• MyISAM相对简单，所以在效率上要优于InnoDB，小型应用可以考虑使用MyISAM。
• MyISAM表是保存成文件的形式，在跨平台的数据转移中使用MyISAM存储会省去不少的麻烦。
• InnoDB表比MyISAM表更安全，可以在保证数据不会丢失的情况下，切换非事务表到事务表（alter table tablename type=innodb）。

Mysql索引

数据结构

二叉树

• 非叶子节点只能允许最多两个子节点存在。

• 每一个非叶子节点数据分布规则为左边的子节点小当前节点的值，右边的子节点大于当前节点的值；即二叉查找树的特点就是任何节点的左子节点的键值都小于当前节点的键值，右子节点的键值都大于当前节点的键值。

平衡二叉树

• 在满足二叉查找树特性的基础上，如不是空树，任何一个结点的左子树与右子树都是平衡二叉树，并且高度之差的绝对值不超过 1。

B-Tree

为了描述B-Tree，首先定义一条数据记录为一个二元组[key, data]，key为记录的键值，对于不同数据记录，key是互不相同的；data为数据记录除key外的数据。那么B-Tree是满足下列条件的数据结构：

• d为大于1的一个正整数，称为B-Tree的度。
• h为一个正整数，称为B-Tree的高度。
• 每个非叶子节点由n-1个key和n个指针组成，其中d<=n<=2d。
• 每个叶子节点最少包含一个key和两个指针，最多包含2d-1个key和2d个指针，叶节点的指针均为null 。
• 所有叶节点具有相同的深度，等于树高h。
• key和指针互相间隔，节点两端是指针。
• 一个节点中的key从左到右非递减排列。
• 所有节点组成树结构。
• 每个指针要么为null，要么指向另外一个节点。
• 如果某个指针在节点node最左边且不为null，则其指向节点的所有key小于(v(key_1))，其中(v(key_1))为node的第一个key的值。
• 如果某个指针在节点node最右边且不为null，则其指向节点的所有key大于(v(key_m))，其中(v(key_m))为node的最后一个key的值。
• 如果某个指针在节点node的左右相邻key分别是(key*i)和(key*{i+1})且不为null，则其指向节点的所有key小于(v(key_{i+1}))且大于(v(key_i))。

B+Tree

B-Tree有许多变种，其中最常见的是B+Tree，例如MySQL就普遍使用B+Tree实现其索引结构。

与B-Tree相比，B+Tree有以下不同点：

• 内节点不存储data，存储key和指针。
• 叶子节点不存储指针，存储key和data。

下图是一个简单的B+Tree示意。

由于并不是所有节点都具有相同的域，因此B+Tree中叶节点和内节点一般大小不同。这点与B-Tree不同，虽然B-Tree中不同节点存放的key和指针可能数量不一致，但是每个节点的域和上限是一致的，所以在实现中B-Tree往往对每个节点申请同等大小的空间。

一般来说，B+Tree比B-Tree更适合实现外存储索引结构，具体原因与外存储器原理及计算机存取原理有关，将在下面讨论。

B+Tree（顺序访问指针）

一般在数据库系统或文件系统中使用的B+Tree结构都在经典B+Tree的基础上进行了优化，增加了顺序访问指针。

如上图所示，在B+Tree的每个叶子节点增加一个指向相邻叶子节点的指针，就形成了带有顺序访问指针的B+Tree。做这个优化的目的是为了提高区间访问的性能，例如图4中如果要查询key为从18到49的所有数据记录，当找到18后，只需顺着节点和指针顺序遍历就可以一次性访问到所有数据节点，极大提到了区间查询效率。

索引的物理存储

与B-Tree相比，B+Tree有以下不同点：

• 非叶子结点的子树指针与关键字个数相同；
• 非叶子结点的子树指针P[i]，指向关键字值属于[K[i], K[i+1])的子树（B-树是开区间）；
• 为所有叶子结点增加一个链指针；
• 所有关键字都在叶子结点出现；
• 内节点不存储data，只存储key

为什么B+Tree更适合做文件索引

因为B+ Tree的内部节点并没有指向关键字具体信息的指针，所以他的内部节点比其他结构的更小，同样大小的盘块能够容纳更多的单位索引结构，一次性读入内存的 关键字信息索引就更多，相对来说IO读写次数也就少很多。

两种引擎的索引存储机制

下面就让我们从索引结构的角度来分析一下两种引擎的索引存储机制

MyISAM索引实现

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

上图是MyISAM表主索引的示意，我们可以看到仅仅MyISAM的索引文件仅仅保存数据记录的地址，在MyISAM中，主索引和辅助索引（Secondary key）在结构上没有任何区别，只是主索引要求key是唯一的，而辅助索引的key可以重复。

因此，MyISAM中索引检索的算法为首先按照B+Tree搜索算法搜索索引，如果指定的Key存在，则取出其data域的值，然后以data域的值为地址，读取相应数据记录。

MyISAM的索引方式也叫做“非聚集”的。

InnoDB索引实现

都是采用的B+ Tree作为的索引结构，但具体实现方式大相径庭。

• InnoDB的数据文件本身就是索引文件。从上文知道，MyISAM索引文件和数据文件是分离的，索引文件仅保存数据记录的地址。而在InnoDB中，表数据文件本身就是按B+Tree组织的一个索引结构，这棵树的叶节点data域保存了完整的数据记录。这个索引的key是数据表的主键，因此InnoDB表数据文件本身就是主索引。
  上图是InnoDB主索引（同时也是数据文件）的示意图，可以看到叶节点包含了完整的数据记录。这种索引叫做聚集索引。因为InnoDB的数据文件本身要按主键聚集，所以InnoDB要求表必须有主键（MyISAM可以没有)，如果没有显式指定，则MySQL系统会自动选择一个可以唯一标识数据记录的列作为主键，如果不存在这种列，则MySQL自动为InnoDB表生成一个隐含字段作为主键，这个字段长度为6个字节，类型为长整形。

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

拓展

了解完MySQL索引结构，以及两种引擎分别的实现方式，能够帮助我们理解很多事情。譬如：

• InnoDB不建议使用过长的字段作为主键，因为所有辅助索引都引用主索引，过长的主索引会令辅助索引变得过大
• 用非单调的字段作为主键在InnoDB中不是个好主意，因为InnoDB数据文件本身是一颗B+Tree，非单调的主键会造成在插入新记录时数据文件为了维持B+Tree的特性而频繁的分裂调整，十分低效，而使用自增字段作为主键则是一个很好的选择
• 我们在innodb中如果涉及到事务并发，请一定要遵从按照统一的加锁顺序，且要避免在不同的事务给主键索引和辅助索引分别加锁，这是一个十分隐蔽的死锁案例，将来会仔细讲。
• 对锁的概念以及应用可能会更加深刻，譬如为什么行锁只可能作用在加了索引的字段上，如果你有兴趣，请继续学下去。

索引补充

索引类型

用于提高读写效率的数据结构有很多，这里先介绍常见的3种

哈希索引

哈希表是一种以键-值（key-value）的方式存储数据的结构，我们只要输入待查找的值（即key），就可以找到其对应的值（即Value）。哈希的思路很简单，把值放在数组里，用一个哈希函数把key换算成一个确定的位置，然后把value放在数组的这个位置，即idx = Hash(key)。如果出现哈希冲突，就采用拉链法解决。

因为哈希表中存放的数据不是有序的，因此不适合做区间查询，适用于只有等值查询的场景。

有序数组

有序数组在等值查询和范围查询场景中的性能都非常优秀。用二分法就可以快速找到（时间复杂度为O(logN)）。但是如果要往中间插入一条数据，则必须挪动后面的所有记录，成本较高。因此，有序数组只适用于静态存储引擎，即数据表一旦建立后不再会修改。

B+树索引（INNODB）

在 InnoDB 中，表都是根据主键顺序以索引的形式存放的，这种存储方式的表称为索引组织表。又因为前面我们提到的，InnoDB 使用了 B+ 树索引模型，所以数据都是存储在 B+ 树中的。每一个索引在 InnoDB 里面对应一棵 B+ 树。

假设，有这样一张表：该表主键为ID，且还有一个字段为k，并在k上有索引。

    CREATE TABLE T(
        id int primary key,
        k int not null,
        index (k)
    )engine=InnoDB;

表中有5条记录，分别为R1~R5，(100,1)、(200,2)、(300,3)、(500,5)和(600,6)。则在InnoDB中的索引组织结构是这样的：

根据叶子结点的内容，索引类型分为主键索引和非主键索引。

• 主键索引的叶子结点存的是整条记录，主键索引也被称为聚簇索引（clustered index）
• 非主键索引的叶子结点存的是主键的值，非主键索引也被称为二级索引（secondary index）/普通索引/辅助索引。

那么，基于主键索引和非主键索引的查询有什么区别？

• 如果语句是 select * from T where ID=500，即主键查询，则只需要搜索ID这棵树。
• 如果语句是 select *from T where k=5，即非主键索引查询，则需要先搜索k索引树，得到ID的值为500，再到ID索引树搜索一次。从非主键索引回到主键索引的过程称为回表。

也就是说，基于非主键索引的查询需要多扫描一棵索引树。因此，我们在应用中应该尽量使用主键查询。而从存储空间的角度讲，因为非主键索引树的叶结点存放的是主键的值，那么，应该考虑让主键的字段尽量短，这样非主键索引的叶子结点就越小，非主键索引占用的空间也就越小。一般情况下，建议创建一个自增主键，这样非主键索引占用的空间最小。

联合索引

联合索引是指对表上的多个列进行索引。下面以一个例子进行说明。假设有下面这样一张表，有这样一个需求，我们需要查询某个用户的购物情况，并按照时间进行排序，取出某用户近几次的购物情况。

    // 表
    CREATE TABLE buylog(
        userid int not null,
        buy_date DATE
    )ENGINE=InnoDB;
    // 插入数据
    insert into buylog values(1, '2019-08-13');
    insert into buylog values(2, '2019-08-14');
    insert into buylog values(3, '2019-08-15');
    insert into buylog values(1, '2019-08-11');
    insert into buylog values(3, '2019-08-10');
    insert into buylog values(1, '2019-08-12');
    // 添加索引
    alter table buylog add index(userid);
    alter table buylog add index(userid, buy_date);
    // （或用key关键字也一样的）
    alter table buylog add key(userid);
    alter table buylog add key(userid, buy_date);

上面的代码建立了两个索引，两个索引都包含了userid字段。

如果只对于userid进行查询，如：

select * from buylog where userid=2;

通过explain查看该语句的执行情况，如下，（explain显示了mysql如何使用索引来处理select语句以及连接表。可以帮助选择更好的索引和写出更优化的查询语句。）

可以看到，possible_keys在这里有两个索引可供使用，分别是userid索引和(userid,buy_date)联合索引。优化器最终选择的索引（即key）是userid，因为该索引的叶子节点只包含单个键值，所以理论上一页能存放的记录会更多（意味着可以减少查询的次数）。

接着假定要查询userid为1的最近两次的购买记录，如：

select * from buylog where userid=1 order by buy_date desc limit 2;

同样的，我们看一下它的执行过程是怎样的，如下：

可以看到，这一次查询优化器选择的索引是userid_2（也就是(userid, buy_date)联合索引）。为什么呢？因为在这个联合索引中，记录已经分别根据userid和buy_date排好序了，利用这个索引则可以直接取出相应的数据而无需再对buy_date额外做一次排序操作了。如果强制使用userid索引，则它的执行计划如下：

从Extra字段可以看出，该语句的执行需要使用fliesort，也就是需要一次额外的排序操作才能完成查询。显然，这个排序就是对buy_date字段的排序，因为这里仅使用了userid索引，该索引未对buy_date进行排序。

总结：

联合索引(a, b)是根据a, b进行排序（先根据a排序，如果a相同则根据b排序）。因此，下列语句可以直接使用联合索引得到结果（事实上，也就是用到了最左前缀原则）：

select ... from xxx where a=xxx; 
select ... from xxx where a=xxx order by b;

而下列语句则不能使用联合查询：

select ... from xxx where b=xxx;

对于联合索引(a, b, c)，下列语句同样可以直接通过联合索引得到结果：

select ... from xxx where a=xxx order by b;select ... from xxx where a=xxx and b=xxx order by c;

而下列语句则不行，需要执行一次filesort排序操作。

select ... from xxx where a=xxx order by c;

最左前缀原则

最左前缀匹配原则指的是，在使用联合索引时，MySQL 会根据联合索引中的字段顺序，从左到右依次到查询条件中去匹配，如果查询条件中存在与联合索引中最左侧字段相匹配的字段，则就会使用该字段过滤一批数据，直至联合索引中全部字段匹配完成，或者在执行过程中遇到范围查询，如 >、<、between 和 以%开头的like查询 等条件，才会停止匹配。

查询的时候如果使用多条件，SQL执行引擎会自动优化为匹配联合索引的顺序

对于有很多字段的一张表，查询的方式是多样的，难道要为了每一种可能的查询都定义索引吗？这样岂不是很浪费空间，毕竟建索引也是需要一些空间的。事实上，B+ 树这种索引结构，可以利用索引的“最左前缀”原则来定位记录，避免重复定义索引。

以下面的例子进行说明什么是“最左前缀原则”。

假设建立了一个联合索引(name,age)，可以看到，索引项是按照索引定义里面出现的字段顺序排序的，先根据名字排序，名字相同的就根据年龄排序。

当你的逻辑需求是查到所有名字是“张三”的人时，可以快速定位到 ID4，然后向后遍历得到所有需要的结果。

如果你要查的是所有名字第一个字是“张”的人，你的 SQL 语句的条件是”where name like ‘张%’”。这时，你也能够用上这个索引，查找到第一个符合条件的记录是 ID3，然后向后遍历，直到不满足条件为止。

可以看到，不只是索引的全部定义，只要满足最左前缀，就可以利用索引来加速检索。这个最左前缀可以是联合索引的最左 N 个字段，也可以是字符串索引的最左 M 个字符。

因此，基于最左前缀原则，我们在定义联合索引的时候，考虑如何安排索引内的字段顺序就至关重要了！评估的标准就是索引的复用能力，比如，当已经有了(a,b)字段的索引，一般就不需要再单独在a上建立索引了。

覆盖索引

如果一个索引包含（或者说覆盖）所有需要查询的字段的值，我们就称之为“覆盖索引”。我们知道在 InnoDB 存储引擎中，如果不是主键索引，叶子节点存储的是主键+列值。最终还是要“回表”，也就是要通过主键再查找一次。这样就会比较慢覆盖索引就是把要查询出的列和索引是对应的，不做回表操作！

覆盖索引即需要查询的字段正好是索引的字段，那么直接根据该索引，就可以查到数据了，而无需回表查询。

还是利用“B+树索引”提到过的表，如果执行的语句是：

select * from T where k between 3 and 5;

则这条SQL语句的执行流程如下：

1. 在 k 索引树上找到 k=3 的记录，取得 ID = 300；
2. 再到 ID 索引树查到 ID=300 对应的 R3；
3. 在 k 索引树取下一个值 k=5，取得 ID=500；
4. 再回到 ID 索引树查到 ID=500 对应的 R4；
5. 在 k 索引树取下一个值k=6，不满足条件，循环结束。
   在这个过程中，回到主键索引树的过程，称为回表。在这个例子中，由于查询的结果是所有字段，所需要的数据只有主键上才有，所以不得不回表。但如果执行的语句是下面这样的，注意！这里查询的结果只是“ID”（恰好是主键），而不是所有字段了。

select ID from T where k between 3 and 5;

由于查询的值是ID，而ID的值已经在k索引树上了，因此可以直接提供查询结果，不需要回表。也就是说，在这个查询里，索引k已经“覆盖了”我们的查询需求，故称为覆盖索引。

除了上面这种情况，针对某些统计问题时，覆盖索引也能发挥用处。还是以上面的例子，执行如下语句来统计表的记录总数（在此我们假设这张表数据量特别特别大，需要多次磁盘IO）：

select count(*) from T;

如果没有对字段k设置索引，那么只能是通过聚簇索引来计算；如果对字段k设置了索引，那么，由于聚簇索引的叶结点存放的是整行记录的所有信息，而辅助索引的叶结点只存放主键，两者相比，对于一页内存，显然辅助索引能够存放的节点更多，意味着辅助索引可以减少IO次数，从而更快的计算出count(*)的值。

验证如下：

没有对字段k设置索引时，优化器会选择聚簇索引进行操作（即key为PRIMARY）。

对字段k设置了索引时，优化器会选择辅助索引进行操作（即key为k）

可见，如果建立了辅助索引，在有些场景下，优化器会自动使用辅助索引从而提升查询效率。

总结：覆盖索引就是从辅助索引中就能直接得到查询结果，而不需要回表到聚簇索引中进行再次查询，所以可以减少搜索次数（不需要从辅助索引树回表到聚簇索引树），或者说减少IO操作（通过辅助索引树可以一次性从磁盘载入更多节点），从而提升性能。

索引下推

索引下推是 MySQL 5.6 版本中提供的一项索引优化功能，可以在非聚簇索引遍历过程中，对索引中包含的字段先做判断，过滤掉不符合条件的记录，减少回表次数。

什么是索引下推（Index Condition Pushdown，ICP）呢？假设有这么个需求，查询表中“名字第一个字是张，性别男，年龄为10岁的所有记录”。那么，查询语句是这么写的：

select * from tuser where name like '张 %' and age=10 and ismale=1;

根据前面说的“最左前缀原则”，该语句在搜索索引树的时候，只能匹配到名字第一个字是‘张’的记录（即记录ID3），接下来是怎么处理的呢？当然就是从ID3开始，逐个回表，到主键索引上找出相应的记录，再比对age和ismale这两个字段的值是否符合。

但是MySQL 5.6引入了索引下推优化，可以在索引遍历过程中，对索引中包含的字段先做判断，过滤掉不符合条件的记录，减少回表字数。

下面图1、图2分别展示这两种情况。

（图1）

（图2）
图 1 中，在 (name,age) 索引里面我特意去掉了 age 的值，这个过程 InnoDB 并不会去看 age 的值，只是按顺序把“name 第一个字是’张’”的记录一条条取出来回表。因此，需要回表 4 次。

图 2 跟图 1 的区别是，InnoDB 在 (name,age) 索引内部就判断了 age 是否等于 10，对于不等于 10 的记录，直接判断并跳过。在我们的这个例子中，只需要对 ID4、ID5 这两条记录回表取数据判断，就只需要回表 2 次。

总结：如果没有索引下推优化（或称ICP优化），当进行索引查询时，首先根据索引来查找记录，然后再根据where条件来过滤记录；在支持ICP优化后，MySQL会在取出索引的同时，判断是否可以进行where条件过滤，也就是说提前执行where的部分过滤操作，在某些场景下，可以大大减少回表次数，从而提升整体性能。

索引名称

• 聚集索引
  • 主键索引(innodb)
• 非聚集索引
  • 主键索引(myisam)
  • 二级索引/辅助索引(innodb)
  • 二级索引/辅助索引(myisam)