MySQL学习(3)B+树索引是如何快速查询的_索引查询数据innodb,b+tree 数上怎么查询

前言

我们已经知道在磁盘中，有很多索引页，这些页并非在物理结构上相连接，而是通过双向链表关联。如果要查找一条数据，需要通过页目录中的槽，通过二分法定位到分组再进行遍历查找。比如下面这样：

SELECT [查询列表] FROM 表名 WHERE 条件;
1

假设表中只有一个页，在查找记录时，可以根据搜索条件的不同分为两种情况。

• 以主键作为搜索条件：根据页目录使用二分法快速定位槽，然后遍历该槽对应分组中的记录，即可找到对应记录。
• 以其他列作为搜索条件：按照页中数据next_record形成的单向链表，挨个儿遍历。

然而正常情况下，表中的记录是很多的，这些记录会存放在很多页中，现在查找记录可以分为两个步骤。

1. 沿着页的双向链表定位记录所在的页
2. 从该页中便利查找到记录

不管是主键查找还是非主键查找，都涉及到大量的遍历操作，如果表记录非常多时，所花费的时间会很长。这时候就需要用到索引了。

先建一个表：

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

什么是索引

前面提到，COMPACT行格式的记录头信息中有一项属性record_type表示记录的类型，其中0表示普通记录，2表示Infimum记录，3表示Supremum记录，重要的是1表示B+树非叶子节点的目录项记录。

记录放在页里简易图如下所示：

要想实现索引必须保证两件事情：

1. 一个页中的用户记录都按照大小依次串连成单链表，下一个索引页中的最小用户记录的主键值必须大于上一个页中最大用户记录的主键值
2. 给所有的页建立目录项

在对页中的记录进行增删改操作时，必须通过一些诸如记录移动的操作来维护第1条成立，使下一页用户记录最小的主键值大于上一页用户记录最大的主键值，这个过程称为页分裂。还需要模仿页目录的模式，对所有的页建立目录，每个页对应一个目录项，每个目录项有两个组成部分：

• key：页中最小记录主键值
• page_no：页号

满足这两个条件后，可以通过二分查找发，快速定位到所查询主键属于哪个目录项对应的页中，再根据页目录查找到指定记录。这样的一个目录就是索引。

理想是丰满的，如果记录非常多的时候，我们经常对记录进行增删改，时常造成大量的记录迁移，又或者不迁移，那会造成很多存储空间浪费。

InnoDB中的索引

InnoDB中的这个目录项叫做目录香记录，它与普通记录的结构一样，且具有主键和页号两个列，不同之处在于它的record_type和min_rec_flag属性。目录项记录和普通的记录的区别如下：

存放目录项记录的页和存放普通记录的页没有区别，都是一样的FIL_PAGE_INDEX索引页，页的组成结构也没有不同，都会为主键生成页目录，从而根据槽快速查找。

这下查询的步骤变成了，

1. 先去目录项记录的页，通过二分法找到用户记录所在的页的页号；
2. 去指定页号，通过槽找到记录。

如果表中的记录非常多，目录项记录也非常多时，就会有更多的页存储目录项的页，这时候再生成一个更高级的目录，去对应下级的目录项记录的页。这就是一个多级目录，最底层的才是用户记录。如下图所示：

这种数据结构就叫做B+树，无论是存放用户记录的索引页，还是存放目录项记录的索引页，都是B+树上的节点。

一个B+树可以分为好多层，最下面的那层，也就是存放用户记录的那层为第0层，往上依次加1。Page Header中PAGE_LEVEL属性就表示这个页作为节点在B+树中的层级。

聚簇索引

记录的存储默认就是一个索引，就是一个B+树，满足以下条件：

• 使用记录主键值的大小进行记录和页的排序
  • 页（包括叶子结点和非叶子结点）内的记录按照主键的大小顺序排成一个单向链表，页内的记录被划分成若干组，每个组中主键值最大的记录在页内的偏移量在页目录中被记录成槽。
  • 各个存放用户记录的页根据记录的主键大小排序排成一个双向链表。
  • 存放目录项的页（也就是非叶子结点）分为不同层级，同一层级中的页根据目录香记录的主键大小排序排成一个双向链表。
• 叶子结点存储的是完整的用户记录，包含了用户定义的列和隐藏列。

在InnoDB中，聚簇索引就是数据的存储方式。所有的完整的用户记录都存放在这个聚簇索引的叶子结点处。简单来说，按记录的主键建立的索引，就是聚簇索引，不需要人为创建，默认就存在，数据默认就是按这种方式存储的。

二级索引

聚簇索引只能在搜索条件是主键值时才有作用，如果想搜索其他列，可以使用其他的列作为排序规则，建立B+树。如下所示以c2列建立B+树。

新建的B+树有如下特点：

• 使用记录c2列的大小进行记录和页的排序，规则与聚簇索引差不多，将主键换成c2列
• B+树的叶子结点存储的并不是完整的记录，而是c2列+主键这两列
• 目录项记录中使用c2列+主键+页号

有了这个新建的B+树，当使用c2列作为搜索条件查询记录时

1. 确定第一条符合条件的目录项记录所在的页
2. 找到目录项，并确定第一条符合条件的用户记录所在的页
3. 在这个用户记录的页中定位到第一条符合条件的用户记录
4. 根据这个记录的主键值再到聚簇索引中查找完整的用户记录，这个过程叫回表。重复这个过程，直到下一条记录不满足条件为止。

为什么要回表？为了节省空间，二级索引中叶子结点没有存储完整的记录。

二级索引目录项中实际还有一列主键，为了方便记录在插入时，保证非叶子结点目录香记录的唯一性。

要注意的是，由于列不是唯一的，所以在判断第一条记录所在的页是，要往小的猜，比如目录项为2和4的两个目录项指向的页，第一条符合值为4的列可能在前者的页中，要从前开始判断，直到找到第一条为止。

联合索引

同时为多个列建立索引就是联合索引，按照建立索引的顺序，依次排序。

• 每条目录香记录包含所有索引列、主键和页号组成，按照索引列顺序依次排序
• B+树叶子结点的用户记录有所有索引列和主键组成

联合索引本质也是二级索引，不同于分别为不同列建立索引的地方是：

• 建立联合索引只会建立一颗B+树
• 分别为列建立索引时，会分别去建立不同的B+树

每次建立B+树索引时，都会为这个索引创建一个根节点页面，当有记录插入时，先存储到这个根节点，此时以来页目录就可完成快速查询。当数据越来越多，超出页容量时，会新申请两个页将记录复制到新的页中，根节点此时升级为存储目录项的页，把刚刚新的页对应的目录香记录插入到根节点中。当数据越来越多时，用户记录的节点会再次把记录复制到新的页，并将自己升级为存储目录项的页。这个过程类似于所有的树枝都是从树根长出的。

InnoDB为了避免B+树的层级增长过高，要求所有索引页都至少存放2条记录。

MyISAM中的索引简介

在InnoDB中，索引即数据，也就是聚簇索引的B+树已经存储了完整记录。MyISAM的索引虽然也是树形结构，但是索引和数据是分开存储的。

• 记录按照插入顺序单独存储在数据文件，这个文件不分组，有多少记录就添加多少记录，通过记录的行号快速访问到一条记录。
• 索引单独存储到索引文件中，MyISAM会为主键创建一个索引，在索引的叶子结点处存储的是主键值和行号。
  1. 先通过索引找到对应的行号
  2. 再通过行号找对应的记录

由于主键索引也需要回表查询，MyISAM中的索引相当于全部都是二级索引。当行格式采用定长记录格式（Static）时，每条记录占用的存储空间是固定的，可以轻松通过行号找到记录，但是变长记录格式（Dynamic）则是在索引叶子结点处存储记录的地址偏移量。总的来说，MyISAM的回表速度是非常快的，尽管InnoDB也不算慢，但是比不上直接用地址去访问。

如何创建索引

InnoDB和MyISAM会自动为主键或UNIQUE属性的列建立索引，如果想为其他列建立索引，需要显示声明。每建立一个索引都会建立一个B+树，而且每增删改一条记录，都要维护页中记录的排序，耗费性能和存储空间。

在创建表时，可以指定需要建立索引的列：

CREATE TABLE 表名(
	列...,
	(KEY|INDEX)索引名（需要被索引的单个列或多个列）
);
1
2
3
4

其中KEY和VALUE任选一个即可。

在修改表结构的时候添加索引：

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

还可以在修改表结构的时候删除索引：

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

例如，为上表c2和c3列添加一个联合索引：

CREATE TABLE index_demo(
	c1 INT,
	c2 INT,
	c3 CHAR(1),
	PRIMARY KEY(c1),
	INDEX idx_c2_c3 (c2, c3)
);
1
2
3
4
5
6
7

删除c2和c3联合索引：

ALTER TABLE index_demo DROP INDEX idx_c2_c3;
1

添加c2索引：

ALTER TABLE index_demo ADD INDEX idx_c2 (c2);
1

使用图形界面更便捷，例如Navicat，在设计表中，进入索引编辑页，即可添加或修改索引：

总结

InnoDB中索引即数据，数据即索引；MyISAM中索引是索引，数据是数据。

InnoDB中索引分为两种：

• 聚簇索引：以主键值的大小作为页和记录的排序规则，在叶子节点存储完整记录，在非叶子节点存储主键+页号。
• 二级索引：以索引列的大小作为页和记录的排序规则，在叶子节点处存储记录的索引列+主键，在非叶子节点存储索引列+主键+页号。

InnoDB的B+树根节点自创建起就不再移动，只会分裂出叶子节点。

一个索引页至少存储2条记录。

MyISAM的数据和索引分开存储，在叶子节点存储列+行号（或地址偏移量）。