Session 6 B+树索引

本章的辅助表

1
2
3
4
5
6
mysql> CREATE TABLE index_demo(
    ->     c1 INT,
    ->     c2 INT,
    ->     c3 CHAR(1),
    ->     PRIMARY KEY(c1)
    -> ) ROW_FORMAT = Compact;

比如要往下图的页插入记录(4, 4, 'a')（假设页的最大容量为3，实际上可以容纳几十到上百条记录）

image-20230721140313628

当分配新页时，新分配的数据页编号可能并不是连续的，也就是说我们使用的这些页在存储空间里可能并不挨着。

为了满足下一个数据页中用户记录的主键值必须大于上一个页中用户记录的主键值的要求，所以在插入主键值为4的记录的时候需要伴随着一次记录移动，也就是把主键值为5的记录移动到页28中，然后再把主键值为4的记录插入到页10中，这个过程的示意图如下：

img

这个过程表明了在对页中的记录进行增删改操作的过程中，我们必须通过一些诸如记录移动的操作来始终保证这个状态一直成立：下一个数据页中用户记录的主键值必须大于上一个页中用户记录的主键值。这个过程我们也可以称为页分裂。

为了根据主键值快速定位某些记录所在的页，我们需要给它们做个目录（这个目录有一个别名，称为索引），每个页对应一个目录项，每个目录项包括下面两个部分：

  • 页的用户记录中最小的主键值，我们用key来表示。
  • 页号，我们用page_no表示。

image-20230721141902326

设计InnoDB的大佬们需要一种可以灵活管理所有目录项的方式。他们灵光乍现，忽然发现这些目录项其实长得跟我们的用户记录差不多，只不过目录项中的两个列是主键和页号而已，所以他们复用了之前存储用户记录的数据页来存储目录项，为了和用户记录做一下区分，我们把这些用来表示目录项的记录称为目录项记录。

那InnoDB怎么区分一条记录是普通的用户记录还是目录项记录呢？别忘了记录头信息里的record_type属性。

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

image-20230721142302741

果此时我们再向上图中插入一条主键值为320的用户记录的话，那就需要分配一个新的存储目录项记录的页

image-20230721142509635

当记录量更大时，可以给这些存储目录项记录的页再生成一个更高级的目录，就像是一个多级目录一样，大目录里嵌套小目录，小目录里才是实际的数据。

image-20230721142545066

这样便形成了一种数据结构，它的名称是B+树

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

假设一个页放100条记录，那么4层结构就足以放1e8条记录了。

聚簇索引

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

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

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

  2. B+树的叶子节点存储的是完整的用户记录。

      所谓完整的用户记录，就是指这个记录中存储了所有列的值（包括隐藏列）。

  **我们把具有这两种特性的B+树称为聚簇索引**，所有完整的用户记录都存放在这个聚簇索引的叶子节点处。这种聚簇索引并不需要我们在MySQL语句中显式的使用INDEX语句去创建（后边会介绍索引相关的语句），InnoDB存储引擎会自动的为我们创建聚簇索引。

在InnoDB存储引擎中，聚簇索引就是数据的存储方式（所有的用户记录都存储在了叶子节点），也就是所谓的==索引即数据，数据即索引==。一个页面最少存储2条用户记录。

二级索引

聚簇索引只能在搜索条件是主键值时才能发挥作用，为了以别的列作为搜索条件，需要多建几棵B+树，不同的B+树中的数据采用不同的排序规则。比如我们使用的是c2列的大小作为B+树的排序规则，所以我们也称这个B+树为为c2列建立的索引。

image-20230721143958442

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

  • 使用记录c2列的大小进行记录和页的排序
  • B+树的叶子节点存储的并不是完整的用户记录，而只是c2列+主键这两个列的值。
  • 目录项记录中不再是主键+页号的搭配，而变成了c2列+页号的搭配。

以查找c2列的值为4的记录为例，在页42中可以快速定位到实际存储用户记录的页，但是由于**c2列并没有唯一性约束**，所以c2列值为4的记录可能分布在多个数据页中，又因为2 < 4 ≤ 4，所以确定实际存储用户记录的页在页34和页35中。

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

为这种按照非主键列建立的B+树需要一次回表操作才可以定位到完整的用户记录，所以这种B+树也被称为二级索引（英文名secondary index），或者辅助索引。

联合索引

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

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

以c2和c3列的大小为排序规则建立的B+树称为联合索引，本质上也是一个二级索引。它的意思与分别为c2和c3列分别建立索引的表述是不同的。

根页面不变

B+树的形成过程实际上是这样的：（自顶向下）

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

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

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

image-20230721150159303

如果我们想新插入一行记录，其中c1、c2、c3的值分别是：9、1、'c'，那么无法确定要插到哪页。

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

  • 索引列的值
  • 主键值
  • 页号

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

image-20230721150308585

MyISAM的索引方案

MyISAM的索引方案虽然也使用树形结构，但是却将索引和数据分开存储：

  • 将表中的记录按照记录的插入顺序单独存储在一个文件中，称之为数据文件。这个文件并不划分为若干个数据页，有多少记录就往这个文件中塞多少记录就成了。我们可以通过行号而快速访问到一条记录。

  • 使用MyISAM存储引擎的表会把索引信息另外存储到一个称为索引文件的另一个文件中。MyISAM会单独为表的主键创建一个索引，只不过在索引的叶子节点中存储的不是完整的用户记录，而是主键值 + 行号的组合。也就是先通过索引找到对应的行号，再通过行号去找对应的记录！

      这一点和InnoDB是完全不相同的，在InnoDB存储引擎中，我们只需要根据主键值对聚簇索引进行一次查找就能找到对应的记录，而在MyISAM中却需要进行一次回表操作，意味着**MyISAM中建立的索引相当于全部都是二级索引！**

  • 如果有需要的话，我们也可以对其它的列分别建立索引或者建立联合索引，原理和InnoDB中的索引差不多，不过在叶子节点处存储的是相应的列 + 行号。这些索引也全部都是二级索引。

InnoDB和MyISAM会自动为主键或者声明为UNIQUE的列去自动建立B+树索引，但是如果我们想为其他的列建立索引就需要我们显式的去指明。（为什么不自动为每个列都建立个索引呢？别忘了，每建立一个索引都会建立一棵B+树，每插入一条记录都要维护各个记录、数据页的排序关系，这是很费性能和存储空间的）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
CREATE TALBE 表名 (
    各种列的信息 ··· , 
    [KEY|INDEX] 索引名 (需要被索引的单个列或多个列)
)
ALTER TABLE 表名 ADD [INDEX|KEY] 索引名 (需要被索引的单个列或多个列);
ALTER TABLE 表名 DROP [INDEX|KEY] 索引名;

CREATE TABLE index_demo(
    c1 INT,
    c2 INT,
    c3 CHAR(1),
    PRIMARY KEY(c1),
    INDEX idx_c2_c3 (c2, c3) # 建立联合索引
);
ALTER TABLE index_demo DROP INDEX idx_c2_c3; #删除索引