B+树索引

2023-12-28 18:42:04

总结写前面如果都知道就不用看下面了：因为没用过MyISAM所以压根没看这玩意。

InnoDB存储引擎总结：

　　InnoDB存储引擎的索引是一棵B+树，，完整的用户揭露都存储在B+树第0层（从下往上数）的叶子节点中，其他层次的节点都属于内节点，内节点存储的是目录项记录。

　　InnoDB的索引分为两种：

　　　　聚簇索引(聚集索引)：以主键值的大小作为页和记录的排序规则，在叶子节点存储记录包含在表中的所有页。

　　　　二级索引：以索引列的大小作为页和记录的排序规则，在叶子节点存储记录的索引列和主键。

　　Innodb存储引擎的B+树根节点自创建起就不再移动。

　　在二级索引的B+树内节点中目录项由索引列的值，主键和页号组成。

　　一个数据页至少存储2条记录。

　　MyISAM存储引擎的数据和索引分开存储，这种引擎的索引全部都是二级索引，在叶子节点存储的是列+行号(对于定长记录格式的记录来说)

InnoDB数据页有7个部分组成，各个数据页可以组成一个双向链表，而每个数据页中的记录又可以组成一个单向链表，每个数据页都会为存储在它里边儿的记录生成一个页目录，在通过主键查找某条记录的时候可以在页目录中使用二分法快速定位到对应的槽，然后再遍历该槽对应分组中的记录即可快速找到指定的记录。

页和记录的关系的示意图如下：

没有索引的查找

本集的主题是索引，在正式介绍索引之前，我们需要了解一下没有索引的时候是怎么查找记录的。为了方便大家理解，我们下边先只唠叨搜索条件为对某个列精确匹配的情况，所谓精确匹配，就是搜索条件中用等于=连接起的表达式，比如这样：

SELECT [列名列表] FROM 表名 WHERE 列名 = xxx;

在一个页中的查找

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

以主键为搜索条件

这个查找过程我们已经很熟悉了，可以在页目录中使用二分法快速定位到对应的槽，然后再遍历该槽对应分组中的记录即可快速找到指定的记录。
以其他列作为搜索条件

对非主键列的查找的过程可就不这么幸运了，因为在数据页中并没有对非主键列建立所谓的页目录，所以我们无法通过二分法快速定位相应的槽。这种情况下只能从最小记录开始依次遍历单链表中的每条记录，然后对比每条记录是不是符合搜索条件。很显然，这种查找的效率是非常低的。

在很多页中查找

大部分情况下我们表中存放的记录都是非常多的，需要好多的数据页来存储这些记录。在很多页中查找记录的话可以分为两个步骤：

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

不论是根据主键列或者其他列的值进行查找，由于我们并不能快速的定位到记录所在的页，所以只能从第一个页沿着双向链表一直往下找，在每一个页中根据我们上边已经唠叨过的查找方式去查找指定的记录。因为要遍历所有的数据页，所以这种方式显然是超级耗时的，如果一个表有一亿条记录，使用这种方式去查找记录那要等到猴年马月才能等到查找结果。

InnoDB中的索引方案

Innodb复用了之前存储用户记录的数据页来存储目录项，为了和用户记录做一下区分，我们把这些用来表示目录项的记录称为目录项记录。

行格式记录头信息里的record_type属性

0：普通的用户记录
1：目录项记录
2：最小记录
3：最大记录

如图所示：

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

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

用户记录和目录项记录用的是一样的数据页（页面类型都是0x45BF，这个属性在Page Header中），页的组成结构也是一样一样的，都会为主键值生成Page Directory（页目录）以加快在页内的查询速度。所以现在根据某个主键值去查找记录的步骤可以大致拆分成下边两步，以查找主键为20的记录为例（因为都是从一个页中通过主键查某条记录，所以都可以使用Page Directory通过二分法而实现快速查找）：

先到存储目录项记录的页中通过二分法快速定位到对应目录项，因为12 < 20 < 209，所以定位到对应的记录所在的页就是页9.
从页9中根据二分法快速定位到主键值为20的用户记录。

因为存储目录项记录的页不止一个，所以如果我们想根据主键值查找一条用户记录大致需要3个步骤：

确定目录项记录页

我们现在的存储目录项记录的页有两个，即页30和页32，又因为页30表示的目录项的主键值的范围是[1, 320)，页32表示的目录项的主键值不小于320，所以主键值为20的记录对应的目录项记录在页30中。
通过目录项记录页确定用户记录真实所在的页。
在真实存储用户记录的页中定位到具体的记录。

我们的实际用户记录其实都存放在B+树的最底层的节点上，这些节点也被称为叶子节点或叶节点，其余的节点都是用来存放目录项的，这些节点统统被称为内节点或者说非叶节点。其中最上边的那个节点也称为根节点。

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

如果B+树只有1层，也就是只有1个用于存放用户记录的节点，最多能存放1000条记录。
如果B+树有2层，最多能存放1000×1000=1000000条记录。
如果B+树有3层，最多能存放1000×1000×1000=1000000000条记录。
如果B+树有4层，最多能存放1000×1000×1000×1000=1000000000000条记录。哇咔咔～这么多的记录！！！

你的表里能存放1000000000000条记录么？所以一般情况下，我们用到的B+树都不会超过4层，那我们通过主键去查找某条记录最多只需要做4个页面内的查找，又因为在每个页面内有所谓的Page Directory（页目录），所以在页面内也可以通过二分法实现快速定位记录。

聚簇索引

我们上边介绍的B+树本身就是一个目录，或者说本身就是一个索引。它有两个特点：

使用记录主键值的大小进行记录和页的排序，这包括三个方面的含义：

- 　　页内的记录是按照主键的大小顺序排成一个单向链表。
- 　　各个存放用户记录的页也是根据页中记录的主键大小顺序排成一个双向链表。
- 　　各个存放目录项的页也是根据页中记录的主键大小顺序排成一个双向链表。

　　2. B+树的叶子节点存储的是完整的用户记录。所谓完整的用户记录，就是指这个记录中存储了所有列的值。

　　ps: InnoDB存储引擎的表会存在主键（唯一非null），如果建表的时候没有指定主键，则会使用第一非空的唯一索引作为聚集索引，否则InnoDB会自动帮你创建一个不可见的、长度为6字节的row_id用来作为聚集索引。

我们把具有这两种特性的B+树称为聚簇索引，所有完整的用户记录都存放在这个聚簇索引的叶子节点处。这种聚簇索引并不需要我们在MySQL语句中显式的去创建，InnoDB存储引擎会自动的为我们创建聚簇索引。另外有趣的一点是，在InnoDB存储引擎中，聚簇索引就是数据的存储方式（所有的用户记录都存储在了叶子节点），也就是所谓的索引即数据。

二级索引

大家有木有发现，上边介绍的聚簇索引只能在搜索条件是主键值时才能发挥作用，因为B+树中的数据都是按照主键进行排序的。那如果我们想以别的列作为搜索条件该咋办呢？难道只能从头到尾沿着链表依次遍历记录么？

不，我们可以多建几棵B+树，不同的B+树中的数据采用不同的排序规则。

这个B+树与上边介绍的聚簇索引有几处不同：

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

联合索引

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

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

InnoDB中B+树索引的注意事项：

　　1. 根节点万年不动窝，实际B+树形成过程如下：

　　　　a. 为某个表创建一个B+树索引，（聚簇索引不是人为创造，默认存在）都会为这个索引创建一个根节点页面，没有数据的时候没有目录项，没有记录行。

　　　　b. 插入用户记录先把用户记录存在根节点。

　　　　c. 在根节点的可用空间用完时，此时会将根节点的所有记录复制到新分配的页(比如a)，然后对这个新页进行页分裂操作，得到另一个新页b。这时新插入的记录会根据键值（也就是聚簇索引中的键值或者二级索引中对应的索引列的值）的大小分配到页a或页b中。

　　根节点此时便升级为存储目录项记录的页，也就是把页a和页b对应的目录项记录插入到根节点中。

　　ps: 一个B+树索引的根节点自创建之日起便不会再移动，也就是页号不会再变化。这样只要我们创建一个索引，那么它根节点的页号便会记录到某个地方，后续InnoDB需要使用这个索引的时候都会从哪个固定的地方取出根节点的也好，从而访问这个索引。

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

　　　　a. 在B+树的内节点中，目录项记录的内容实际上是 “索引项列”+“主键值”+“页号”, 也就是把主键值页添加到二级索引内节点中的目录项记录中，这样就能保证B+树每一层节点中各条目录项记录除页号这个字段外是唯一的，

　　　　b. 不然如果这个索引项列都是a, 如何排序呢存放，如何把其放到正确的页里呢？

　　ps: 对于二级索引记录来讲，是先按照二级索引列的值来进行排序，在二级索引列值相同的情况下，再使用主键索引来进行排列，相当于二级索引列和主键还是一个联合索引。

　　　另外，对于唯一二级索引(当我们的某个列或列组合声明UNIQUE属性时，便会为这个列或列组合建立唯一二级索引)，也可能会出现多条记录键值相同的情况(一是声明为UNIQUE属性的列可能存储多个NULL值，二是因为MVCC)，

　　 唯一二级索引的内节点目录项页会包含记录的主键值。

　　3. 一个页面至少要容纳2条记录

　　　　为了避免B+树层级过高，Innodb要求所有的数据页至少可以容纳两条记录。