B+ 树索引

一个简单的索引方案

在 InnoDB 数据页的结构 中讲到通过把页内记录分组，将每组最大记录的偏移量存入 Page Directory (页目录) 中，可以实现二分查找记录

页内的记录可以使用二分查找优化速度，但如果一个表过大导致一个页存放不下，就会将表存入多个页中，此时应该如何查询呢？遍历存放了该表记录的页，页内再通过二分查找？

虽然这也是一种方法，但无疑会非常慢！！回想一下页中记录是通过 next_record 形成一个根据主键递增的单向链表，但此时也是无法使用二分查找，但由于加入了 Page Directory (页目录) 就可以了

因为 Page Directory 类似于是一个数组，每个槽的大小为 2 字节，所以才可以二分查找。严格来说，我们二分查找的对象不是页中记录，也是 Page Directory 中存放的槽

页内可以这样优化，那么页间是否也可以这样照猫画虎呢？回想一下页与页的关系是什么？

从上图可以看出来，页与页是通过 File Header 中的两个前后指针连接起来，形成一个双向链表；页内记录与记录之间是通过 next_record 连接起来，形成一个有序的单向链表

是不是很像！！！没错，我们也可以为页建立一个目录，类似于为记录建立的 Page Directory。先通过为页建立的目录定位到待查询记录处于哪个页面，然后再去对应的页内查询

为了通过目录定位页的时候可以使用二分，页与页之间必须满足：下一个数据页中用户记录必须全部大于上一个数据页中所有用户记录。由于数据页内记录本来就已经有序，所以只需要满足下一个数据页中最小的记录都大于上一个数据页中最大的记录即可 (Infimum 和 Supremum 记录除外)

我们先建一个表：


create table index_demo (
    c1 int,
    c2 int,
    c3 char(1),
    PRIMARY KEY (c1)
) row_format=compact;

新建表的行格式为 COMPACT，关于 InnoDB 行格式详细介绍可见 InnoDB 行格式。为了后续画图简便，只保留行格式中最重要部分，而且竖着画。假设每页只能存 3 条记录，向表中插入一些记录后，如下图所示：

下面就开始为上图添加画龙点睛之笔，给它们编制一个目录，每个页都是一个目录项，目录项中包含两个部分

页的用户记录中最小的主键值，用 key 来表示 (注意和页中 Page Directory 的槽区分，槽中记录每个分组中最大的记录偏移量)
页号，用 page_no 来表示

查询一个记录有两个步骤：定位页 ➕ 定位记录。由于为页添加了目录，所以这两个步骤都可以使用二分查找

注意：目录还有一个别名 -> 索引 (点题)

InnoDB 中的索引方案

仔细观察上一部分的目录项结构，它像不像是有两个字段的记录：key 和 page_no。所以 InnoDB 并没有为目录项建立专门类型的页，而是和用户记录一样都是使用数据页

将上部分的图直接重构一波就变成了 InnoDB 中的索引方案：

注意看图中红色虚线框出来的地方，该位置表示记录的类型，1 表示 B+ 树非叶子节点的目录项记录，0 表示普通用户记录

由于目录项相比于用户记录来说字段更少，所以一个数据页能存放的目录项记录肯定比用户记录多，所以这里假设一个页可以存 4 条目录项记录

上图就是我们在很多地方都听过的 B+ 树，它的特点在于同层页通过双向链表连接，页面内记录通过单向链表连接，且同层页中所有纪录都保持递增的顺序。用户记录全部都存储在 B+ 树的叶子节点中，而目录项纪录都存储在 B+ 树的非叶子节点中

在一般情况下，B+ 树的层数不会超过 4 层，所以最多只需要做三次页定位和一次纪录定位即可查询到目标记录

$10^{11}$ 条用户记录

这里推荐一个可视化网站，可以模拟 B+ 树的变化过程 👉 B+ Trees

聚簇索引

聚簇索引又被称为主键索引，该索引是根据主键自动建立，它的效果和上一部分介绍的一模一样，叶子节点存放完整的用户记录 (包括隐藏列)，非叶子节点存放目录项纪录

在 InnoDB 中，聚簇索引就是数据的存储方式，也就是所谓的：索引即数据，数据即索引！！

二级索引

我们并非永远都是根据主键去查询，也有根据非主键字段去查询某个纪录的时候，这个时候可以为非主键字段建立一个新的索引。假设为 c2 字段建立一个索引：

在索引中，叶子节点是不完整的用户记录，只包含了索引列和主键，先根据索引列排序，如果索引列相同再根据主键排序；非叶子节点中依旧是目录项纪录，包含索引列、主键和页号

重点一：叶子节点存放不完整的用户记录，是为了节约空间，当查询到目标记录后，需要再根据主键回表，在聚簇索引中查询到完整的用户记录

重点二：非叶子节点中目录项记录必须包含主键，否则无法保证目录项纪录的唯一项，因为除了主键和添加唯一索引的字段，其它字段都无法保证没有重复值

联合索引

联合索引就是为多个列建立索引。假设为 c2 和 c3 两列建立联合索引，那么 B+ 树的排序规则为：

记录先按照 c2 排序
如果 c2 相同，再按照 c3 排列

其实联合索引本质上也是一种二级索引，叶子节点是不完整的用户记录，只包含了联合索引列和主键；非叶子节点中依旧是目录项纪录，包含联合索引列、主键和页号

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

根页面万年不动

当为某个表创建一个 B+ 树索引时，都会为这个索引创建一个根节点页面。一开始表为空，根节点页面中也没有纪录

向表中插入数据时，会先将用户记录存储到根页面中。当根页面满了后，先将根页面中的内容复制到新页中，然后对新页分裂成两个页，得到另外一个新页，最后将两个新页对应的目录项纪录插入到根页面中

可以看到根页面一开始存储用户记录，当满了后就开始存储目录项纪录，因为这棵 B+ 树会向下扩张，此时根页面不再是叶子节点，所以开始存储目录项纪录

之所以要让根页面不动，是为了始终都可以根据一开始设置的根页面访问到整棵 B+ 树，就不需要再更新根页面的位置

一页面至少存 2 条纪录

当每个页面只存 1 条记录时，整棵 B+ 树就退化成链表，无法优化查询速度！！

MyISAM 中的索引方案

前文说 InnoDB 的聚簇索引即包含了目录项纪录也包含了完整用户目录，前者存放在非叶子节点中，后者存放在叶子节点中，可被称为：索引即数据，数据即索引！！

MyISAM 的索引方案有些不同，虽然也是采用树形结构，但却是将数据和索引分开存储

数据文件：将表中所有数据按照插入顺序单独存放在数据文件中
索引文件：将表的索引信息单独存放到索引文件中

MyISAM 也会为主键单独创建一个索引，不同在于叶子节点存放的不再是完整用户记录，而是主键➕行号，通过行号可以在数据文件中找到对应记录的完整数据，相当于回表操作，类似于 InnoDB 的二级索引