B+ 树索引

在 InnoDB 数据页章节，我们知道了每个数据页可以组成一个双向链表，而每个数据页中的记录会按照主键值从小到大的顺序组成一个单向链表。每个数据页都会为存储在它里面的记录生成一个页目录，再通过主键查找某条记录的时候可以在页目录中使用二分法快速定位到对应的槽，然后再遍历该槽对应分组中的记录即可快速找到指定的记录。页和记录的关系如下图所示：

没有索引时进行查找

没有索引时，怎么查找一条记录呢？这里给一个样例来看一下，为了方便理解，我们先简单复盘一下搜索条件为某个列等于某个常数的情况。

1	SELECT [查询列表] FROM 表名 WHERE 列名 = xxx;

在一页中查找

假设目前表中记录比较少，所有的记录都可以存放在一个页中。在查找记录时，可以根据搜索条件不同分为两种情况。

以主键作为搜索条件：通过在页目录中使用二分法快速定位到对应的槽，然后遍历该槽对应分组中的记录，即可快速找到对应的记录。
以其他列作为搜索条件：对非主键列的查找就主键列那么方便了，因为在数据页中并没有为非主键列建立所谓的页目录，所以无法通过二分法快速定位对应的槽。此时只能从 Infimum 记录开始一次遍历单向链表中每条记录，然后进行判断。可以看到这样的查找效率非常低。

在多页中查找

在大部分时候，表中存放的记录都是非常多的，需要用到多个数据页来存储这些记录，而在多个数据页中查找记录可以分为两个步骤：

定位到记录所在的页
从所在的页内查找相应的记录

在没有索引的情况下，无论是根据主键还是其他列进行查找时，我们不能快速地定位到记录所在的页，所以只能从第一页沿着双向链表一直往后找。在每一页中按照上面在一页中查找的方式去寻找指定的记录。因为要遍历所有的数据页，使用这种查询方式，代价是巨大的。为了能实现高效的搜索，“索引”上线了。

索引

为了方便讲解，先创建一个示例表：

CREATE TABLE index_demo (c1 INT,
	c2 INT,
	c3 CHAR (1) ,
	PRIMARY KEY (c1) ) ROW_FORMAT = COMPACT;

把一些记录放到页里面的示意图如下：

一个简单的索引方案

思考一下，为什么我们根据某个条件查找一些记录时，需要遍历所有的数据页呢？因为每个页中的记录虽然是从小到大的，但是页和页之间没有规律，记录可能存在交叉，无法快速定位到匹配的记录都在哪些数据页中。那能不能仿照数据页的页目录一样，再建立一个目录，这个目录配合数据页目录完成，在建立这个目录时，需要完成以下两件事：

下一个数据页中用户记录的最小主键值必须大于上一个页中用户记录的最大主键值。为了避免主键值在页内排序正常，但是在整个所有页中来看，存在交叉排序的情况。
举个栗子，现在往 index_demo 表中插入 3 条数据。
1
INSERT INTO index_demo VALUES(1, 4, 'u'), (3, 9, 'd'), (5, 3, 'y');
此时这些记录已经按照主键值的大小串成一个单向链表了，如下所示：
我们假设一页最多存放 3 条记录，此时我们再插入一条记录。
1
INSERT INTO index_demo VALUES(4, 4, 'a');
此时页结构如下图所示：
这里分配的新页页号是 12？为什么不是 11？因为，新分配的数据页编号并不一定连续，它们只是通过维护上一页和下一页的编号而建立了链表关系。再让我们回头看看上面的图，此时新页中的最小主键值为 4，而页 10 的最大主键值为 5，5>4，此时违反了我们上面提到的“下一个数据页中用户记录的主键值必须大于上一个页中用户记录的主键值”的要求，所以此时应该要做一次记录移动，把主键为 5 和主键 4 的位置进行调换。此时的步骤如下：
- 插入时发现需要进行转移，此时先把主键值为 5 的记录移动到页 12。
- 再将主键值为 4 的记录插入到页 10。
这个过程表明，在对页中的记录进行增删改操作时，必须通过一些诸如记录移动的操作来始终保证这个状态一直成立：下一个数据页中用户记录的最小主键值必须大于上一个页中用户记录的最大主键值。
给所有的页建立一个目录项。
由于数据页编号不一定是连续的，所以在向 index_demo 表中插入许多记录后，可能会形成如下局面：
由于这些大小为 16KB 的页在磁盘上可能并不挨着，如果想从这么多页中根据主键值快速定位某些记录所在的页，就需要给它们编制一个目录，每个页对应一个目录项，每个目录项包括下面两个部分：
- 页的用户记录中最小的主键值，用 key 来表示；
- 页号，用 page_no 表示。
所以为上面几个页编制的目录如图所示：
以页 12 为例，它对应目录项 2，目录项中包含该页页号以及用户记录中最小主键值。我们只需要把几个目录项在物理存储器上连续存储，例如把它们放在一个数组中，就可以实现根据主键值快速查找某条记录的功能了。比如我们想查找主键值为 20 的记录，查找过程如下：
1. 先从目录项中根据二分法快速确定主键值为 20 的记录在目录项 3 中，因为 (12<20) ，对应的页是 3.
2. 再根据前文讲的在页中查找记录的方式去页 3 中定位具体记录。
至此，针对数据页编制的简易目录就完成了。这个目录别名称为“索引”。

InnoDB 中的索引方案

上一小节，我们构建了一个简易的索引方案，但是这里我们做了假设，所有目录项都可以在物理存储器上连续存储，这样做会有以下几个问题：

InnoDB 使用页作为管理存储空间的基本单位，最多只能保证 16KB 的连续存储空间。 虽然一个目录项占用不了多大的存储空间，但是随着记录增多，目录项所占用的连续存储空间页越来越大，这样的设计是不现实的。
我们对记录经常进行增删改操作，假设我们把页 10 的记录全部删除，页 10 也就没了存在的必要，这也就意味着目录项 1 也没存在的必要，需要把目录项 1 后的目录项都向前移动一下，即便不移动，将其作为冗余存放在目录项列表中，也浪费了大量空间。这种牵一发而动全身的设计不是什么好设计。

所以 InnoDB 在设计时，发现目录项和用户记录长得很像，只不过目录项中两个列是主键和页号而已，所以他复用了之前存储用户记录的数据页来存储目录项。为了与用户记录取份，这些用来表示目录项的记录称为目录项记录。那么如何区分呢？在 InnoDB 数据页章节讲解的记录头信息中的 record_type 属性，现在完整讲解一下：

0：普通用户记录
1：目录项记录
2：Infimum 记录
3：Supremum 记录

此时目录项记录如下：

从图中可以看出，我们新分配了一个编号为 30 的页来专门存储目录项记录。这里再次强调一下目录项记录和普通用户记录的区别：

目录项记录的 record_type 值是 1，而普通用户记录的 record_type 值是 0。
目录项记录只有主键值和页的编号两个列，而普通用户记录的列是用户自己定义的，可能包含很多列，另外还有 InnoDB 自己添加的隐藏列。
只有目录下记录的 min_rec_flag 属性才可能为 1，普通用户记录的 min_rec_flag 属性都是 0。

除上述区别外，它们没有其他区别了，它们用的是一样的数据页 (也没类型都是 0x45BF，这个属性在 File Header 中) ；页的组成结构也是一样；都会为主键值生成 Page Directory，从而在按照主键值进行查找时可以使用二分法来加快查询速度。虽然说目录项记录中只存储主键值和对应的页号，比用户记录需要的存储空间小多了，但是毕竟是一个页只有 16KB 大小，能存放的目录项记录也是有限的。如果表中数据太多，以至于一个数据页不足以存放所有的目录项记录，该怎么办？当然是再来一个存储目录项记录的页了。为了方便理解，如图所示：

从图中可以看出，在插入 3 条主键值分别为 101、120、138 的用户记录后，产生了新的数据页，但其实此时只要新插入 1 条数据也会产生新数据页：

为存储该用户记录而新产生了页 18；
因为存储目录项记录的页 30 已满，所以不得不创建一个新的页 32 来存放 31 对应的目录项目录。

现在如果想查找主键值为 20 的 1 条用户记录，则大致需要 3 个步骤。具体如下：

确定存储目录项记录的页。
现在有两个目录项记录，页 30 和页 32。因为页 30 的目录项记录主键值范围是[1, 101)，页 32 的范围是 [101, ∞)，所以主键值 20 的记录应当记录在页 30 中。
通过存储目录项记录的页确定用户记录真正所在的页。
在真正存储用户记录的页中定位到具体的记录。

那么问题来了，在步骤 1 中，我们需要定位存储目录项的页，但是这些页在存储空间中也不可能紧挨着。如果表中数据非常多，则会产生很多存储目录项记录的页，那怎么根据主键值快速定位一个存储目录项记录的页呢？同之前的原理一样，为这些页在生成一个更高级的目录，像多级目录一样。

此时再看着像不像一个树结构，这样的结构我们称为 B+ 树。

InnoDB 规定最下面的那层 (也就是存放用户记录的那层) 为第 0 层，之后层级依次往上加。在上面的样例中，我们做了个非常极端的假设：一页最多存放 3 条记录。但其实在真实环境中，一个页存放的记录数量是非常大的。假设所有存放用户记录的叶子节点所代表的数据页可以存放 100 条用户记录，所有存放目录项记录的内节点所代表的数据页可以存放 1000 条目录项记录，那么：

如果 B+ 树只有 1 层，也就是只有 1 个用于存放用户记录的节点，则最多能存放 100 条用户记录；
如果 B+ 树有 2 层，最多能存放 $1,000 * 100 = 100,000$ 条用户记录；
如果 B+ 树有 3 层，最多能存放 $1,000 * 1,000 * 100 = 100,000,000$ 条用户记录；
如果 B+ 树有 4 层，最多能存放 $1,000 * 1,000 * 1,000 * 100 = 100,000,000,000$ 条用户记录。

一般表里很少会超过 10000000000 条记录，所以一般情况下，MySQL 的 B+ 树都不会超过 4 层。这样一来，通过主键值去查找某条记录时，最多需要 4 个页面查找，3 个存储目录项记录的页和 1 个存储用户记录的页。每个页面都存在 Page Directory，所以在页面内也可以通过二分法快速定位。

在讲解数据页的 Page Header 部分时介绍过一个名为 PAGE_LEVEL 的属性，它就代表这个数据页作为节点在 B+ 树中的层级。

聚簇索引

B+ 树本身是一个庞大的目录，或者本身就是一种索引，它有以下两个特点：

使用记录主键值的大小进行记录以及页的排序。
- 页内的记录按照主键值大小顺序排成一个单向链表，通过二分法快速定位。
- 存放用户记录的页也是根据页中用户记录的主键大小顺序排成一个双向链表。
- 存放目录项记录的页分为不同的层级，在同一层级中的页也是根据页中目录项记录的主键大小顺序排成一个双向链表。
B+ 树的叶子节点存储的是完整的用户记录。 所谓完整的用户记录，就是指这个记录存储了所有列的值 (包括隐藏列) 。

二级索引

但是可以通过上述内容发现一个问题，一直在讲主键，但是我们工作中还会用到一些非主键索引，那面对非主键索引是怎么处理的呢？

InnoDB 会多建几棵 B+ 树，不同的树中采用不同的排序规则。比如我们可以用 C2 列的大小作为数据页，然后再建一棵 B+ 树，如图所示：

这个 B+ 树和主键的 B+ 树存在几处不同：

这里采用了 C2 列的大小进行记录和页的排序。
- 页内的记录按照 C2 列的大小顺序排成一个单向链表。
- 各个存放用户记录的页也是根据页中记录 C2 列的大小顺序排成一个双向链表。
- 存放目录项记录的页分为不同的层级，同一层级中的页也是根据页中目录项记录的 C2 列大小顺序排成一个双向链表。
这里 B+ 树的叶子节点存储的并不是完整的用户记录，而只是 C2 列的值和主键值。
目录项记录中不再是主键和页号的映射，而变成了 C2 列和页号的搭配。

现在假如我们查找 C2=4 的记录，可以利用刚刚建好的 B+ 树。这里的 C2 列没有唯一性约束，所以满足 C2=4 的记录可能有很多条，具体看看下列的查找过程：

确定第一条符合 C2=4 条件的目录项记录所在的页。
根据根页面快速定位到符合条件的目录项记录所在的页为 42 (2<4<9) 。
通过第一条符合 C2=4 条件的目录项记录所在的页面确定第一条符合 C2=4 条件的用户记录所在的页。
根据页 42 可以快速定位到符合条件的目录项记录所在页为 34 或者 35 (2<4≤4) =) 。
在真正存储第一条符合 C2=4 条记的用户记录的页中定位到具体的记录。
到页 34 和页 35 中定位具体的用户记录 (如果在页 34 中使用页目录定位到第一条符合条件的用户记录，就不需要再到页 35 中使用页目录去定位第一条符合条件的用户记录了) 。
这个 B+ 树的叶子节点只存储了 C2 和 C1 两个列。在这个 B+ 树叶子节点处定位到第一条符合的用户记录后，再根据记录中的 C1 主键信息到聚簇索引中再查找到完整用户记录。这个过也称为回表。然后再返回到这棵 B+ 树的叶子节点处，找到刚才定位到的符合条件的那条用户记录，并沿着记录组成的单向链表向后继续搜索其他也满足 c2=4 的记录，每找到一条的话就继续进行回表操作 . 重复这个过程，直到下一条记录不满足 c2 斗的这个条件为止。

因为这种以非主键列的大小为排序规则而建立的 B+ 树需要执行回表操作才可以定位到完整的用户记录，所以这种 B+ 树也称为 二级索引 (Secondary Index) 或辅助索引。

为什么还需要一次回表呢？直接把完整的用户记录放到叶子节点不就好了吗？
这样做确实可以提升性能，但是太耗费空间了。索引少并且表字段不多的情况下可能不明显，但是当表中的索引或者表字段过多，每个索引都需要完整的用户记录，这样太浪费存储空间了。
迄今为止，我们一直讨论的聚簇索引或者二级索引其值都是数字，那如果是字符或者字符串呢？
别忘了字符串同样可以根据字符集和比较规则完成大小比较。

联合索引

我们可以同时以多个列的大小作为排序规则，也就是同时为多个列建立索引。比如我们想让 B+ 树按照 C2 和 C3 列的大小进行排序，这里包含两层含义：

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

为 C2 和 C3 列建立索引，示意图如下：

联合索引需要注意以下两点：

每条目录项记录都由 C2、C3、页号这三部分组成。记录先按照 C2 列进行排序，如果 C2 列相同，再按照 C3 列排序。
B+ 树叶子节点处的用户记录由 C2、C3、C1 这三部分构成。

这样的索引称为联合索引，也称为复合索引。它本质上是一个二级索引，索引列包括 C2、C3。需要注意，”以 C2 和 C3 列的大小为排序顺序规则建立联合索引”和“分别为 C2 和 C3 列建立索引”是完全不同的两个概念。不同点如下：

建立联合索引指挥建立一棵 B+ 树。
分别建立索引，会建立两棵 B+ 树。

B+ 树索引的注意事项

根页面万年不动

前面在介绍 B+ 树索引的时候，为了方便理解，我们先把存储用户记录的叶子节点都画出来，然后再画出存储目录项记录的内节点。实际上 B+ 树的形成过程是下面这样的：

每当为某个表创建一个 B+ 树索引 (聚簇索引不是人为创建的，它默认就存在) 时，都会为这个索引创建一个根节点页面。最开始表中没有数据的时候，每个 B+ 树索引对应的根节点中既没有用户记录，也没有目录项记录。
随后向表中插入用户记录时，先把用户记录存储到这个根节点中。
在根节点中的可用空间用完时继续插入记录，此时会将根节点中的所有记录复制到一个新分配的页 (比如页 a) 中，然后对这个新页进行页分裂操作，得到另一个新页 (比如页 b) 。这时新插入的记录会根据键值 (也就是聚簇索引中的主键值，或二级索引中对应的索引列的值) 的大小分配到页 a 或页 b 中。根节点此时便升级为存储目录项记录的页，也就需要把页 a 和页 b 对应的目录项记录插入到根节点中。

在这个过程中，需要特别注意的是，一个 B+ 树索引的根节点自创建之日起便不会再移动 (也就是页号不再改变) 。这样只要我们对某个表建立一个索引，那么它的根节点的页号便会被记录到某个地方，后续凡是 InnoDB 存储引擎需要用到这个索引时，都会从那个固定的地方取出根节点的页号，从而访问这个索引。

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

在 B+ 树的内节点中，目录项记录的内容是索引列加页号的组合，但是这个组合对二级索引来说有点不严谨。假设有个数据表 test 如下：

c1	c2
1	1
2	1
3	1
4	1

假设我们针对 C2 列做了二级索引，此时二级索引的 B+ 树如下：

如果我们现在想插入一条记录，C1=5；C2=1，那么通过上面的 B+ 树，我们应该将这条记录插入哪个页呢？通过页 3 也就是根目录 (内节点) ，我们出现了分歧，无法判断了！

为了让新记录知道自己该插入哪个页，需要保证 B+ 树同一层内节点的目录项记录除了页号这个字段以外是唯一的。所以二级索引的内节点的目录项记录的内容实际上是由 3 部分构成的：

索引列的值
主键值
页号

也就是我们把主键值也添加到二级索引内节点中的目录项记录中，这样就能保证内节点中除了页号这个字段外是唯一的。实际上二级索引的 B+ 树是这样的。

对于二级索引来说，是先按照二级索引列的值进行排序，在二级索引值相同的情况下，再按照主键值进行排序。所以，为 C2 列建立索引其实相当于为 (C2，C1) 列建立了一个联合索引。另外，对于唯一二级索引 (当我们为某个列或列组合声明 UNIQUE 属性时，便会为这个列或列组合建立唯一二级索引) 来说，也可能会出现多条记录键值相同的情况 (一是声明为 UNIQUE 属性的列可能存储多个 NULL 值，二是我们后面要讲的 MVCC 服务) ，唯一二级索引的内节点的目录项记录也会包含记录的主键值。

一个页面至少容纳两条记录

B+ 树的一个核心特性是所有的数据记录都存储在叶子节点，而内节点则用来存储指向这些叶子节点的指针。这种结构使得 B+ 树非常适合执行范围查询，因为可以通过顺序访问叶子节点来快速访问连续的数据记录。B+ 树的高度通常很低，这意味着大多数操作 (如插入、删除、查找) 都可以在很少的磁盘 I/O 操作中完成。

如果一个大的目录中只存放一个子目录是啥效果呢 ? 那就是目录层级会非常多，而且最后那个存放真正数据的目录中只能存放一条记录。InnoDB 通过要求每个数据页至少能存放两条记录，避免了许多潜在的性能问题。这种设计策略有助于保持 B+ 树的高度较低，提高查询效率，同时确保数据的存储密度和访问速度。

MyISAM 中索引方案简介

我们知道，在 InnoDB 中索引即数据，也就是聚簇索引的那棵 B+ 树的叶子节点中已经包含了所有完整的用户记录。MyISAM 的索引方案虽然也使用树形结构，但是却将将索引和数据分开存储。

将表中的记录按照记录的插入顺序单独存储在一个文件中 (称之为数据文件) 。这个文件并不划分为若干个数据页，有多少记录就往这个文件中塞多少记录。这样一来，我们可以通过行号快速访问到一条记录。
由于没有和 InnoDB 一样按照主键大小排序，所以在数据中无法使用二分法快速定位。
将表中的索引单独存储在一个文件中 (称之为索引文件) 。MyISAM 会为表的主键单独创建一个索引，只不过在索引的叶子节点中存储的不是完整的用户记录，而是主键值和行号的组合。也就是通过索引找到对应的行号，再通过行号去找对应的记录！
在 InnoDB 中我们只需要根据主键值对聚簇索引进行一次查找就能找到对应的记录，而在 MyISAM 中需要一次回表，这意味着 MyISAM 中建立的索引相当于全部是二级索引！
MyISAM 的行格式有定长记录格式 (Static) 、边长记录格式 (Dynamic) 、压缩记录格式 (Compressed) 等。
Static 记录格式可以使用行号轻松算出某条记录在数据文件中的地址偏移量了。但是变长记录格式就不行了，MyISAM 会直接在索引叶子节点处存储该条记录在数据文件中的地址偏移量。由此可以看出，MyISAM 的回表操作是十分快速的，因为它是拿着地址偏移量直接到文件中取数据，而 InnoDB 是通过获取主键之后再去聚簇索引中找记录，虽然说也不慢，但还是比不上直接用地址去访问。

简单来说，InnoDB 是“索引即数据，数据即索引”的处理方式，而在 MyISAM 中却是“索引是索引，数据是数据”。

MySQL 中创建和删除索引

InnoDB 和 MyISAM 会自动为主键或者带有 UNION 属性的列建立索引。如果想为其他列创建索引就需要我们显示地指明了。

可以在创建表时，指定需要建立索引的单个列或者建立联合索引的多个列：

1	CREATE TABLE 表名 (各个列信息 , (KEY\|INDEX) 索引名 (需要被索引的单个列或多个列));

也可以在修改表结构时添加索引：

1	ALTER TABLE 表名 ADD (INDEX\|KEY) 索引名 (需要被索引的单个列或多个列);

也可以在修改表结构时删除索引：

1	ALTER TABLE 表名 DROP (INDEX\|KEY) 索引名;