索引是一种数据结构，如果没有索引，我们查询一条记录时可能要先遍历页组成的双向链表找到记录所在的数据页，再在该页中结合页目录通过二分查找记录（当以主键为搜索条件时是这样，如果以其他列作为搜索条件无法使用页目录，需要再遍历这个页里行格式组成的单向链表），这样做显然很低效，因此提出了索引的数据结构来加速我们的查询过程。一般在建表的时候我们会根据需要为表创建索引，InnoDB会自动为主键列或者UNIQUE列创建B+树索引，如果我们想在建表的时候为其他列建立索引，可以使用以下SQL语句：

  1. CREATE TALBE 表名 (
  2.     各种列的信息 ··· , 
  3.     [UNIQUE | FULLTEXT][KEY|INDEX] 索引名 (需要被索引的单个列或多个列)
  4. )

其中加上UNIQUE代表创建的是唯一索引，加上FULLTEXT代表创建的是全文索引。
举例，为表index_demo的列c2、c3建立联合索引：

  1. CREATE TABLE index_demo(
  2.     c1 INT,
  3.     c2 INT,
  4.     c3 CHAR(1),
  5.     PRIMARY KEY(c1),
  6.     INDEX idx_c2_c3 (c2, c3)
  7. );

说明：

  • 一般选择INDEX作为建立索引的语句；

  • 索引名一般用idx_列名的形式，这个是固定的，用_区分不同的列。

    1、InnoDB中的B+树索引方案

    回顾一下InnoDB存储引擎中，每一条记录在页中的存储方式。页是磁盘和内存交互的基本单位，每一条记录对应的行格式会按照主键值从小到大的顺序在页中组成一个单向链表，每个页（索引页）之间组成一个双向链表。每个索引页生产一个页目录，有了页目录，可以在根据主键值在页中查找记录时结合二分法迅速定位到该记录。页和记录的示意图如下：
    image.png
    这个是介绍后面索引形成过程的基础，不熟悉的可以再看看小册。

    1.1 B+树索引形成过程

    都知道InnoDB存储引擎默认的索引是B+树，这个B+树长什么样子呢？是怎么形成的呢？这是本节主要介绍的内容。
    （1）Compact行格式简化
    简化一下之前介绍的行格式，并令其竖直展示，如下：
    image.png
    （2）行格式在页中的存放
    把一些记录放到页里的示意图如下，其中橘黄色代表主键列，如下：
    image.png
    （3）目录项
    这个就是索引结构的前身，或者叫雏形，这里为了介绍B+数索引的形成流程，把这个结构也说明一下。
    目录项的数据结构定义如下：
    索引 - 图4
    目录项要遵守下面两条规则：

  • 下一个数据页中所有用户记录的主键值必须大于上一个页中所有用户记录的主键值；

  • 每一个数据页都对应一个页目录。

目录项和页的对应关系如下：
image.png
（4）目录项记录
目录项也是可以存储到数据页中的记录，把页里用来表示目录项的记录称为目录项记录，目录项记录和普通用户记录用以下两个区别：

  • 目录项记录的record_type值为1，而普通用户记录的record_type值为0；
  • 目录项记录只有两个列：主键值的列（以聚簇索引为例）和页编号的列，而普通用户记录可以有多个列和隐藏列。

将目录项记录也存储到数据页中，关系示意图如下：
image.png
说明：

  • 目录项记录也作为数据记录存放在页中，页中目录项记录同样按照主键值从小到大的顺序形成单链表，存放目录项记录的页互相形成双向链表；
  • 目录项记录一旦满了，也可以为目录项记录再生成一个目录项记录，有点递归套娃的意思。

（5）B+树索引的形成
随着表中的记录不断增多，存储目录项记录的页也不断增多，如何根据主键值快速定位到记录在哪个一个目录项记录对应的页里呢？那就再为这些存储目录项记录的页做一个目录，如果再多，就再建一层目录，示意图如下：
image.png
说明：

  • 无论是存放用户记录的数据页，还是存放目录项记录的数据页，这些页在B+树中都是一个节点；

  • 用户记录都存放到了B+树的叶子节点中（以聚簇索引为例，二级索引和联合索引只是部分列的数据存放在叶子节点中），非叶子节点存放目录项记录所在的数据页。

    1.2 B+树索引形成过程中注意的点

    1.2.1 页分裂

    一个页的大小是16kb，当页中装载的记录达到上限了该怎么办呢？答案是进行页分裂。页分裂是指：当一个数据页1中的记录达到页存储上限时，会重新生成一个数据页2，将数据页1中的记录和即将插入的记录重新按照主键值从小到大的顺序分配到数据页1和数据页2中，保证上一个数据页中的所有记录的主键值均小于下一个数据页中的记录的主键值。页分裂伴随着记录在两个数据页中的插入和移动，因此频繁的页分裂会影响MySQL性能。

    1.2.2 B+树的层级

    一般来讲一个B+树索引最多4层，如果数据量再多就该考虑分库分表了。
    规定B+树索引，最底下的那一次成为第0层，之后层的序号往上依次递增，现在介绍以下为什么上面说一个B+树索引一般最多4层。
    假设所有存放用户记录的叶子节点代表的数据页可以存放100条用户记录，所有存放目录项记录的非叶子节点代表的数据页可以存放1000条目录项记录，那么：

  • 如果B+树只有1层，只有1个用于存放用户记录的节点，最多能存放100条记录；

  • 如果B+树有2层，最多能存放1000×100=100000条记录；
  • 如果B+树有3层，最多能存放1000×1000×100=100000000条记录；
  • 如果B+树有4层，最多能存放1000×1000×1000×100=100000000000条记录，即1000亿。

上面假设条件中100和1000都是按小了估计的，实际数据页中可以存放更多的记录，在这种小估计下4层B+树都能存放1000亿条数据，更别说单表其实百万级别的数据就已经增删改查会很卡了，所以B+树索引足够了。

2、InnoDB中索引的分类

2.1 聚簇索引

2.1.1 什么是聚簇索引

我们把具有以下特点的B+树索引称为聚簇索引：

  • 使用记录主键值的大小进行记录和页的排序，这包括以下三个方面的含义：
    • 页内的记录是按照主键值从小到大的顺序排成一个单向链表；
    • 各个存放用户记录的页也是根据页中用户记录的主键大小顺序排成一个双向链表；
    • 存放目录项记录的页分为不同的层次，在同一层次中的页也是根据页中目录项记录的主键大小顺序排成一个双向链表。
  • B+树的叶子节点存储的是完整的用户记录
    所谓完整的用户记录，就是指这个记录中存储了所有列的值（包括隐藏列）。

聚簇索引并不需要我们在MySQL语句中显式的使用INDEX语句去创建，InnoDB存储引擎会自动的为我们创建聚簇索引。如果表中指定了主键列，会为主键列创建一个聚簇索引（主键索引），如果表中没有指定主键列，会选择表中第一个不为NULL的UNIQUE属性的列创建聚簇索引，如果还是没有的话， Innodb 存储引擎为每行数据内置的隐藏列 row_id 创建聚集索引。每张表只能有且一定有一个聚簇索引。另外，聚簇索引由于所有的用户记录都存储在了叶子节点（即B+树索引同时存储了索引和所有的用户记录），因此对聚簇索引来说，索引即数据，数据即索引。

2.2.2 如何根据聚簇索引查找记录

（1）确定该记录对应的目录项记录所在的页
根据主键值大小通过二分法查找，不管是数据页，还是目录项记录所在的页，页里面都是按照主键值从小到大的顺序排列目录项记录的，因此基于目录项记录里主键值大小通过二分法确定要查询的记录对应的目录项记录所在的页。
（2）基于目录项所在的页确定要查询的记录对应的目录项记录，进而确定要查询记录对应的数据页
依然是基于目录项记录所在的页中，目录项记录是按主键值从小到大的顺序串联成单链表的，通过二分法查找主键值对应的具体目录项记录，有了目录项记录就有了对应的数据页的编号，就找到了B+树叶子结点的具体数据页是哪个，注意目录项记录里主键值大小是该目录项记录对应的数据页里用户记录的主键值的最小值。
（3）在数据页中查找对应的用户记录
依然是基于二分法找到主键值对应的页目录中的槽，根据槽确定记录所在的页中的分组中最后一条记录，最后一条记录里的记录头里有分组里包含的记录数目，基于此可以定位查找的记录所在的分组的第一条记录，从第一条记录开始遍历分组，看是否有记录与要查询的主键值匹配。

2.2 二级索引

2.2.1 什么是二级索引

2.1节介绍的聚簇索引使用时有个前提：只有搜索条件是主键值才会发挥作用，业务中我们的where条件语句经常是各种字段的查询，此时二级索引就派上了用场。二级索引会根据索引列来对数据页与数据页，页中每一条记录进行排序，而在聚簇索引中是按照主键值从小到大排序，二级索引是根据索引列的值从小到大排序。
介绍B+树索引由来时举的例子，如果建立了二级索引，索引列是c2列，则根据c2列建立的B+树索引如下图所示，图中深蓝色得列是索引列c2：
索引 - 图8

二级索引的B+树有如下特点：

  • 使用索引列的大小进行记录和页的排序，这包括三个方面的含义：
    • 页内的记录是按照索引列的大小顺序排成一个单向链表；
    • 各个存放用户记录的页也是根据页中记录的索引列大小顺序排成一个双向链表；
    • 存放目录项记录的页分为不同的层次，在同一层次中的页也是根据页中目录项记录的索引列大小顺序排成一个双向链表。
  • B+树的叶子节点存储的并不是完整的用户记录（即不是用户记录的所有列），而只是索引列+主键这两个列的值；
  • 目录项记录中不再是主键 + 页号的搭配，而变成了索引列 +主键列 + 页号的搭配。

    2.2.2 如何根据二级索引查找记录

    我们现在想通过索引列：c2列查找某些记录，以查找c2列的值为4的记录为例，查找过程如下（参考上面的二级索引B+树的图）：
    （1）确定目录项记录页
    根据根页面，也就是页44，可以快速定位到目录项记录所在的页为页42（因为2 < 4 < 9）。
    （2）通过目录项记录页确定用户记录真实所在的页
    在页42中可以快速定位到实际存储用户记录的页，但是由于c2列并没有唯一性约束，所以c2列值为4的记录可能分布在多个数据页中，又因为2 < 4 ≤ 4，所以确定实际存储用户记录的页在页34和页35中。
    （3）在真实存储用户记录的页中定位到具体的记录
    到页34和页35中定位到具体的记录。
    （4）回表
    由于二级索引B+树叶子节点中的记录值只存储了索引列c2和主键列c1，所以我们必须再根据主键值从聚簇索引中再查找一遍完整的用户记录，这个过程叫回表。

    2.2.3 回表

    2.2.2中的第4步，我们根据这个以c2列大小排序的B+树只能确定我们要查找记录的主键值，所以如果我们想根据c2列的值查找到完整的用户记录的话，仍然需要到聚簇索引中再查一遍，这个过程也被称为回表。也就是根据**c2**列的值查询一条完整的用户记录需要使用到**2**棵**B+**树。
    为什么还需要回表呢？直接像聚簇索引一样，将完整的用户记录存放到叶子节点中不就行了么？答案是这样做会存储冗余数据。相当于每建立一棵B+树都需要把所有的用户记录再都拷贝一遍，这就有点太浪费存储空间了。

    2.2.4 顺序IO和随机IO（回表的代价）

    上面介绍了回表的概念，回表这个过程其实是耗费性能的，下面具体介绍一下顺序IO和随机IO的概念以及回表过程的性能损耗。
    建表如下：
    1. CREATE TABLE person_info(
    2.   id INT NOT NULL auto_increment,
    3.   name VARCHAR(100) NOT NULL,
    4.   birthday DATE NOT NULL,
    5.   phone_number CHAR(11) NOT NULL,
    6.   country varchar(100) NOT NULL,
    7.   PRIMARY KEY (id),
    8.   KEY idx_name_birthday_phone_number (name, birthday, phone_number)
    9. );
    person_info表中有2个索引，一个是主键id对应的聚簇索引（InnoDB会自动为主键列建立聚簇索引），另一个是用KEY关键字声明的是由name列、birthday列和phone_number列构成的联合索引（联合索引的内容在2.3小节会介绍）。

下面的SQL语句对person_info表进行查询，如下：

  1. SELECT * FROM person_info WHERE name > 'Asa' AND name < 'Barlow';

查询条件里有联合索引idx_name_birthday_phone_number的索引列，整个查询过程如下：

  1. 从联合索引idx_name_birthday_phone_number对应的B+树中取出name值在Asa和Barlow之间的索引项记录；
  2. 由于索引idx_name_birthday_phone_number对应的B+树叶子节点中只包含name、birthday、phone_number、id这4个字段，而查询列表是*，需要获取country字段的信息，因此需要进行回表，即从第一步中获取到的主键id对应的B+树（聚簇索引）根据id字段查询，获取聚簇索引中叶子节点中完整的用户记录，并将其返回给客户端。

下面继续介绍顺序IO和随机IO的概念：

  • 顺序IO：由于索引idx_name_birthday_phone_number对应的B+树中的记录首先会按照name列的值进行升序排序，所以值在Asa～Barlow之间的记录在磁盘中的存储是相连的，集中分布在一个或几个数据页中，我们可以很快的把这些连着的记录从磁盘中读出来，这种读取方式我们也可以称为顺序I/O；
  • 随机IO：根据第1步从联合索引对应的B+树获取到的记录的id字段的值可能并不相连，而在聚簇索引中记录是根据id（也就是主键）的顺序升序排列的，所以根据这些并不连续的id值到聚簇索引中访问完整的用户记录可能分布在不同的数据页中，这样读取完整的用户记录可能要访问更多的数据页，这种读取方式我们也称为随机I/O。

总结：第一步查询联合索引使用的是顺序IO，第二部查询聚簇索引使用的是随机IO，显然顺序IO比随机IO的性能高很多，顺序IO仅需要遍历几个连续的数据页，而不像随机IO一样东找一个西找一个。

需要回表的记录越多，使用到顺序IO的二级索引（联合索引）的就越少，性能就越低，甚至有时候查询时走全表扫描都比使用二级索引的效率要高。那什么时候采用全表扫描的方式，什么时候使用采用二级索引 + 回表的方式去执行查询呢？这个就是查询优化器做的工作，查询优化器会事先对表中的记录计算一些统计数据，然后再利用这些统计数据根据查询的条件来计算一下需要回表的记录数，需要回表的记录数越多，就越倾向于使用全表扫描，反之倾向于使用二级索引 + 回表的方式。一般当需要回表的记录数目超过总记录数目的**30%**时就会采用全表扫描，否则会用二级索引 + 回表的方式，这个30%数字只是个大概值。
比如下面的SQL语句就会使用到二级索引 + 回表的方式查询：

  1. # 添加了LIMIT语句限定了结果集的数目，使回表的数据格式不会太多
  2. SELECT * FROM person_info WHERE name > 'Asa' AND name < 'Barlow' LIMIT 10;
  4. # 对于有排序需求的查询（搜索条件就是索引列）上面介绍的规则依然成立
  5. SELECT * FROM person_info ORDER BY name, birthday, phone_number LIMIT 10;

2.2.5 索引下推

索引下推全称 Index Condition Pushdown，简称ICP，是MySQL 5.6之后引入的特性。索引下推的前提是查询条件是二级索引，索引下推可以减少回表的次数，提高查询效率。使用到了索引下推的语句的执行计划里，Extra列是Using index condition。
以下面的sql语句为例，说明以下索引下推的具体情况，表中对key1列建立了二级索引，查询语句如下：

  1. SELECT * FROM s1 WHERE key1 > 'z' AND key1 LIKE '%a';

根据最左匹配原则，上面的sql语句中，key1 > ‘z’可以使用到二级所用，key1 like ‘%a’无法使用到索引，在MySQL 5.6之前的版本，上述sql语句的执行步骤如下：

  1. 先根据key1 > ‘z’这个条件，从二级索引中获取对应的二级索引记录；
  2. 根据1中得到的二级索引记录，通过主键id去聚簇索引树中进行回表，找到完整的列的数据，再检查数据是否符合key1 like ‘%a’的查询条件，将符合该条件的记录放到最终的结果集中。

上述的查询过程中，虽然key1 like ‘%a’ 不能使用到索引进行查询，但是这个查询条件毕竟仅涉及到了key1这个二级索引，因此引入了索引下推的优化，基于索引下推的优化，上述sql语句的执行步骤如下：

  1. 先根据key1 > ‘z’这个条件，从二级索引中获取对应的二级索引记录；
  2. 对于1中的二级索引记录，先不着急回表，而是检测记录是否满足key1 like ‘%a’这个查询条件，只将满足了这个查询条件的二级索引记录进行回表，从而减少了回表的次数。由于回表的过程是随机IO，比较耗时，因此提升了查询效率。

索引下推的参考文章见：Explain 详解（下）

2.3 联合索引

联合索引就是在二级索引的基础上，索引列不仅限于一个列，可以是多个列构成一个索引。联合索引的B+树会按照组成索引的若干列进行排序，比方说我们想让B+树按照c2和c3列的大小进行排序，这个包含两层含义：

  • 先把各个记录和页按照c2列进行排序；
  • 在记录的c2列相同的情况下，采用c3列进行排序。

因此在使用创建索引的INDEX语句时，索引列的先后顺序是很重要的。

为c2、c3列构建联合索引的B+树结构如下图所示：
索引 - 图9
上图中可以总结一下联合索引的B+树特点：

  • 每条目录项记录都由c2、c3、页号这三个部分（即联合索引的列们和页号两部分）组成，各条记录先按照c2列的值进行排序，如果记录的c2列相同，则按照c3列的值进行排序；
  • B+树叶子节点处的用户记录由c2、c3和主键c1列组成（即由联合索引的列和主键列组成）；

  • 同样需要回表，同样需要再根据主键值查找聚簇索引，同样需要用到2棵B+树。

    3、索引的代价

    索引虽然会加速我们的查询，但是使用索引也会在时间和空间上都付出一定的代价，具体如下：
    （1）空间上的代价
    一个索引就是一棵B+树，每一棵B+树的每一个节点都是一个数据页，一个数据页会占用16KB的内存空间，索引对应的B+树由许多数据页组成，因此索引会占用很大的存储空间。
    （2）时间上的代价
    每次对表进行增删改操作时，可能会涉及到页分裂。页分裂在1.2.1小节介绍过，B+树每层节点都是按照索引列的值从小到大的顺序排序而组成了双向链表，不论是叶子节点中的记录，还是内节点中的记录（也就是不论是用户记录还是目录项记录）都是按照索引列的值从小到大的顺序而形成了一个单向链表。而增、删、改操作可能会对节点和记录的排序造成破坏，所以存储引擎需要额外的时间进行一些记录移位，页面分裂等，这个过程会耗费一些时间。

    4、适合B+树索引的查询情况

    不是所有查询语句都能用到我们建立的索引，下面介绍以一下可能使用B+树索引进行查询的情况。
    为了介绍方便，以一个个人信息的表person_info表为例，建表语句如下：

    1. CREATE TABLE person_info(
    2.   id INT NOT NULL auto_increment,
    3.   name VARCHAR(100) NOT NULL,
    4.   birthday DATE NOT NULL,
    5.   phone_number CHAR(11) NOT NULL,
    6.   country varchar(100) NOT NULL,
    7.   PRIMARY KEY (id),
    8.   KEY idx_name_birthday_phone_number (name, birthday, phone_number)
    9. );

    说明：

  • 表中主键列是id列，是自增的，因此InnoDB存储引擎会自动为id列建立一个聚簇索引；

  • 除了聚簇索引之外，还建立了一个联合索引，索引列是name、birthday和phone_number三个列组成，还有一个country列没在索引列中。

person_info表会为聚簇索引和联合索引建立2棵B+树，下边我们画一下索引idx_name_birthday_phone_number的示意图，如下：
image.png
由于联合索引中列的声明顺序是：name、birthday和phone_number，图中页和记录的排序方式如下：

  • 先按照name列的值进行排序；
  • 如果name列的值相同，则按照birthday列的值进行从小到大的排序；
  • 如果birthday列的值也相同，则按照phone_number列的值从小到大排序。

这个排序规则会贯穿下面的小节。

4.1 全值匹配

如果搜索条件中的列和索引列一致的话，这种情况就称为全值匹配，全值匹配中联合索引的索引列都会用到。
比如上面例子中，以下sql查询语句就是全值匹配：

  1. SELECT * FROM person_info WHERE name = 'Ashburn' AND birthday = '1990-09-27' AND phone_number = '15123983239';

上面sql语句的查询过程：

  • 因为B+树的数据页和记录先是按照name列的值进行从小到大排序的，所以先定位name列的值是Ashburn的记录位置；
  • 在name列相同的记录里又是按照birthday列的值从小到大进行排序的，所以在name列的值是Ashburn的记录里又可以快速定位birthday列的值是'1990-09-27‘的记录；
  • 如果name和birthday列的值都相同，那记录就按照phone_number列的值从小到大排序，所以联合索引中的三个列都可能被用到。

上面**WHERE**子句中搜索条件的顺序改变不会影响到查询过程，因为**InnoDB**中的查询优化器会自动选择先使用哪个搜索条件，后使用哪个搜索条件。

4.2 匹配左边的列

查询语句的搜索条件，只有包含了索引列中最左边的列，索引才能生效，且如果联合索引中有多个列时，搜索条件中的各个列必须是联合索引中从最左边连续的列，下面用例子解释一下这句话：

  • 以下sql语句可以使用到上面创建的联合索引： ```sql

    仅包含索引列中最左边的列

    SELECT * FROM person_info WHERE name = ‘Ashburn’;

匹配索引列中从最左边的列开始的部分索引列

SELECT * FROM person_info WHERE name = ‘Ashburn’ AND birthday = ‘1990-09-27’;

  2. - 以下sql语句无法使用或者部分使用到上面创建的联合索引：
  3. ```sql
  4. # 搜索条件没有从索引列中最左边的列开始
  5. SELECT * FROM person_info WHERE birthday = '1990-09-27';
  7. # 搜索条件从索引列中最左边的列开始，但没有按顺序依次添加到搜索条件，索引中仅有name列可以用到
  8. SELECT * FROM person_info WHERE name = 'Ashburn' AND phone_number = '15123983239';

对“SELECT * FROM person_info WHERE birthday = '1990-09-27'; ”这条sql语句没有用到索引的原因做一个解释说明：因为B+树的数据页和记录先是按照name列的值从小到大排序的，在name列的值相同的情况下才使用birthday列从小到大进行排序，也就是说name列的值相同的记录的birthday值是有序的，name列的值不同的记录中birthday的值可能是无序的。因此搜索条件上来就是birthday对于按照联合索引中已经排序好的记录来说，不能通过比较birthday的值进行遍历来查找记录，也就是用不上我们创建的联合索引。

4.3 匹配列前缀

查询语句中搜索条件是模糊查询，且模糊查询是从索引列最左边的列开始，此时也可以用到索引，这种查询叫匹配列前缀查询。
举例如下：

  1. # 模糊搜索条件是以索引列最左边的列开始，且从头开始通配，可以用到索引
  2. SELECT * FROM person_info WHERE name LIKE 'As%';
  4. # 是从中间开始通配，用不到索引
  5. SELECT * FROM person_info WHERE name LIKE '%As%';

字符串排序的本质就是根据比较规则比较字符串的大小，一般是依次比较两个字符串组成字符的ASCII码值，比较是只要字符串的一个字符大于另一个字符串的对应字符，字符串中剩下的字符就不需要比较了，因此模糊搜索时只要前面的若干的字符能比较出来就可以了。但是如果列中的值都很相似，比如字符串的前很多位字符都是相同的，这样就不要使用匹配列前缀的搜索条件了。

4.4 匹配范围值

查询语句的WHERE搜索条件是一个范围，用比较操作符< > between等连接from和to的搜索条件，多个用AND连接的范围搜索条件，只有范围搜索条件是索引列中最左边的列才能使用到索引，举个例子：

  1. # 该范围搜索语句可以使用到索引
  2. SELECT * FROM person_info WHERE name > 'Asa' AND name < 'Barlow';
  4. # 该范围搜索语句，仅有name条件的可以用到索引，birthday条件用不到索引
  5. SELECT * FROM person_info WHERE name > 'Asa' AND name < 'Barlow' AND birthday > '1980-01-01';

对上面第一条使用到索引的范围搜索语句，查询过程如下：

  1. 通过B+树在叶子节点中找到第一条name值大于Asa的二级索引记录，读取该记录的主键值并进行回表操作，获得对应的聚簇索引记录后发送给客户端；
  2. 根据步骤1中找到的记录，沿着记录所在的链表向后查找（同一页面中的记录使用单向链表连接起来，数据页之间用双向链表连接起来）下一条二级索引记录，判断该记录是否符合name < 'Barlow'条件，如果符合，则进行回表操作后发送至客户端；
  3. 重复步骤2，直到某条二级索引记录不符合name <'Barlow'条件为止。

对于上面第二条范围搜索语句，使用不到索引的原因如下：通过name进行范围查找的记录中可能并不是按照birthday列进行排序的，所以在搜索条件中继续以birthday列进行查找时是用不到这个B+树索引的，说白了是因为索引中的记录是先按照name列的值从小到大排序的，搜索条件中必须首先包含name。

4.5 精确匹配某一列并范围匹配另外一列

如果查询语句的搜索条件，左边是精准查询，右边是范围查询，如下：

  1. SELECT * FROM person_info WHERE name = 'Ashburn' AND birthday > '1980-01-01' AND birthday < '2000-12-31' AND phone_number > '15100000000';

这个查询的条件可以分为3个部分：

  1. name = ‘Ashburn’，对name列进行精确查找，当然可以使用B+树索引了；
  2. birthday > ‘1980-01-01’ AND birthday < ‘2000-12-31’，由于name列是精确查找，所以通过name = ‘Ashburn’条件查找后得到的结果的name值都是相同的，它们会再按照birthday的值进行排序。所以此时对birthday列进行范围查找是可以用到B+树索引的；
  3. phone_number > ‘15100000000’，通过birthday的范围查找的记录的birthday的值可能不同，所以这个条件无法再利用B+树索引了，只能遍历上一步查询得到的记录；如果birthday也是精确查找，则phone_number > ‘15100000000’范围查询可以使用索引。

    4.6 索引用于排序

    在使用ORDER BY子句进行排序时，一般情况下，MySQL都会把记录加载到内存或者磁盘中（如果查询出的结果集太大，会借助磁盘），再用一些快速排序、归并排序等排序算法对内存或者磁盘中的记录进行排序，MySQL中把需要在内存或者磁盘中进行排序的方式称为文件排序（**filesort**）。但如果ORDER BY子句里排序规则是我们的索引列或者索引列的一部分，且ORDER BY子句的列的排序顺序与索引列中的顺序一致，就可以避免在内存或者磁盘中进行排序，直接从B+树索引中读取出来的记录就是排好序的记录。

    4.6.1 可以使用索引进行排序的情况

    如下SQL语句可以使用索引直接完成排序，而不需要在内存或者磁盘中再通过排序算法进行排序：
    1. SELECT * FROM person_info ORDER BY name, birthday, phone_number LIMIT 10;
    这个查询的结果集需要先按照name值排序，如果记录的name值相同，则需要按照birthday来排序，如果birthday的值相同，则需要按照phone_number排序。这就是联合索引中的排序规则，因此可以直接从索引的叶子节点提取出主键值，再进行回表操作取出记录的完整列即可，全程不需要排序。
    注意：使用联合索引进行排序的搜索条件中，**ORDER BY**子句后边的列的顺序也必须按照索引列中的顺序给出，如果给出ORDER BY phone_number, birthday, name的顺序，那也是用不了B+树索引了，这还是因为联合索引中列的顺序已经指定了排序规则的原因。

    4.6.2 不能使用索引进行排序的情况

  • ORDER BY子句中，索引列一个按DESC，另一个按ASC，则不能使用索引排序；
  • ORDER BY子句中的列有非索引列的列作为排序列；
  • ORDER BY子句中的排序列使用到了复杂的表达式，比如UPPER。

    4.7 索引用于分组

    在分组查询中比如如下语句：
    1. SELECT name, birthday, phone_number, COUNT(*) FROM person_info GROUP BY name, birthday, phone_number
    这个查询语句相当于做了3次分组操作：
  1. 先把记录按照name值进行分组，所有name值相同的记录划分为一组；
  2. 将每个name值相同的分组里的记录再按照birthday的值进行分组，将birthday值相同的记录放到一个小分组里，所以看起来就像在一个大分组里又化分了好多小分组；
  3. 再将上一步中产生的小分组按照phone_number的值分成更小的分组，所以整体上看起来就像是先把记录分成一个大分组，然后把大分组分成若干个小分组，然后把若干个小分组再细分成更多的小小分组。

如果分组顺序和联合索引的B+树中的索引列的顺序是一致的（由于联合索引中的B+树索引已经按照索引列排好序的），因此可以直接使用联合索引的B+树进行分组。

5、如何建立索引

总结一下建立索引时的一些tips：
（1）只为用于搜索、排序或分组的列创建索引
也就是说，只为出现在WHERE子句中的列、连接查询中的连接列，或者出现在ORDER BY或GROUP BY子句中的列创建索引。而出现在查询列表中的列就没必要建立索引了，比如下面的sql语句：

  1. SELECT birthday, country FROM person_name WHERE name = 'Ashburn';

像上面例子中，查询列表中的birthday、country这两个列就不需要建立索引，我们只需要为出现在WHERE子句中的name列创建索引就可以了。
（2）为列的基数大的列创建索引
列的基数指的是某一列中不重复数据的个数，比方说某个列包含值2, 5, 8, 2, 5, 8, 2, 5, 8，虽然有9条记录，但该列的基数却是3。也就是说，在记录行数一定的情况下，列的基数越大，该列中的值越分散，列的基数越小，该列中的值越集中。
如果某个列的基数为1，即该列在记录中的值都是一样的，就不需要用到索引去排序了，直接返回全部就可以了。
如果某个列的基数很小，即列中的数据很集中，基本都是相同的，根据搜索条件通过二级索引查出来的记录会很多，这些记录还需要通过回表的操作再查一次聚簇索引，这样两次查询索引还不如直接全量查询的效率高。因此查询优化器会进行优化处理：当列中的某个值在表中记录出现的百分比很高时，会忽略索引，使用全表扫描，这个阈值一般是30%。
比如列是记录用户性别的，只有男、女两个值，这种列就不要再建立索引了。
（3）索引列的类型尽量小
这里说的索引列类型的大小是指类型大小所占据的字节数多少，比如能用INT类型就不要用BIGINT类型，这是因为：

  • 数据类型越小，在查询时进行的比较操作越快；
  • 数据类型越小，索引占用的存储空间越小，一个数据页中可以放下更多的记录，相当于Buffer Pool的缓存页中中可以加载进来更多的数据，进而可以减小磁盘IO的次数，降低磁盘IO带来的性能损耗。

这个tip对表的主键列来说更为适用，因为不仅是聚簇索引会存放主键值，二级索引中也会存放主键值，如果主键适用更小的数据类型，就意味着更多的存储空间和更少的磁盘IO损耗。
（4）可以只对字符串值的前缀建立索引
如果列中存储的字符串很长，要占用很大的存储空间，可以考虑使用字符串前缀作为索引，这样在查找记录时虽然不能精确的定位到记录的位置，但是能定位到相应前缀所在的位置，然后根据前缀相同的记录的主键值回表查询完整的字符串值，再对比就好了，举个例子：

  1. CREATE TABLE person_info(
  2.     name VARCHAR(100) NOT NULL,
  3.     birthday DATE NOT NULL,
  4.     phone_number CHAR(11) NOT NULL,
  5.     country varchar(100) NOT NULL,
  6.     KEY idx_name_birthday_phone_number (name(10), birthday, phone_number)
  7. );

name(10)就表示在建立的B+树索引中只保留记录的前10个字符的编码，适用于字符串之前差异比较大的情况，如果前10个字符都一样的话就不建议用字符串前缀建立索引了。
（5）让索引列在比较表达式中单独出现
假设表中有一个整数列my_col，我们为这个列建立了索引。下边的两个WHERE子句虽然语义是一致的，但是在效率上却有差别：

  1. WHERE my_col * 2 < 4
  2. WHERE my_col < 4/2

第1个WHERE子句中my_col列并不是以单独列的形式出现的，而是以my_col * 2这样的表达式的形式出现的，存储引擎会依次遍历所有的记录，计算这个表达式的值是不是小于4，所以这种情况下是使用不到为my_col列建立的B+树索引的。而第2个WHERE子句中my_col列并是以单独列的形式出现的，这样的情况可以直接使用B+树索引。因此如果索引列在比较表达式中不是以单独列的形式出现，而是以某个表达式，或者函数调用形式出现的话，是用不到索引的。
（6）为了尽可能少的让聚簇索引发生页面分裂和记录移位的情况，建议让主键拥有AUTO_INCREMENT属性
我们在插入记录时，如果记录要插入的数据页已经满了的时候，此时会进行页分裂，重新生成一个数据页，将之前页中的数据和新插入的数据按照主键值从小到大的顺序分配的两个数据页中，这个过程中会伴随着页分裂和记录从一个数据页移动到另一个数据页的场景，这个过程是很消耗性能的。
如果我们插入记录时，主键值是依次递增的，那我们每插满一个数据页就换到下一个数据页继续插，这个过程中只会产生新的数据页，不会有记录移动的问题。因此让主键具有AUTO_INCREMENT，让存储引擎自己为表生成主键，效率会更高，如下：

  1. CREATE TABLE person_info(
  2.     id INT UNSIGNED NOT NULL AUTO_INCREMENT,
  3.     name VARCHAR(100) NOT NULL,
  4.     birthday DATE NOT NULL,
  5.     phone_number CHAR(11) NOT NULL,
  6.     country varchar(100) NOT NULL,
  7.     PRIMARY KEY (id),
  8.     KEY idx_name_birthday_phone_number (name(10), birthday, phone_number)
  9. );

（7）避免冗余和重复索引
有时候建立索引时可能会不小心给同一个列创建了不同的索引，这种冗余索引不仅会占用内存空间，维护上也会增加成本。
（8）尽量使用覆盖索引进行查询，避免回表带来的性能消耗
为了彻底告别回表操作带来的性能损耗，建议在查询列表里只包含索引列，比如这样：

  1. SELECT name, birthday, phone_number FROM person_info WHERE name > 'Asa' AND name < 'Barlow'

这样仅通过建立的联合索引的B+树就可以完成查询了，因为联合索引的B+树叶子节点存放的就是索引列的值，避免了再回表去聚簇索引里再查一遍叶子节点把完整的列读取出来，我们把这种查询列表里仅用到索引列的查询方式称为索引覆盖。
select语句里查询列表不要用*也是尽可能避免回表。

6、索引相关知识点及面试题

6.1 B树和B+树的数据结构

上面介绍了MySql中的索引为什么是B+树，这里抛开MySql，单纯地介绍一下B树和B+树这两种具体的数据结构。

6.1.1 B树

一棵m阶的B-Tree有如下特性：

  • 每个节点最多有m个孩子。
  • 除了根节点和叶子节点外，其它每个节点至少有Ceil(m/2)个孩子。
  • 若根节点不是叶子节点，则至少有2个孩子
  • 所有叶子节点都在同一层，且不包含其它关键字信息
  • 每个非终端节点包含n个关键字信息（P0,P1,…Pn, k1,…kn）
  • 关键字的个数n满足：ceil(m/2)-1 <= n <= m-1
  • ki(i=1,…n)为关键字，且关键字升序排序。
  • Pi(i=1,…n)为指向子树根节点的指针。P(i-1)指向的子树的所有节点关键字均小于ki，但都大于k(i-1)

如下图所示为一个3阶的B Tree：
索引 - 图11
总结下B树的特点：

  • B树的非叶子节点和叶子节点都存储data值（data值可以理解为用户记录）；
  • B树的非叶子节点和叶子节点都存储键值信息和指向下一个节点的指针信息；
  • B树的相邻叶子结点之间没有指针连接。

    6.1.2 B+树

B+Tree相对于B-Tree有几点不同：

  • 非叶子节点只存储键值信息和指向下一个节点的指针信息；
  • 叶子节点只存放具体数据记录；
  • 所有叶子节点组成一个双向链表，便于遍历数据。

如下图所示为一个3阶的B+Tree：
索引 - 图12
这里介绍一下磁盘IO与索引树的关系。之前我们提到过InnoDB的页的概念，页是磁盘与内存交互的基本单位，实际上页还不是磁盘与内存交互的最小单位，而是磁盘块（block），而系统的一个磁盘块的存储空间往往没有这么大，因此InnoDB每次申请磁盘空间时都会是若干个连续磁盘块来凑成一个页的大小16KB。索引树的一个节点对应一个磁盘块，一个磁盘块对应一次磁盘IO，因此树的高度越低，树整体呈“矮胖”型，磁盘IO的次数越少，查询效率就越高。

那B+树相比B树有什么优点呢？下面针对B+树相比B树的两个不同点说明：

（1）B+树的非叶子节点不存储数据记录，仅存储主键值和指针
MySql中页的大小是固定的16KB，B+树非叶子节点不存储具体数据记录，仅存储主键值和指针这些索引信息，可以使一个节点（对应一个16KB大小的数据页）能存储更多的索引信息，使整个树呈“矮胖”形，降低树的高度进而减少磁盘IO次数，提高查询效率。

（2）所有数据记录都存储在B+树的叶子节点里，且叶子结点间组成一个双向链表
数据库肯定涉及遍历数据的场景，B+树相比B树，数据记录全部存储在叶子节点，且叶子结点间组成一个双向链表，因此B+树遍历数据时只需要遍历双向链表即可；而B树要由于数据记录也存储在非叶子节点，遍历数据时要遍历整棵B树，自然效率没有遍历链表高。

B+树的所有数据记录都存储在叶子节点，所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当。

6.2 Hash索引

Hash索引的数据结构在下图中有展示，Hash索引的数据结构是一张哈希表，key存放的是记录的主键值通过哈希函数得到的哈希码，value是指向该记录的指针。哈希表中记录是按照哈希码从小到大的顺序排列的，并不一定是按照主键值的字典序从小到大排列。Hash索引解决哈希冲突的方法是拉链法。需要指出的是，如果是指定主键值查询，由于只需要根据主键值通过一次哈希函数就能确定哈希索引中的哈希码，在哈希冲突不严重的情况下使用哈希索引按照指定主键值查询的效率更高，但当哈希冲突比较严重，且是范围查找时，就不能使用哈希索引而采用B+树索引了。
索引 - 图13
MySql的索引一般采用B+树索引而不是哈希索引的原因是什么呢？或者哈希索引的局限性是什么？下面总结为以下几点：

  • 哈希索引只存储哈希码和行指针，并不存储字段值，确定了行指针后还需要将行指针指向的记录与要查询的记录进行比较，所谓的“不能避免读取行”；
  • 哈希索引的key是主键值通过哈希函数得到的哈希码，哈希表中的排序顺序是根据哈希码而不是主键值（或者叫索引值），所以不能基于哈希索引对数据库记录进行排序；
  • 哈希索引仅支持等值比较查询，不支持范围查询；
  • 当哈希函数不够好，或者数据量过大导致哈希冲突严重时，拉链法遍历链表会让查询速率下降，此时应使用B+树索引。

    6.3 索引常见面试题

    （1）什么是索引？
    索引是为了更加快速高效的查询而设计的针对数据库的一种数据结构，常见的数据库索引有B+树、B树和哈希索引，MySql的默认索引是B+树，MongoDB的索引是B树。

（2）索引的优缺点是什么？
优点：

  • 快速查询数据

缺点：

  • 创建索引和维护索引要耗费时间；
  • 索引需要占物理空间；

具体可以参考链接6。

（3）哪些列适合建立索引、哪些不适合建索引？
我总结我能理解的，更详细的参考链接7。
哪些列适合建立索引？

  • 在经常需要搜索的列上，可以加快搜索的速度；
  • 在作为主键的列上，强制该列的唯一性和组织表中数据的排列结构；
  • 在经常用在连接的列上，这些列主要是一些外键，可以加快连接的速度；

哪些列不适合建立索引？

  • 对于那些在查询中很少使用或者参考的列不应该创建索引。
  • 对于那些只有很少数据值的列也不应该增加索引。

（4）什么样的字段适合建索引？
唯一、不为空、经常被查询的字段。

（5）为什么MySql使用B+树索引而不是哈希索引？
答哈希索引的局限性就行。

  • 哈希索引只存储哈希码和行指针，并不存储字段值，确定了行指针后还需要将行指针指向的记录与要查询的记录进行比较，所谓的“不能避免读取行”；
  • 哈希索引的key是主键值通过哈希函数得到的哈希码，哈希表中的排序顺序是根据哈希码而不是主键值（或者叫索引值），所以不能基于哈希索引对数据库记录进行排序；
  • 哈希索引仅支持等值比较查询，不支持范围查询；
  • 当哈希函数不够好，或者数据量过大导致哈希冲突严重时，拉链法遍历链表会让查询速率下降，此时应使用B+树索引。

当然，哈希索引也有使用场景：当时等值查询，且哈希冲突不严重的情况下哈希索因的查询效率还是很高的。

（6）MySql的索引为什么是B+树而不是B树？
先答一下B树和B+树的数据结构的区别。
B树：

  • B树的非叶子节点和叶子节点都存储data值（data值可以理解为用户记录）；
  • B树的非叶子节点和叶子节点都存储键值信息和指向下一个节点的指针信息；
  • B树的相邻叶子结点之间没有指针连接。

B+树：

  • 非叶子节点只存储键值信息和指向下一个节点的指针信息；
  • 叶子节点只存放具体数据记录；
  • 所有叶子节点组成一个双向链表，便于遍历数据。

再答为什么B树和B+树数据结构的差异导致索引选B+树？
（a）B+树的非叶子节点不存储数据记录，仅存储主键值和指针
MySql中页的大小是固定的16KB，B+树非叶子节点不存储具体数据记录，仅存储主键值和指针这些索引信息，可以使一个节点（对应一个16KB大小的数据页）能存储更多的索引信息，使整个树呈“矮胖”形，降低树的高度进而减少磁盘IO次数，提高查询效率。

（b）所有数据记录都存储在B+树的叶子节点里，且叶子结点间组成一个双向链表
数据库肯定涉及遍历数据的场景，B+树相比B树，数据记录全部存储在叶子节点，且叶子结点间组成一个双向链表，因此B+树遍历数据时只需要遍历双向链表即可；而B树要由于数据记录也存储在非叶子节点，遍历数据时要遍历整棵B树，自然效率没有遍历链表高。
B+树的所有数据记录都存储在叶子节点，所以任何关键字的查找必须走一条从根结点到叶子结点的路，所有关键字查询的路径长度相同，导致每一个数据的查询效率相当。

（7）B树真的不适合做索引么？为什么MongoDB的索引是B树而不是B+树？
这个参考的链接6，不要把B树喷的一无是处…
因为B树适合单条记录的查询，不适合遍历记录；B+树更适合遍历记录。

  • B数的非叶子节点也存储数据，因此查询单条记录时B树的查询效率不固定，可以认为，在查询单条记录时使用B数的平均性能更好。但是由于B树节点之间没有指针连接，因此B树不适合做数据遍历的操作。
  • B+仅有叶子节点存储数据，因此查询单条记录时查询效率固定，都是从根节点到叶子节点，可以认为，在查询单条记录时B+树的平均性能没有B树的好。但是B+树叶子节点是有指针连接的，遍历数据实际是在遍历叶子节点组成的双向链表，自然B+树适合做遍历操作。

解释到这里，问题就转化成：为什么MongoDB的遍历记录的场景不多，MySql遍历记录的场景多呢？
答：因为MySql是关系型数据库，MongoDB是非关系型数据库。
问题又转化成：为什么关系型数据库遍历记录的场景多，而非关系型数据库遍历记录的场景少呢？
下面摘自链接6，更底层的我答不出上了：

由于关系型数据库和非关系型数据的设计方式上的不同。导致在关系型数据中，遍历操作比较常见，因此采用B+树作为索引，比较合适。而在非关系型数据库中，单一查询比较常见，因此采用B树作为索引，比较合适。

参考

掘金小册
B树和B+树原理及在索引中的应用
数据库中的索引技术——哈希索引
为什么Mongodb索引用B树，而Mysql用B+树?
2020年前必须掌握的数据库面试问题
MySQL索引优化看这篇文章就够了！