B+Tree 索引

没有索引我们是怎么查找数据的？

前面的文章说过，数据页中的记录会以主键大小顺序排列组成一个单向链表，并且还会给页中的记录进行分组，“组长”记录则放入页目录中，可以利用二分查找进行高效的搜索。

但是，如果我们的查找条件不含主键列，那么很遗憾，只能进行全表扫描，数据量大的时候，这是个很低效的行为。

一个简单的索引方案

在单个数据页中，因为记录之间是有序的，并且分组做了目录，所以能快速的进行查找。同理，也可以应用到多个数据页上。

首先，我们要保证夸数据页的记录，也是有顺序的，即下一个数据页中的最小用户记录的主键值要大于当前数据页中的最大用户记录的主键值。

然后，要给这些数据页建立 "目录" ，看图说话：

image-20250129122614173

虽然有点粗糙，但是聪明的你应该看得懂的。（这里的箭头想表达的是这些目录在物理上是连续的）

key代表数据页中最小用户记录的主键值；n_page代表页号，这样就能快速定位到记录所在的页。

也许你会发现一个现象，为什么页号不是连续的？MySQL 在进行页面编排的时候，并能承诺一定连续，但是会尽可能的保证它连续（后面表空间的时候会说）。

这里还需要讲解一个概念，页分裂：

新增和修改记录的操作都有很可能导致单页容量不够，此时就会申请新的数据页，将部分数据移动到新的数据页当中，保持结构的平衡。可以类比一下数组的插入操作，当在中间插入时，后续的元素都要进行移位。也就是说，中间位置的页面如果发生了改变，有可能会触发一系列的连锁反应，去维护整体的一个数据结构，造成性能的消耗。

Innodb 的索引方案

上文提到过的简单索引方案有很多的缺陷。随着记录的不断增加，那么会占用大量连续的存储空间，减慢了磁盘加载到内存的效率。而且当我们将某个页中的用户记录全部删除时，这个页没有存在的必要性了，这个时候如果删除其对应的目录项，其余目录项依次补位造成性能的消耗，如果不删除目录项，冗余也会浪费空间，且会减慢查找速度。

MySQL 是怎么做的呢？我们一步步看。

我们的想法就是，通过对主键值进行二分查找，找到一个目标记录。现在的问题是，单个页面内可以，但是多个页面就要涉及到页面的定位了。我们无非也是想通过二分查找的形式去定位页面，这是不是和定位用户记录非常像呢？实际上，MySQL 也是这么做的：

image-20250129132736455

我单独创建一个数据页，其中的记录用来存储页号和最小主键值不就行了嘛，在目录项数据页中，利用页目录实现二分查找，这个过程和存储用户记录的数据页相似，心智模型差不多。

现在让我们来看一下目录项数据页中记录和用户记录有那些不同，无非就是描述记录的元信息不一样嘛（记录头信息）：

  • record_type

    记录的类型不一样，用户记录也叫做普通记录，值为0；

    目录项记录的值是1。（前面也有提过）

  • min_rec_flag

    目录项数据页中最小的目录项记录会被添加该标记（后面有用）

剩下的，没什么不同的了，无非就是目录项记录的字段表示页号和最小主键值而已。

单页的大小是16kb，就算存储的是目录项记录，那么随着用户记录越来越多，还是会装不下：

image-20250129135047484

这幅图假设单个目录项数据页只能存放4条记录（实际能存储的内容很多的），现在我们面临的问题是无法在多个目录项数据页中快速定位到某个数据页（链表无法二分查找）。

很简单，往上在抽一层嘛：

image-20250129135615729

Ok，问题完美解决。

这很像一棵树，我们将这种结构称为B+树，一般来说2~3层足以容纳下海量的数据，最多不会超过4层。

为什么？

我们可以来算一下，假设数据页可以存储的最大记录数是100条：

  • 树的高度为0，最多100条数据
  • 树的高度为1，最多100 * 100条数据
  • 树的高度为2，最多100 * 100 * 100条数据
  • 树的高度为3，最多100 * 100 * 100 * 100条数据

谁家单表10亿条数据啊？（实际上存储的会比这个更多）

B+树的底层叫做叶子节点，存储的是用户记录，其余的非叶子节点，存储的是目录项记录。

还记得前面的min_rec_flag嘛？表示目录项数据页中最小的目录项记录。现在应该能猜到有什么用了吧。当需要给目录项数据页添加目录时，直接找到min_rec_flag的值为1的记录，将它的主键值“提上去”即可。

Page_Header中的Page_Level属性记录了当前页在树中的层级。

索引的分类

现在我们知道了，索引就是B+树，类似于现实生活中书的目录。

1、聚簇索引

有个比较经典的语句：“索引即数据，数据即索引”，描述的就是聚簇索引，这也是 Innodb 存储引擎对于数据页的组织形式。有两个特征：

  • 无论是数据页还是记录本身，都会按照主键值进行排序
  • 组成叶子节点的数据页中存储完整的用户记录，非叶子节点作为目录项数据页提供用户记录数据页的快速定位服务

2、二级索引

和聚簇索引其实差不多，本质上也是一棵B+树，不同的地方有三点：

  • 数据页或者记录本身，是按照索引列的大小进行排序的
  • 非叶子中记录存储的是索引列的值和页号
  • 叶子节点存储的是索引列的值和主键值

正因为叶子节点并没有存储完整的用户记录信息，所以还需要根据找到的主键值进行回表查询操作。

为什么不将完整的用户记录信息copy过来呢？

一是这样做会消耗大小的性能，插入一条数据的时候，要在多个索引文件中进行添加数据的操作，还有可能需要维护树的结构。二是数据冗余后，空间消耗较大，是原来的两倍。

3、联合索引

二级索引是为单个字段添加的索引，而联合索引是为多个字段一起添加的索引。比如为字段A和字段B添加一个联合索引，其含义就是，先以字段A进行排序，字段A的值相等，再比较字段B。相应的，建立的B+树的目录项数据页中存储的记录，就多了一个字段B。

注意事项

1、根节点的页号永不改变

一旦为某个字段创建了索引（主键由 MySQL 自动创建），MySQL 就会分配一个新的索引页作为B+树的根节点。刚开始插入数据的时候，直接插入到根节点中，如果根节点装不下了，就会申请一个新的数据页，对它进行页分裂操作，保证记录之间的顺序性，根节点升级为目录项数据页，存储用户记录数据页的页号和最小索引值。

整个过程中，根节点的页号永远不会发生改变，方便 Innodb 存储引擎根据数据字典（后面会说）找到根节点的页号。

2、非叶子节点记录的唯一性

之前描述的二级索引中关于目录项数据页中存储的记录字段不够完整。假设这么一种情况，你要为性别字段加上索引，你的B+树该怎么组织呢？

很显然，性别无非就是男或者女，也就是目录项数据页中的记录只会有两条，但是两条记录能指向多个页面嘛？显然是不行的。

为了确保非叶子节点记录的唯一性，实际上二级索引会隐式的转化为联合索引，联合主键字段一起构建B+树。当索引列值相同时，才比较主键值，这样就提供了唯一性的保障。

所以，实际上，只有两种索引，聚簇索引和联合索引（非聚簇索引）。

3、数据页至少容纳两条数据

如果一个数据页只装一条数据，那么就会产生频繁的页分裂操作，消耗性能，树的高度也会受到影响，极端情况下B+树退化成一个链表，而且访问一次数据页只能获得一条记录，不是很理想。所以，MySQL 规定，一个数据页至少放两条数据，减少副作用。

（这一点了解就行了，实际上单个数据页容纳的记录数还是很客观的，毕竟16KB嘛，就算是长文本，有溢出页做担保，再说了，很大的数据放在 MySQL 中，合适嘛？）

MyISAM 索引方案简介

这里简单的介绍一些，与 Innodb 不同，MyISAM 将索引与用户记录分开存储，放在不同的文件中，通过索引查找到对应的行号，拿到行号后去用户记录文件中获取数据。相当于一个二级索引，需要进行一次回表操作。而且，用户记录并没有进行排序，只是按照插入顺序排列，无法直接使用二分查找。

（了解一下就行了）

2025/01/29

writeBy kaiven