InnoDB B+树索引

[Jimmy2Angel]

MySQL 作为最（bu）流（yao）行（qian）的开源数据库，性能高、成本低、可靠性好，其中一部分原因离不开其支持的 MyISAM、InnoDB、Memory 等多种存储引擎。不同的存储引擎管理的表的存储结构可能不同，采用的存取算法也可能不同，本文基于目前 MySQL 默认的存储引擎 InnoDB 对数据的存储及索引进行简单的介绍。

InnoDB 索引页结构

页简介

页 是 InnoDB 管理存储空间的基本单位，一个页的大小一般是 16kb。InnoDB 针对不同功能设计了许多不同类型的 页，例如表空间头部信息页、Undo日志页、段信息页以及本文的主角 索引页。

索引页

每个 索引页 包含以下几个部分：

• File Header，表示页的一些通用信息，占固定的38字节。每个数据页的 File Header 部分都有上一个和下一个页的编号，所以所有的数据页会组成一个双向链表。

• Page Header，表示数据页专有的一些信息，占固定的56个字节。

• Infimum + Supremum，两个虚拟的伪记录，分别表示页中的最小和最大记录，占固定的26个字节。

• User Records：真实存储我们插入的记录的部分，大小不固定。

• Free Space：页中尚未使用的部分，大小不确定。

• Page Directory：页中的某些记录相对位置，也就是各个槽在页面中的地址偏移量，大小不固定，插入的记录越多，这个部分占用的空间越多。

• File Trailer：用于检验页是否完整的部分，占用固定的8个字节。

用户记录在索引页中的存储

上面介绍了 索引页 的几个部分，其中 User Records 部分就是用来储存用户写入的记录，但是一开始生成页的时候是没有这一部分的，当用户第一次写入记录的时候，会自动从 Free Space 中申请一个记录大小的空间划分到 User Records 中，当 Free Space 被用完之后还需要写入数据，就需要去申请一个新的 索引页。

每个记录的头信息中都有一个 next_record 属性，从而使页中的所有记录串联成一个单链表。需要注意的是：

• 索引页 中存在的 Infimum 和 Supremum 代表页中的最小和最大记录，当不存在用户数据的时候，它们也是存在的。

• Infimum 的 next_record 指向第一条用户记录。

• 最后一条用户记录的 next_record 指向 Supremum。

• 这样从 Infimum 到用户记录再到 Supremum 就形成了一个单向链表。

• 最重要的是，页内的用户数据是按主键值大小进行排序的。

当用户删除一个记录的时候：

• 该记录并没有从存储空间中移除，而是把该条记录的 delete_mask 值设置为 1。
• 该记录的 next_record 值变为了0，意味着该记录没有下一条记录了。
• 该记录的上一条记录的 next_record 指向了该记录的下一条记录。

当数据页中存在多条被删除掉的记录时，这些记录的 next_record 属性将会把这些被删除掉的记录组成一个垃圾链表，以备之后重用这部分存储空间。

Page Directory（页目录）

上面介绍了用户记录在 索引页 中按主键值大小排序形成一条单向链表，那么用户按照主键去查找某条记录的时候，从 Infimum 开始往后依次查找即可。当页中的记录较少的时候没有问题，但是当页中有很多记录的时候这么查找的性能就有问题了。

为了缩小查找的范围，InnoDB 设计了一个分组的概念，将页中的记录分成多个组，每个组中记录数量有限，那么如果能定位到要查找的记录在哪个组的话，再遍历该组的记录链表即可。

分组的相关信息如下：

• 没有用户记录的时候，Infimum 是第一个组，Supremum 是第二个组

• 插入用户记录的时候，都会从 页目录 中找到主键值比本记录的索引列值大并且差值最小的槽

• 在一个组中的记录数等于 8 个后再插入记录时，会将该组拆分成两个组，一个组 4 条记录，另一个 5 条记录

• 对于最小记录所在的分组只能有 1 条记录，最大记录所在的分组拥有的记录条数只能在 1~8 条之间，剩下的分组中记录的条数范围只能在是 4~8 条之间

• 每个组的最后一条记录（也就是组内最大的那条记录）的头信息中的 n_owned 属性表示该记录拥有多少条记录，也就是该组内共有几条记录

现在分组有了，那么怎么定位到用户记录在哪个分组呢？InnoDB 又设计了一个 槽 的概念（也就是一个目录的概念）：

• 将每个组的最后一条记录的地址偏移量单独提取出来按顺序存储到靠近 页 的尾部的地方，这个地方就是所谓的 Page Directory，也就是 页目录。
• 页面目录中的这些地址偏移量被称为 槽（英文名：Slot），所以这个页面目录就是由 槽 组成的。
• 其实也就是说每个 槽 对应一个分组中的最后一条记录。

那么现在问题就解决了，要在一个页中按索引列查找一个记录的话，步骤如下：

1. 在 Page Directory 上通过二分查找即可定位到要查找的记录所在的分组。
2. 虽然不知道该分组的第一个记录，但是可以通过前一个分组的最后一条记录的 next_record 找到。
3. 然后从该分组的第一条记录开始，通过 next_record 遍历该分组内的记录链表即可。

File Header

File Header 针对各种类型的页都通用，也就是说不同类型的页都会以 File Header 作为第一个组成部分，它描述了一些针对各种页都通用的一些信息，比方说这个页的编号是多少，它的上一个页、下一个页是谁。这里我们关注 FIL_PAGE_PREV 和 FIL_PAGE_NEXT。它们是上一个页面和下一个页面的页号。这样页与页之间就形成了一个 双向链表，为什么会有多个页呢？那肯定是一个页中的记录太多了啊，导致了 页分裂。

总结

• 用户记录在页中按索引列大小排序形成单向链表

• 页中的记录划分为多个分组

• Page Directory 中存放每个分组最后一条记录的地址偏移量

• 用户在单个页内查找记录过程：先二分查找定位分组，再遍历分组内记录

InnoDB 索引

前面介绍了单个 索引页 内记录的存储情况，但是当用户记录非常多的时候，索引页 肯定也不止一个，这个时候要查找一个记录的话，需要先定位到记录所在的页，然后再通过前面介绍的单页面查找方式进行查找。

InnoDB 索引从逻辑角度可以划分为主键索引（聚簇索引）、二级索引和联合索引等。

聚簇索引

InnoDB 会为主键自动创建聚簇索引，也就是一个 B+ 树，树的每一个节点都是一个上文所说 索引页，我们称叶子节点为数据页（存储用户数据），非叶子节点为目录项页（定位到数据页）。目录项页中存储的每个记录是 主键+页号。通过页号可以找到下一个层次的一个目录项 A，主键值就是目录项 A 中最小的主键值。

这样一来，我们想要通过主键查找一条用户记录的话:

1. 通过根节点中的主键比对，然后通过页号导航到下一层次的目录项页
2. 然后再从该目录项页导航到下下一层目录项页，直到抵达叶子结点，也就是一个数据页
3. 再然后就可以通过上文所说的单页面查找方式查找。

这个 B+ 树有两个特点：

1. 使用记录主键值的大小进行记录和页的排序
   • 页内的记录根据主键值大小排序形成 单向链表
   • 目录项页分为不同层次，同一层次的目录项页按照主键值大小排序形成 双向链表
   • 数据页也按主键值大小排序形成 双向链表
2. 叶子结点中存储完整的用户记录，也就是存储了所有列的值（包括隐藏列）

我们把具有这两个特点的索引称为聚簇索引，由于叶子节点存储完整的用户记录，所有索引即数据，数据即索引。

二级索引

上面所说的聚簇索引只适用于搜索条件是主键的情况，那么搜索条件不是主键的话怎么办呢？例如搜索条件是索引列 c2 的话，其实也会创建一个 B+ 树，与聚簇索引不同的是：

• 使用 c2 列值的大小进行记录和页的排序

  • 页内的记录根据 c2 列值大小排序形成一个 单向链表
  • 目录项页分为不同层次，同一层次的目录项页根据 c2 列值大小排序形成一个 双向链表
  • 存放用户记录的数据页也是根据 c2 列值大小排序形成一个 双向链表

• 目录项记录中不再是 主键+页号 的搭配，而变成了 c2列+页号 的搭配

• 叶子节点存储的并不是完整的用户记录，而只是 c2列+主键 这两个列的值

其实在目录项中不仅有 c2 列和页号，也会有主键，防止添加记录时由于和目录项记录中 c2 列值相同导致不知道应该放在那个页中。

这样我们按索引列 c2 搜索用户记录时：

1. 先从该 B+ 树索引中获取到主键值
2. 再用主键值去聚簇索引中查找记录（回表操作）

由于该 B+ 树索引的叶子节点只存储主键值，搜索数据时需要回表查找完整用户记录，所以该索引称为二级索引或辅助索引。

联合索引

我们也可以为多个列建立联合索引，以列 c2 和 c3 为例，排序规则为先按 c2 列排序，c2 列相同时按 c3 列排序。

与上面说到的二级索引一样，目录项页存的是 索引列+主键+页号，数据页存的是 索引列+主键。因此也可能需要回表操作。为什么说的是可能呢？因为如果我们的查询列（就是我们要 select 的列）就是 c2，那么该联合索引中本身就存了 c2 列值，也就不需要回表查找了。

B+ 树的形成过程

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

B+ 树索引

上文所说的聚簇索引、二级索引等是从逻辑角度划分的，其实都是 B+ 树索引。下面说说 B+ 树索引的适用范围以及如何挑选索引列。

适用范围

以联合索引 idx_name_birthday_phone 为例，会先按 name 排序，name 相同按 birthday 排序，birthday 相同按 phone 排序。

全值匹配

SELECT * FROM person_info WHERE name = 'Ashburn' AND birthday = '1990-09-27' AND phone = '15123983239';

查询过程为：

• 因为 B+ 树的页和记录先是按照 name 列的值进行排序的，所以先可以很快定位 name 列的值是 Ashburn 的记录位置。
• 在 name 列相同的记录里又是按照 birthday 列的值进行排序的，所以在 name 列的值是 Ashburn 的记录里又可以快速定位 birthday 列 的值是 '1990-09-27' 的记录。
• 如果很不幸，name 和 birthday 列的值都是相同的，那记录是按照 phone 列的值排序的，所以联合索引中的三个列都可能被用到。

匹配左边的列

SELECT * FROM person_info WHERE name = 'Ashburn' AND birthday = '1990-09-27';

如果我们想使用联合索引中尽可能多的列，搜索条件中的各个列必须是联合索引中从最左边连续的列。

也就是说如果是上述的搜索条件，我们可以先根据 name 查找再根据 birthday 查找，但是如果搜索条件是：

SELECT * FROM person_info WHERE name = 'Ashburn' And phone = '15123983239';

这样只能用到 name 列的索引，birthday 和 phone 的索引就用不上了，因为 name 值相同的记录先按照 birthday 的值进行排序，birthday 值相同的记录才按照 phone 值进行排序。

匹配范围值

SELECT * FROM person_info WHERE name > 'Asa' AND name < 'Barlow'; 

找到 name 值为 Asa 的记录，找到 name 值为 Barlow 的记录，找到两者之间的记录的主键值，然后回表查找。

不过在使用联合进行范围查找的时候需要注意，如果对多个列同时进行范围查找的话，只有对索引最左边的那个列进行范围查找的时候才能用到 B+ 树索引。例如：

SELECT * FROM person_info WHERE name > 'Asa' AND name < 'Barlow' AND birthday > '1980-01-01';

这个查询只能用到联合索引 idx_name_birthday_phone 的 name 列的部分。

精确匹配某一列并范围匹配另一列

对于同一个联合索引来说，虽然对多个列都进行范围查找时只能用到最左边那个索引列，但是如果左边的列是精确查找，则右边的列可以进行范围查找，例如：

SELECT * FROM person_info WHERE name = 'Ashburn' AND birthday > '1980-01-01' AND birthday < '2000-12-31' AND phone > '15100000000';

这个查询可以用到联合索引 idx_name_birthday_phone 的 name 列和 birthday 列的部分，但是用不到 phone 列的部分。

用于排序

在 MySQL 中，把在内存中或者磁盘上进行排序的方式统称为文件排序（英文名：filesort），跟 文件 这个词儿一沾边儿，就显得这些排序操作非常慢了（磁盘和内存的速度比起来，就像是飞机和蜗牛的对比）。但是如果 ORDER BY 子句里使用到了我们的索引列，就有可能省去在内存或文件中排序的步骤，比如下边这个简单的查询语句：

SELECT * FROM person_info ORDER BY name, birthday, phone LIMIT 10;

这个查询的结果集需要先按照 name 值排序，如果记录的 name 值相同，则需要按照 birthday 来排序，如果 birthday 的值相同，则需要按照 phone 排序。巧了，联合索引 idx_name_birthday_phone 中记录刚好就是这么排序的，直接用就好了。

用于分组

有时候我们为了方便统计表中的一些信息，会把表中的记录按照某些列进行分组。比如下边这个分组查询：

SELECT name, birthday, phone, COUNT(*) FROM person_info GROUP BY name, birthday, phone;

这个查询语句相当于做了3次分组操作：

1. 先把记录按照 name 值进行分组，所有 name 值相同的记录划分为一组。
2. 将每个 name 值相同的分组里的记录再按照 birthday 的值进行分组，将 birthday 值相同的记录放到一个小分组里，所以看起来就像在一个大分组里又化分了好多小分组。
3. 再将上一步中产生的小分组按照 phone 的值分成更小的分组，所以整体上看起来就像是先把记录分成一个大分组，然后把 大分组 分成若干个 小分组，然后把若干个 小分组 再细分成更多的 小小分组。

然后针对那些 小小分组 进行统计，比如在我们这个查询语句中就是统计每个 小小分组 包含的记录条数。如果没有索引的话，这个分组过程全部需要在内存里实现，而如果有了索引的话，恰巧这个分组顺序又和我们的 B+ 树中的索引列的顺序是一致的，而我们的 B+ 树索引又是按照索引列排好序的，这不正好么，所以可以直接使用 B+ 树索引进行分组。

如何挑选索引列

只为用于搜索、排序或分组的列创建索引

也就是说，只为出现在 WHERE 子句中的列、连接子句中的连接列，或者出现在 ORDER BY 或 GROUP BY 子句中的列创建索引。

考虑列的基数

列的基数 指的是某一列中去重后数据的个数，比方说某个列包含值 2, 5, 8, 2, 5, 8, 2, 5, 8，虽然有 9条记录，但该列的基数却是 3。也就是说，在记录行数一定的情况下，列的基数越大，该列中的值越分散，列的基数越小，该列中的值越集中。如果为一个基数为 1 的列建立一个索引，那么至少有两个问题：

• 所有值都一样就无法排序，无法进行快速查找了
• 使用这个二级索引查出的记录还可能要做回表操作，这样性能损耗就更大了

最好为那些列的基数大的列建立索引，为基数太小列的建立索引效果可能不好。

索引列的类型尽量小

我们在定义表结构的时候要显式的指定列的类型，以整数类型为例，有 TINYINT、MEDIUMINT、INT、BIGINT 这么几种，它们占用的存储空间依次递增，我们这里所说的 类型大小 指的就是该类型表示的数据范围的大小。能表示的整数范围当然也是依次递增，如果我们想要对某个整数列建立索引的话，在表示的整数范围允许的情况下，尽量让索引列使用较小的类型，比如我们能使用 INT 就不要使用 BIGINT，能使用 MEDIUMINT 就不要使用 INT ，这是因为：

• 数据类型越小，在查询时进行的比较操作越快
• 数据类型越小，索引占用的存储空间就越少，在一个数据页内就可以放下更多的记录，从而减少磁盘I/O带来的性能损耗，也就意味着可以把更多的数据页缓存在内存中，从而加快读写效率

这个建议对于表的主键来说更加适用，因为不仅是聚簇索引中会存储主键值，其他所有的二级索引的节点处都会存储一份记录的主键值，如果主键适用更小的数据类型，也就意味着节省更多的存储空间和更高效的I/O。

索引字符串值的前缀

在建表语句中 KEY idx_name_birthday_phone (name(10), birthday, phone) 中的 name(10) 就表示在建立的 B+ 树索引中只保留记录的前 10 个字符的编码，这种只索引字符串值的前缀的策略是我们非常鼓励的，尤其是在字符串类型能存储的字符比较多的时候。

让索引列在比较表达式中单独出现

如果索引列在比较表达式中不是以单独列的形式出现，而是以某个表达式，或者函数调用形式出现的话，是用不到索引的。

总结

• 页 是 InnoDB 管理存储空间的基本单位，用户记录是存在 索引页 中的
• InnoDB 的聚簇索引、二级索引等都是一个 B+ 树，树的节点是 索引页
• 聚簇索引非叶子节点存储目录项，叶子节点存储完整用户记录；非聚簇索引叶子节点存的是 索引列+主键
• B+ 树索引适用于全值匹配、最左列匹配、范围匹配等情况
• 在挑选索引列的时候，需要考虑列的基数、列的类型以及让索引列单独出现等

参考书籍：

• 《高性能MySQL》
• 《MySQL 是怎样运行的：从根儿上理解 MySQL》