1. 什么是索引

索引是帮助MySQL高效获取数据的一种数据结构
MySQL数据库种的数据存储在计算机的磁盘中，在执行查询时，需要将磁盘中的数据读入内存，这部分的时间开销很大，索引的出现就是为了减少磁盘的IO次数

2. 数据查询过程

有一张数据表table：

id name
1 张三
2 李四
3 王五
4 赵六
5 钱七

假设没有索引，需要查找id=4的数据，采用最原始的方式 —- 顺序查找

  1. select * from `table` where id = 4; 
  2. 1. 首先需要将这些数据从磁盘加载到内存
  3. 2. 在内存中顺序查找，逐条比较id是否与要求的相等
  4. 3. 找到第四条数据并返回

数据在磁盘中是以磁盘块的形式进行存储的，当数据量较大时，一个磁盘块装不下，需要多个磁盘块，那么在查询的过程中可能需要多次IO，把目标数据所在的磁盘块加载到内存中，时间成本很高

3. 索引底层数据结构 — B+树

MySQL存储数据时，会将数据存储在一个数据页中，一个数据页大小默认为16KB
数据页类似于一个容器，可以装多条数据，如果数据放满了，那就换一个容器，即新建一个数据页来存储
现在假设一个数据页中能方三条数据，那么上述table表的数据存储在磁盘中就是
MySQL索引 - 图1
数据页中的数据以单链表的形式进行连接，并且按照指定的关键字进行升序排序（在此处就是id的值），数据页与数据页之间以双向链表的形式进行连接
现在，为了方便查找，可以为这两个数据页做一个标识，将每个数据页中最小的一条记录拿出来，做成一个目录，存放进另一个数据页
MySQL索引 - 图2
目录页中目录项的结构是 [id，数据页号]，即id所在的数据页的页号，目录项的连接方式与数据项相同。目录之间也使用单链表进行连接，并且也需要根据id的值进行升序排序，并且目录项需要指向它所标记的数据页，这就构成了一棵简易的B+树
有了这棵B+树之后，假设要查询id=3这条数据，查询的顺序就是

  1. 1. 先将目录页1加载到内存中，先比较第一个目录id=1<3，再比较第二个目录项id=4>3，那么就说明id=3的记录在目录项id=1的所指的数据页中
  2. 2. 将数据页1加载到内存中，由于数据页中的数据是有序的，所以可以进行二分法查找，找到id=3这条数据并返回

虽然在数据量比较小的情况下，这种索引的优势体现不出来，但当数据量十分庞大时，比如上百万条数据，如果使用顺序查找，就需要从第一个数据页开始，一个一个将数据页加载到内存，并逐个比较；而索引的方式就可以避免加载一些无关的数据页，减少IO的次数，通常IO的次数与B+树的深度有关，一般数据库底层的B+树不会超过四层，也就是说，最多只需要四次IO就能够找到目标数据

为什么B+树不会超过四层？
这是由于一个数据页的大小为16KB，假设一条数据的大小为16B，那么这个数据页就能够容纳16KB / 16B = 1000条数据，再看目录页，一个目录项显然要比一条数据项小的多，因为它只记录两项数据，一个是关键字的值，一个是所标识的数据页，那现在仍然假设一个目录项是16B，一个目录页能容纳的目录项也是1000条，那么光两层的B+树就能够存储的数据量为1000 * 1000 = 10^6条数据，三层的话就是10^9，四层就是10^12数据量是十分庞大的，一般一张数据表不会有这么多的数据，所以一般B+树是不会超过四层的

4. 索引的分类

按照数据库中数据的存储方式可分为：聚簇索引和非聚簇索引
按照一个索引所对应的列可分为：单行索引和联合索引

4.1 聚簇索引

针对于逐渐所创建的索引称之为聚簇索引
InnoDB存储引擎会自动创建聚簇索引
聚簇索引的特点：

  • 1、使用记录主键值的大小进行记录和页的排序，数据页中的数据记录是按照主键递增顺序排成一个单链表，目录页中也是按照每个数据页的第一条数据的主键值的大小递增排序
  • 2、在聚簇索引中，B+树叶子结点存储的是一条完整的用户记录
  • 3、索引即数据，数据即索引

聚簇索引的优点：

  • 数据访问更快，一次可以加载一定范围内的有序数据，可以节省大量的IO操作的时间

聚簇索引的缺点：

  • 1、插入数据的速度严重依赖于插入的顺序
  • 2、更新主键的代价很高，可能需要将某一数据项从一个数据页中移动到另一个数据页，并且需要修改目录页

所以，一般情况下，主键都是自增的

MySQL中一般一张数据表只有一个聚簇索引，因为表中只能有一个主键

4.2 非聚簇索引

按照不同的数据列进行B+树的排序，比如学号字段，年龄字段等
非聚簇索引的特点：

  • 1、B+树叶子结点数据页中的数据按照创建索引的字段进行升序排序，这一点与聚簇索引相同

  • 2、非聚簇索引数据页中的数据项并非记录一条完整的用户记录，而是只记录部分列的值，一般是索引列 + 主键列

    1.  假设一张表有三个字段：id（主键），name，age，现在按照年龄创建索引<br />       <br />![](https://cdn.nlark.com/yuque/0/2022/jpeg/26710108/1647768431099-61257c5b-ac92-4241-a53b-05f3d94c0fc0.jpeg)<br />    为什么不记录完整的数据？<br />    为了节省空间，试想一下，在数据库中假设有1000000条数据，已经有一个聚簇索引了，记录了一百万条完整的数据，现在又要创建几个非聚簇索引（可以创建多个非聚簇索引），如果非聚簇索引也保存完整的数据信息，那么对空间的要求太高了，所以，为了节省空间，就只保留一部分的信息

  • 3、可以创建多个非聚簇索引，理论上来说可以对数据表中每一个可排序的字段都创建非聚簇索引，但不建议这么做

非聚簇索引的查询过程：
前面与聚簇索引相同，需要从根节点开始，从上往下一直找到叶子结点，在某一个数据页中精确找到某一条数据之后，由于非聚簇索引中存放的是部分信息，需要根据一条数据项中所存储的主键值去聚簇索引中查找这条数据的完整记录，这就是所谓的回表操作
所以对于非聚簇索引的查找效率比聚簇索引稍低一些，因为需要两次查询才能找出一条完整的记录

非聚簇索引下还有一个分支是联合索引，即按照多个字段进行排序，某个字段值相等就看另外的字段值

所以在InnoDB存储引擎下一般数据表的存储布局：由多棵B+树构成

4.3 索引的其他分类

  • 从逻辑上说，索引主要有4中：普通索引，唯一索引，主键索引和全文索引
  • 按照物理实现的方式分，索引有：聚簇索引和非聚簇索引
  • 按照作用字段的个数来分，索引主要有：单列索引和联合索引

    5 InnoDB下索引创建规则

    5.1 根页面万年不动

    在之前的叙述中，当一个数据页放满数据之后，会新创建一个数据页放新数据，这其实是不对的
    在InnoDB存储引擎下，真正的B+树的创建过程是（以聚簇索引为例）：
    1、当为某一张表创建B+树索引时，会自动创建一个根节点页面x
    MySQL索引 - 图3
    2、随着数据的增多，当根页面x放满后，如果还有数据要添加进来，InnoDB会先新建一个数据页y，将原来根页面中的所有数据项先拷贝到这个数据页y中，再新建一个数据页z存新插入的数据，然后将这两个数据页的目录存入根页面x中，这样根页面就成了目录页

3、随着数据的增多，当根页面中目录项也存满时，也会重复上面的操作，先新建一个数据页，将根页面中的所有数据拷贝到新的数据页中，再新建一个数据页，存放新插入数据的目录项，接着将这两个目录页构成的目录项存入根页面x中

4、所以不管怎么样，根页面x永远是B+树的一个根节点，一般来说，创建了根页面x后，x就常驻内存，节省一次IO

5.2 目录页中目录项记录的唯一性

当创建索引的那个字段值的重复率比较高的时候，免不了在排序之后，多个数据页中数据项的字段值是相等的（但一定是唯一的，因为还有主键的值，这里的字段指的是创建索引的那个字段值是相同的），这样创建出的目录项可能就会变成 [索引项1，数据页1]，[索引项2，数据页2]，索引项1 的值= 索引项2的值；这样查找到这一层级的目录页后，就无法确定到底要到哪个数据页中去查找数据，这样会降低查找的效率

所以在目录页中的目录项需要有区分度（目录项相同指的是目录项所记录的索引列的值相同，不包含后面记录的数据页，因为那个是查找目标），那么如何保证目录页中记录的唯一性呢，很简单，在创建目录项时，可以把主键的值加上，主键一定是唯一的

5.3 一个页面内至少存储两条数据

这很好理解，如果一个数据页只存一条数据，那查找就和顺序查找没什么区别了

6. MySQL下索引数据结构的选择

6.1 索引数据结构选择原则

从MySQL的角度来讲，不得不考虑的一个现实问题就是磁盘IO，如果所选择的索引结构能够尽量减少磁盘的IO操作，所消耗的时间也就越少，可以说，磁盘的IO操作次数对索引的使用效率至关重要，所以，MySQL衡量查询效率的标准就是磁盘IO次数

6.2 可供选择的数据结构

1. Hash结构

hash是通过某种确定性算法，将输入转变为输出，相同的输入永远能够得到相同的输出
hash结构的一个重要特点就是查询效率极高，比如Java中的HashMap，查找效率是O(1)，这比之前所介绍的B+树的查找效率还要高，因为B+树需要自顶向下依次查找，多次访问结点才能查找到目标数据

为什么不选择Hash结构作为索引的数据结构呢？
这与hash的特性有关，hash是在一个确定的key下才能找到其所对应的value，也就是说，如果以hash作为索引的数据结构，那么仅能够满足 =，<>等简单查询，如果进行范围查询，hash型索引的时间复杂度会退化为O(n)
另一个重要的原因就是Hash存储的数据是没有顺序的，因为它所计算出来的hashCode是随机的，如果想要使用Order By的话，就要对数据进行重新排序
再一个，对于联合索引的情况，Hash值是将联合索引键合并之后一起计算的，无法对单独的一个键或者几个索引键进行查询
最后，如果hash存储的键重复值过高，那么hash的效率就会降低，这是因为hash冲突会使用拉链法，将重复数据拉成一个链表，如果重复元素过多，那么这个链表会很长，查询的效率就会变低
在MySQL中，只有Memory存储引擎支持hash索引，MyISAM和InnoDB都不支持hash索引

2. 二叉搜索树

二叉搜索树的特征就是：中序遍历是有序的
比父节点小的结点存在左子树中，比父节点大的结点存在右子树中
二叉搜索树的查询规则就是：

  1. 如果key值大于根节点，则在右子树中进行查找
  2. 如果key值小于根节点，则在左子树中进行查找
  3. 如果key值等于根节点，返回结果

二叉搜索树的查找效率也很高，在O(logn)的复杂度，但却是不稳定的，因为对于一个有序的数组来说，就可能出现下面的情况
MySQL索引 - 图4
这样的话，查找就与顺序查找没什么区别，也并不能减少磁盘的IO次数

3. 平衡二叉树

根据二叉搜索树的缺陷，就引申出了平衡二叉树的概念，在二叉搜索树的基础上增加了一点约束
平衡二叉树是一棵空树，或者它左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是平衡二叉树。
这个限制就有效避免了二叉搜索树会退化成链表的情况

4. B树

B树是多路平衡查找树，它的每一个结点最多可以包含M个子结点，M称为B树的阶，每个结点中包括了关键字和子节点的指针
MySQL索引 - 图5
可以从B树的结构中看出来，每个结点既包含了指向子结点的指针，又包含了一些数据；
B树的索引过程，比如要找到9号元素：

  1. 先加载根节点，比较结点中的数据17和9的大小，17 > 9
  2. 将P1指针所指的结点加载到内存，依次比较其中的数据和9的大小 8 < 9，12 > 9
  3. 将P2指针所指的结点加载到内存中，查找9号元素

B树做查询的缺点就是查找效率不平衡，如果查找叶子结点中的数据，那么就需要多次IO，如果查找根节点中的数据，仅需要一次IO，并且将数据与指针放在一起也有可能浪费空间

7. 索引的设计原则

7.1 唯一性字段创建唯一索引

字段的数值有唯一性的限制，就可以创建唯一性索引，这样能够更快速地通过该索引来确定某条记录
比如一张学生表中有(学号，姓名，班级)字段，其中，学号字段有唯一性约束，那么就可以在学号字段上创建索引，这样可以很快速地确定某个学生的信息

  1. 在Alibaba的java开发手册中规定了：
  2. 业务上具有唯一特性的字段，即使是组合字段，也必须创建唯一性索引

7.2 频繁作为where条件的字段

如果某个字段在select语句的where条件中经常被使用到，那么就可以给这个字段创建索引，尤其是在数据量大的情况下，创建普通索引可以大幅提升数据查询的效率

7.3 经常作为group by和order by的列

group by是分组，order by是排序，在创建索引的时候，InnoDB会生成一棵B+树对数据按照索引排序，相同数据排完序之后就在相邻的位置，group by和order by的时候就不需要进行其他操作了

7.4 update和delete的where条件列

update和delete的先决条件就是得先找到这条记录，那么就可以对where条件后的字段创建索引，快速找到相应的记录，进行修改或者删除

7.5 Distinct字段需要创建索引

distinct（去重）
创建索引之后，相同值的数据都在相邻的位置，去重效率就会提高，不需要一个个进行比较

7.6 多表Join连接操作时，创建索引

  1. 在多表连接时，连接表的数量最好不要超过三张表，因为每增加一张表就相当于增加了一次嵌套循环，数量级增长非常快，会影响查询的效率
  2. 对where条件字段创建索引，因为where条件才是对数据条件的过滤，在数据量大的情况下，没有索引的话效率会很差
  3. 对于连接的字段创建索引，并且该字段在多张表中的类型必须一致，比如都为int类型；若数据类型不一致，那么可能会进行隐式的转换，当进行转换之后，索引就失效了

7.7 对字段类型占空间小的创建索引

类型大小指的是该类型表示的数据范围的大小，就比如int类型占4byte
在定义表结构时会显示的指定列的类型，以整型为例：有MEDIUMINT，INT，BIGINT等，它们所占据的存储空间依次递增，在创建索引时，尽量让索引列使用较小的类型，原因如下：

  • 数据类型越小在查询时进行的比较操作越快
  • 数据类型越小，索引占用的存储空间就越少，那么一个数据页中就可以存储更多条记录，从而减少IO来降级性能的损耗
  • 对于主键更加适用，因为除了聚簇索引，在非聚簇索引中都会存储一份记录的主键值，如果使用小的数据类型，就可以大大减少存储空间

7.8 使用字符串前缀创建索引

如果需要记录的字符串很长，那么存储这样一些字符串本身就需要占据极大的存储空间，当我们为这些字符串创建完整的索引，在B+树中就会有两个问题：

  • B+树索引需要把这样的字符串完整地存储起来，既费时又费空间
  • 在做字符串比较时，也很耗费时间

为了解决这样的情况，可以截取字符串的前几位建立索引，这就叫前缀索引；这样在查询的时候，虽然不能精确定位到记录的位置，但可以通过前缀相同的记录的主键值再回表查找完整的字符串
但对排序会有影响，因为只能匹配到前缀，无法比较前缀之后的字符串，如果前缀相同的字符串较多，那么就无法精确排序

7.9 区分度较高的列适合作为索引

区分度较高可以理解为，不重复的数据多，比如像学生学号这样能够精确定位到唯一学生的字段
这样的字段创建索引之后，能够精确地定位到某条数据，不需要再进行范围比较

7.10 不适合创建索引的情况

前面说了几种适合创建索引的情况，接下来再说说不能够创建索引的情况

  1. 在where条件中使用不到的字段不设置索引

用不到的字段创建索引只会浪费空间

  1. 数据量小的表不需要创建索引

一般数据量小的表，比如不到1000行数据的表，本身执行就已经很快了，创建索引反而会拖慢进度

  1. 有大量重复数据的字段不适合创建索引
  2. 避免对经常更新的字段创建索引，维护索引的成本很高
  3. 不建议使用无序的值作为索引，比如像身份证号，UUID等，插入新数据时，对B+树的改变大，维护成本页很高