MySQL 索引的 B+ 树到底有多高？

一、问题

经常遇到业务线的同学问，既然页面 I/O 对 MySQL 查询性能影响较大，那么对于一次 MySQL 查询，底层要进行多少次页面 I/O 呢？

为了回答这个问题，下文我们简化几个概念：

• h：统称索引的高度；

• h1：聚簇索引的高度；

• h2：二级辅助索引的高度；

• k：中间结点的扇出系数。

二、分析

不得不说这是一个非常棒的问题，跟咱们的日常查询密切相关。这个问题看似简单，但回答起来并不那么容易。首先我们来看下MySQL B+树索引的结构：

我们都知道 MySQL 里，索引是用 B+树来实现的。B+树的叶子结点才保存具体数据（聚簇索引保存的是完整行数据，而二级辅助索引保存的是索引值+主键，非覆盖索引查询还得回表），中间结点都是用来索引叶子结点的。

2.1 索引高度 h 与页面 I/O 数的关系

从索引结构可以看出，每次查询都要访问到叶子结点，其访问的页面数正好就是索引的高度 h。例如，一次主键上的点查询SELECT * FROM USER WHERE id=1，那么要查询 h1 个页面才能找到叶子结点里的行数据，也即进行 h1 次页面 I/O。（另外，二级索引基本都加载在内存里了，这里我们暂忽略这种情况。）

综上，查询对应的页面 I/O 数跟利用的索引有关，主要分为以下几种情况：

• 点查询：

• 聚族索引：h1

• 二级索引：

• 覆盖索引：h2

• 回表查询：h2+h1

• 范围查询：这种情况相对比较复杂，但跟点查询的原理类似，读者可自行分析；

• 全表查询：B+树的叶子结点是通过链表连接起来的，对于全表查询，需要从头到尾将所有的叶子结点访问一遍。

2.2 索引高度 h 的理论计算

从上可以看出，h 的大小势必成为索引性能的一个关键。那么通常表的索引高度 h 是多大呢？

我们假设中间结点的扇出系数为 k、叶子结点的行记录数为 n，则叶子结点数为k^(h-1)，总记录数为k^(h-1)*n。

在 InnoDB 里，每个页面默认 16KB，假设主键是 4B 的 int 类型。对于中间节点，每个主键值后有个页号 4B，还有 6B 的其他数据(参考《MySQL 技术内幕：InnoDB 存储引擎》)，那么扇出系数 k=16KB/(4B+4B+6B)≈1170。我们再假设每行记录大小为 1KB，则每个叶子结点可以容纳的记录数 n=16KB/1KB=16。

在高度 h=3 时，叶子结点数=1170^2 ≈137W，总记录数=1170^2*16=2190W！！也就是说，InnoDB 通过三次索引页面的 I/O，即可索引 2190W 行记录。

同理，在高度 h=4 时，总行数=1170^3*16≈256 亿条！！！

这只是我们的理论分析，InnoDB 也没有提供相应的视图进行查看，那么我们该如何查看索引的真实高度呢？

三、查看索引真实高度的方法

姜承尧大神在《查看 InnoDB表中每个的索引高度》一文中有介绍查看索引真实高度的方法。

如上图所示，InnoDB 是索引组织表，每个页都包含一个 PAGE_LEVEL 的信息（见上图右半部分），用于表示当前页所在索引中的高度。默认叶子节点的高度为 0，那么 Root 页的 PAGE_LEVEL+1 就是这棵索引的高度。

接下去的问题就是怎样得到一张表所有索引的 Root 页所在的位置呢？在《MySQL 技术内幕：InnoDB 存储引擎》书中分析过<space，3>这个页（即 ibd 文件的第 3 个页面，从 0 开始）是聚簇索引的 Root 页，在《MySQL 内核：InnoDB 存储引擎 卷 1》中也分析，Root 页的位置通常是不会更改的。那么其他索引的 Root 页所在的位置呢？通过下面的 SQL 语句可以查出表中各索引的 Root 页信息：

SELECT b.name, a.name, index_id, type, a.space, a.PAGE_NOFROM information_schema.INNODB_SYS_INDEXES a,     information_schema.INNODB_SYS_TABLES bWHERE a.table_id = b.table_id       AND a.space <> 0;

运行结果如下：

其中<SPACE，PAGE_NO>就是索引的 Root 页信息，SPACE 可以认为是表的 ibd 文件，PAGE_NO 代表 ibd 文件中的页面号（从 0 开始）。有了这些信息就可以方便的定位了，因为 PAGE_LEVEL 在每个 Root 页的偏移量 64 位置处，占用两个字节，这样我们通过hexdump就可以快速定位到各索引树的高度信息了。例如，我们通过如下命令查看 user 表聚簇索引的高度：

$hexdump -C -s 49216 -n 10 user.ibd0000c040  00 01 00 00 00 00 00 00  03 2b

这里，49216 表示的是16384*3+64，即从第 3 个页内偏移量 64 位置开始读取 10 个字节，前两个字节为 PAGE_LEVEL，后 8 个字节是 index_id，就是上图中看到的 index_id=811（0x032b=811）的聚簇索引，这里 PAGE_LEVEL 为 00 01，那么索引树的高度就为 2。

综上，查看索引真实高度的方法总结如下：

1. 通过information_schema.INNODB_SYS_INDEXES和information_schema.INNODB_SYS_TABLES找到对应索引 Root 页在 ibd 文件的页面号 PAGE_NO（聚簇索引通常为 3，其他索引往上累加）；

2. 通过hexdump -C -s 16384*PAGE_NO+64 -n 10 user.ibd，前两个字节+1 即为索引的高度。

四、验证索引的真实高度

我们创建一个 user 表，其结构如下：

CREATE TABLE `user` (  `id` INT(11) NOT NULL AUTO_INCREMENT,  `card_id` INT(11) NOT NULL DEFAULT '0' COMMENT '身份证号',  `name` VARCHAR(32) NOT NULL DEFAULT '' COMMENT '英文名字',  `age` TINYINT(2) UNSIGNED NOT NULL DEFAULT '0' COMMENT '年龄',  `content` VARCHAR(1024) NOT NULL DEFAULT '' COMMENT '附属信息',  `create_time` TIMESTAMP NOT NULL DEFAULT CURRENT_TIMESTAMP COMMENT '创建时间',  `update_time` TIMESTAMP NOT NULL DEFAULT CURRENT_TIMESTAMP ON UPDATE CURRENT_TIMESTAMP COMMENT '最近更新时间',
  PRIMARY KEY (`id`),  UNIQUE KEY `uniq_card_id` (`card_id`),  KEY `idx_name` (`name`)) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4 COMMENT='用户表';

持续向表中插入数据，card_id字段跟 id 一样从 1 开始，name为 32 个随机字符，content为长度在[500,1000]之间的随机字符。数据示例如下：

我们通过hexdump -C -s 49216 -n 10 user.ibd && hexdump -C -s 65600 -n 10 user.ibd && hexdump -C -s 81984 -n 10 user.ibd查看三个索引的真实高度，汇总如下：

从真实数据可以看出，聚簇索引在 2700W 时高度才升为 4，比上文分析的 2190W 要慢 500W 左右，这主要应该是因为 2190W 是基于行记录为 1KB 来估算的，而我们插入的数据在[0.5KB，1KB]之间，从页使得叶子结点可以容纳更多的行记录。

另外发现一个有趣的现象，idx_name索引在 2300W 时高度就升为 4。这主要是因为name长度为 32，扇出系数 k=16KB/(32B+4B+6B)≈390，这比聚簇索引的 1170 要小的多（或者说要瘦的多），造成索引“瘦高”的情况。

五、总结

• 一次查询的页面 I/O 数跟索引高度 h 呈正相关，主要分为以下几种情况：

• 点查询：

• 聚族索引：h1

• 二级索引：

• 覆盖索引：h2

• 回表查询：h2+h1

• 范围查询：这种情况相对比较复杂，但跟点查询的原理类似，读者可自行分析；

• 全表查询：B+树的叶子结点是通过链表连接起来的，对于全表查询，需要从头到尾将所有的叶子结点访问一遍。

• 索引高度通常为 2~4 层。在高度 h=3、主键为 int 类型、行记录大小为 1KB 时，可索引的总行数为 1170^2*16=2190W。这也是很多大厂将2000W作为分库分表标准的原因；

• 查看索引真实高度的方法如下：

• 通过information_schema.INNODB_SYS_INDEXES和information_schema.INNODB_SYS_TABLES找到对应索引 Root 页在 ibd 文件的页面号 PAGE_NO（聚簇索引通常为 3，其他索引往上累加）；

• 通过hexdump -C -s 16384*PAGE_NO+64 -n 10 user.ibd，前两个字节+1 即为索引的高度。

• 索引高度 h 也跟索引字段的数据类型有关。如果是 int 或 short，扇出系数大，索引效率更好，整个索引看起来属于“矮胖”型；而如果是 varchar(32)等，那扇出系数就低了，整个索引看起来属于“瘦高”型，索引效率自然要低些。所以我们在字段选取类型时，其类型越简单效率越好。

看到这里，是不是有点心动了？那还不赶快用本文的方法去看下自己负责表的索引高度？

附赠快速查看命令：

#聚簇索引（第一个）hexdump -C -s 49216 -n 10 user.ibd
#第二个索引hexdump -C -s 65600 -n 10 user.ibd
#第三个索引hexdump -C -s 81984 -n 10 user.ibd

转转研发中心及业界小伙伴们的技术学习交流平台，定期分享一线的实战经验及业界前沿的技术话题。

关注公众号「转转技术」（综合性）、「大转转 FE」（专注于 FE）、「转转 QA」（专注于 QA），更多干货实践，欢迎交流分享~