一、为什么要使用索引

MySQL中数据是存储在文件系统的，数据是以何种形式保存，决定了取得时要以何种方式获取

MySQL执行流程图.png

1、安装顺序保存

如果现在要找7这一行，需要从1开始一行一行找，直到找到7为止，这样等于7次IO操作，这样读取是很耗时的

安装顺序保存.png

2、使用 二叉树 数据结构进行存储

二叉树数据结构.png

二、索引

1、索引概论

• MySQL官方索引的定义为：索引（Index）是帮助 MySQL 高效获取数据的数据结构。
• 索引的本质: 索引是数据结构。可以简单理解为排好序的快速查找数据结构，满足特定查找算法。这些数据结构以某种方式指向数据，这样就可以在这些数据结构的基础上实现 高级查询算法

2、索引的优点

• 1、类似大学图书馆建书目索引，提高数据检索的效率，降低 数据库的IO成本，这也是创建索引最主要的原因
• 2、通过创建唯一索引，可以保证数据库表中每一行 数据的唯一性
• 3、在实现数据的参考完整性方面，可以 加速表和表之间的连接。也就是说，对于有依赖关系的子表和父表联合查询时，可以提高查询速度
• 4、在使用分组和排序字句进行数据查询时，可以显著 减少查询中分组和排序的时间，降低了 CPU 的消耗

3、索引的缺点

• 1、创建索引和维护索引要 耗费时间，并且随着数据量的增加，所耗费的时间也会增加
• 2、索引需要 磁盘空间，除了数据表占数据空间之外，每一个索引还要占一定的物理空间，存储在磁盘上，如果有大量的索引，索引文件就可能比数据文件更快达到最大文件尺寸
• 3、虽然索引大大提高了查询速度，同时却会 降低更新表的速度。当对表中的数据进行增加、删除和修改的时候，索引也要动态地维护，这样就降低了数据的维护速度

三、InnoDB中的索引

1、索引设计

• 创建表

新建 book 表，表中有 2 个 INT 类型的列，1个VARCHAR类型的列，并且规定 id列为主键，使用 Compact 行格式来实际存储记录

CREATE TABLE `book`
(
    `id`   INT NOT NULL AUTO_INCREMENT COMMENT '主键',
    `page` INT NOT NULL DEFAULT '1' COMMENT '页数',
    `name` VARCHAR(200) DEFAULT NULL COMMENT '书名',
    PRIMARY KEY (`id`)
) ENGINE = InnoDB
  DEFAULT CHARSET = utf8mb4
  ROW_FORMAT = COMPACT
  COLLATE = utf8mb4_0900_ai_ci COMMENT ='书籍';

• Compact 行格式 Compact 行格式.png

• record_type：记录头信息的一项属性，表示记录的类型

  • 0：表示普通记录
  • 1：表述数据项记录
  • 2：表示最小记录
  • 3：表示最大记录

• next_record：记录头信息的一项属性，表示下一条地址相对于本条记录的地址偏移量，我们用箭头来表明下一条记录是谁

• 各个列的值：这里只记录 book 表中的 3 个列，分别是 id，page 和 name

• 其他信息：除了上述3 种信息以外的所有信息，包括其他隐藏列的值以及记录的额外信息

2、MySQL 的页

MySQL中的数据是一条一条记录来存储的，并且会把满足一定大小（16k）的数据保存到一个页中

• book 数据 book 数据.png
• 数据在也中存储 页中存储数据.png

• 查询数据

在根据某个搜索条件查询一些记录时为什么要遍历所有的数据源？因为各个页中的记录并没有规律，我们并不知道与搜索条件匹配的数据在哪些页中，所以不得不依次遍历所有的数据页。所以如果我们 想快速的定位到需要查找的记录在哪些数据页 中该怎么办？我们可以为快速定位记录所在数据页而 建立一个目录，建立这个目录必须要完成以下事

• 建立目录
  • 下一个数据页中用户记录的 主键值 必须大于上一个页中用户记录的主键值。（这就是为什么在创建主键是最好是使用数字，而不是使用字符串，hash值等等）
    页中存储数据.png

SELECT *
FROM book
WHERE id = 3;

• 当查询id为3的数据时，由于现在只有一个数据页而且数据存储时是使用id从左到右依次增大，当查询id=3时数据只需要使用二分法就可以确定，找到结果后返回数据

3、数据项

随着数据的增多，一页数据无法保存下来所有数据，所以需要把数据保存到新页，当有2个页时，如果查找id=5时的数据时，需要从第一页中的左侧开始依次向右侧遍历查询，如果在第一页中没有找到就在第2页中再从左到右遍历继续寻找，直到遍历完所有数据。这样遍历全部数据效率太低，为了解决这个问题引入了数据项

• 数据项与数据页都是使用页的结构，只是存储的内容不同而已。数据项中存储的是数据页中的最左侧数据的id和数据页的页数

• 第一步:复制数据页0，生成一个数据页1。因为数据页的根是不变的，同时把数据页0改成数据项类型，因为现在数据页0存储的不再是数据，而是存储的是数据页 复制数据页0.png

• 第二步：创建新的数据页2 image.png
• 第三步：当数据项满时，创建新的数据项 新建数据项.png

4、通过id来查询数据

• 查询id=8的数据

SELECT *
FROM book
WHERE id = 8;

• 分析
  • 当前已经分为3层，首先从根页开始查询，首先从根页0开始找，通过根页0找到页4
  • 通过根页4中数据的 二分法 由于id=8 大于7所以找到页3
  • 在页3中通过 二分法 找到id=8的数据返回

5、索引

通过上面的分析查找，渐渐形成了一个数型的目录页，这个目录有个别名，称为 索引。

6、小结 image.png

• 目录项记录和用户记录的不同点

  • 目录项记录 的 record_type值是1，而普通用户记录 的 record_type值是0
  • 目录项记录只有 主键值和页的编号 两个列，而普通的用户记录的列是用户自己定义的，可能包含很多列，另外还有InnoDB自己添加的隐藏列
  • 记录头信息里还有一个叫 min_rec_mask 的属性，只有在存储 目录项记录 的页中的主键值最小的 目录项记录 的 min_rec_mask 值为 1 ，其他别的记录的 min_rec_mask 值都是 0

• 两者用的是一样的数据页，都会为主键值生成 Page Directory （页目录），从而在按照主键值进行查找时可以使用 二分法 来加快查询速度。

7、B+Tree

一个B+树的节点其实可以分成好多层，规定最下边的那层，也就是存放我们用户记录的那层为第 0 层，
之后依次往上加。之前我们做了一个非常极端的假设：存放用户记录的页 最多存放3条记录 ，存放目录项
记录的页 最多存放4条记录 。其实真实环境中一个页存放的记录数量是非常大的，假设所有存放用户记录
的叶子节点代表的数据页可以存放 100条用户记录 ，所有存放目录项记录的内节点代表的数据页可以存
放 1000条目录项记录

• 如果B+树只有1层，也就是只有1个用于存放用户记录的节点，最多能存放 100 条记录
• 如果B+树有2层，最多能存放 1000×100=10,0000 条记录
• 如果B+树有3层，最多能存放 1000×1000×100=1,0000,0000 条记录
• 如果B+树有4层，最多能存放 1000×1000×1000×100=1000,0000,0000 条记录。相当多的记
  录！！！

三、常见的索引概念

索引按照物理实现方式，索引可以分为2种：聚簇索引和非聚簇索引。通常也把非聚簇索引称为二级索引或者辅助索引

1、聚簇索引

1.1、聚簇特点

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

1.2、聚簇优点

• 数据访问更快 ，因为聚簇索引将索引和数据保存在同一个B+树中，因此从聚簇索引中获取数据比非聚簇索引更快
• 聚簇索引对于主键的 排序查找 和 范围查找 速度非常快
• 按照聚簇索引排序顺序，查询显示一定范围数据的时候，由于数据都是紧密相连，数据库不用从多个数据快中提取数据，所以 节省了大量的IO操作

1.3、聚簇缺点

• 插入速度严重依赖于插入顺序，按照主键的顺序插入是最快的方式，否则将会出现页分裂，严重影响性能。因此，对于 InnoDB 表，我们一般都会定义个 自增的ID列为主键
• 更新主键的代价很高，因为将会导致被更新的行移动。因此，对于 InnoDB表，我们一般定义主键为不可更新
• 二级索引访问需要两次索引查找，第一次找到主键值，第二次根据主键值找到行数据

1.4、聚簇限制

• 对于 MySQL 数据库目前只有InnoDB数据引擎支持聚簇索引，而 MyISAM 并不支持聚簇索引
• 由于数据物理存储排序方式只能有一种，所以每个 MySQL 的 表只能有一个聚簇索引。一般情况下就是该表的主键来作为聚簇索引
• 为了充分利用聚簇索引的聚簇的特性，所以 InnoDB表的主键列优先 选用有序的顺序id，而不建议用无序的id，比如：UUID、MD5、HASH、字符串等列作为主键无法保证数据的顺序增长

四、二级索引（辅助索引、非聚簇索引）

聚簇索引 只能在搜索条件是 主键值 时才能发挥作用，因为 B+树中的数据都是按照主键进行排序的。如果想用别的列作为搜索条件该怎么办？肯定不能是从头到尾沿着链表依次遍历记录一遍。我们可以为改搜索条件创建一个 B+树，不同的B+树中的数据采用不同的排序规则。如以 页数page列的大小为数据页、页中记录的排序规则

1、以page列的大小为数据页建立二级索引B+树 二级索引.png

• 使用page = 560 为条件来查询

SELECT *
FROM book
WHERE page = 560;

• 查询过程

  • 1、page=560，会从以page作为索引的B+树中查询
  • 2、从页5中查询到只有一条数据找到第9页
  • 3、在页9中通过 二分查找 找到数据项360-7和 560-8这两条路径
  • 4、通过 360-7找到页7，从页7中找到page=560一条数据
  • 4.1、由于需要查询book表的全属性id，page， name 但是此时没有 name 属性，需要通过id来回表，查询出全部属性
  • 4.2、通过 id=5，从聚簇索引中查询到数据返回
  • 5、通过 560-8找到页8
  • 5.1、在页8中找到一条数据项记录560-8
  • 5.3、通过回表 id=8，从聚簇索引中查询到数据返回
• 返回结果 image.png

2、该二级索引的B+树与聚簇索引的B+树的不同

• 使用记录C2列（page属性）的大小进行记录和页的排序，这包括 3 个方面的含义

  • 1、页内的记录是按照C2列的大小顺序排成一个单向链表
  • 2、各个存放 用户记录的页 也是根据页中记录的C2列大小顺序排成一个 双向链表
  • 3、存放 目录项记录的页 分为不同的层次，在同一层次中的页也是根据页中目录记录的C2列大小顺序排成一个 双向链表

• B+树的叶子节点存储的并不是完整的用户记录，而只是 C2列 + 主键 这两个列的值

• 目录项记录中不再是 主键 + 页号 的搭配，而变成了 C2列 + 页号 的搭配

3、回表概念

根据这个以C2列大小排序的B+树只能确定我们要查找记录的主键值，所以如果我们想根据C2列的值查找到完整的用户记录的话，仍然需要到 聚簇索引 中再查询一遍，这个过程就称为 回表。也就是根据 C2列的值查询一条完整的用户记录需要使用到 2 棵B+树

• 直接把完整记录放到叶子节点就可以省去 回表操作了，为什么不这样设计？

把完整记录保存到叶子节点这样的设计 太占用地方了，相当于每创建一个棵 B+ 树都需要把所有的用户记录再都拷贝一遍，这就太浪费存储空间了

• 聚簇索引和非聚簇索引 聚簇索引和非聚簇索引.png

4、小结：聚簇索引与非聚簇索引的原理不同，在使用上也有一些区别

• 1、聚簇索引的 叶子节点 存储的就是我们的 数据记录，非聚簇索引的叶子节点存储的是 数据位置。非聚簇索引不会影响数据表的物流存储顺序
• 2、一个表 只能有一个聚簇索引，因为只能有一种排序存储的方式，但可以有 多个非聚簇索引，也就是多个索引目录提供数据检索
• 3、使用聚簇索引的时候，数据的 查询效率高，但如果对数据进行插入、删除、更新等操作，效率会比非聚簇索引低。

五、联合索引-特殊的二级索引

除了以主键做索引以及使用一个非主键列做索引外，还可以使用多个非主键列一起做索引，我们称为联合索引或复合索引。如我们想让 C2列和C3列的大小进行排序，这个包含两层含义

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

1、联合索引（C2列+C3列） 联合索引.png

• 每条 目录项记录 都由 C2、C3、页号 这三个部分组成，各条记录先按照 C2列的值进行排序，如果记录的C2列相同，则按照C3列的值进行排序
• B+树 叶子节点 处的用户记录由 C2列、C3列和主键列 组成

2、InnoDB的B+树索引的注意事项

2.1、根页面位置万年不动

• 每当为某个表创建一个B+树索引（聚簇索引不是人为创建的，默认就有）的时候，都会为这个索引创建一个 根节点 页面。最开始表中没有数据的时候，每个B+树索引对应的 根节点 中既没有用户记录，也没有目录项记录

• 随后向表中插入用户记录时，先把用户记录存储到这个 根节点 中

• 当根节点中的可用 空间用完时 继续插入记录，此时会将根节点中的所有记录复制到一个新分配的页，比如页a中，然后对这个新页进行页分裂的操作，得到另一个新页，比如 页b。这时新插入的记录根据键值（也就是聚簇索引中的主键值，二级索引中对应的索引列的值）的大小就会被分配到 页a或页b中，而 根节点便升级为存储目录项记录的页

• 一个 B+树索引的根节点自诞生之日起，便不会再移动。这样只要我们对某个表建立一个索引，那么它的根节点的页号便会被记录到某个地方，然后凡是 InnoDB 存储引擎需要用到这个索引的时候，都会从那个固定的地方取出根节点的页号，从而来访问这个索引

2.2、内节点中目录项记录的唯一性

由于B+树索引的内节点中目录项记录的内容是索引列 + 页号 的搭配，但是这个搭配对于二级索引来说有点不严谨。

• 索引列 + 页搭配的二级索引不严谨
  

  C2列建立二级索引的B+树.png

• 如果想新插入一行记录，其中 C1、C2、C3的值分别为：9、360、数据结构，那么在修改这个为C2列建立的二级索引对应的B+树时便碰到了个大问题：由于页9中存储的目录项记录是由C2列 + 页号 的值构成的，页9中的两条目录项记录对应的C2列的值都是 360，而我们 新插入的这条记录 的C2列的值也是 360，那我们这条新插入的记录到底应该放到 页7中，还是应该放到 页8中？

• 为了让新插入记录能找到自己在那个页里，我们需要 保证在B+树的同一层内节点的目录项记录除页号这个字段以外是唯一的。所以对于二级索引的内节点的目录项记录的内容实际上是由三个部分组成的：

  • 1、索引列的值
  • 2、主键值
  • 3、页号

• 把 主键值也添加到二级索引内节点的目录项记录，这样就能保证B+树每一层节点中各条目录项记录除页号这个字段外是唯一的，所以我们为C2列建立二级索引后的示意图实际上应该是这样：

  image.png

2.3、一个页面最少存储2条记录

• 一个B+树只需要很少的层级就可以轻松存储数亿条记录，查询速度相当不错。这是因为B+树本质上就是一个大的多层级目录，每经过一个目录时都会过滤掉许多无效的子目录，直到最后访问到存储真实数据的目录。那如果一个大的目录中只存放一个子目录是个啥效果？那就是目录层级非常非常多，而且最后的那个存放真实数据的目录只能存放一条记录。费了半天劲只能存放一条真实的用户记录？所以 InnoDB的一个数据页至少可以存放两条记录

六、MyISAM中的索引

主键索引.png 非主键索引.png

• MyISAM的索引方式都是“非聚簇”的，与InnoDB包含1个聚簇索引是不同的

1、 MyISAM 与 InnoDB对比

• ① 在InnoDB存储引擎中，我们只需要根据主键值对 聚簇索引 进行一次查找就能找到对应的记录，而在MyISAM 中却需要进行一次 回表 操作，意味着MyISAM中建立的索引相当于全部都是 二级索引
• ② InnoDB的数据文件本身就是索引文件，而MyISAM索引文件和数据文件是 分离的 ，索引文件仅保存数据记录的地址
• ③ InnoDB的非聚簇索引data域存储相应记录 主键的值 ，而MyISAM索引记录的是 地址 。换句话说，InnoDB的所有非聚簇索引都引用主键作为data域
• ④ MyISAM的回表操作是十分 快速 的，因为是拿着地址偏移量直接到文件中取数据的，反观InnoDB是通过获取主键之后再去聚簇索引里找记录，虽然说也不慢，但还是比不上直接用地址去访问
• ⑤ InnoDB要求表 必须有主键 （ MyISAM可以没有 ）。如果没有显式指定，则MySQL系统会自动选择一个可以非空且唯一标识数据记录的列作为主键。如果不存在这种列，则MySQL自动为InnoDB表生成一个隐含字段作为主键，这个字段长度为6个字节，类型为长整型
  image.png

2、 索引的代价

• 空间上的代价

每建立一个索引都要为它建立一棵B+树，每一棵B+树的每一个节点都是一个数据页，一个页默认会
占用 16KB 的存储空间，一棵很大的B+树由许多数据页组成，那就是很大的一片存储空间

• 时间上的代价

每次对表中的数据进行 增、删、改 操作时，都需要去修改各个B+树索引。而且我们讲过，B+树每
层节点都是按照索引列的值 从小到大的顺序排序 而组成了 双向链表 。不论是叶子节点中的记录，还是内节点中的记录（也就是不论是用户记录还是目录项记录）都是按照索引列的值从小到大的顺序
而形成了一个单向链表。而增、删、改操作可能会对节点和记录的排序造成破坏，所以存储引擎需要额外的时间进行一些 记录移位 ， 页面分裂 、 页面回收 等操作来维护好节点和记录的排序。如果我们建了许多索引，每个索引对应的B+树都要进行相关的维护操作，会给性能拖后腿