MySQL 索引的 B+ 树到底有多高?
一、问题
经常遇到业务线的同学问,既然页面 I/O 对 MySQL 查询性能影响较大,那么对于一次 MySQL 查询,底层要进行多少次页面 I/O 呢?
为了回答这个问题,下文我们简化几个概念:
h:统称索引的高度;
h1:聚簇索引的高度;
h2:二级辅助索引的高度;
k:中间结点的扇出系数。
二、分析
不得不说这是一个非常棒的问题,跟咱们的日常查询密切相关。这个问题看似简单,但回答起来并不那么容易。首先我们来看下MySQL B+树索引的结构:
![](https://static001.geekbang.org/infoq/7a/7a67e799f9a0846621a7216923cd6e6a.png)
我们都知道 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表中每个的索引高度》一文中有介绍查看索引真实高度的方法。
![](https://static001.geekbang.org/infoq/ad/ade3eeed48577facff9431a303d7d83f.png)
如上图所示,InnoDB 是索引组织表,每个页都包含一个 PAGE_LEVEL 的信息(见上图右半部分),用于表示当前页所在索引中的高度。默认叶子节点的高度为 0,那么 Root 页的 PAGE_LEVEL+1 就是这棵索引的高度。
接下去的问题就是怎样得到一张表所有索引的 Root 页所在的位置呢?在《MySQL 技术内幕:InnoDB 存储引擎》书中分析过<space,3>这个页(即 ibd 文件的第 3 个页面,从 0 开始)是聚簇索引的 Root 页,在《MySQL 内核:InnoDB 存储引擎 卷 1》中也分析,Root 页的位置通常是不会更改的。那么其他索引的 Root 页所在的位置呢?通过下面的 SQL 语句可以查出表中各索引的 Root 页信息:
运行结果如下:
![](https://static001.geekbang.org/infoq/5f/5f82c6443d0b64fd33f111cefff0d166.png)
其中<SPACE,PAGE_NO>就是索引的 Root 页信息,SPACE 可以认为是表的 ibd 文件,PAGE_NO 代表 ibd 文件中的页面号(从 0 开始)。有了这些信息就可以方便的定位了,因为 PAGE_LEVEL 在每个 Root 页的偏移量 64 位置处,占用两个字节,这样我们通过hexdump
就可以快速定位到各索引树的高度信息了。例如,我们通过如下命令查看 user 表聚簇索引的高度:
这里,49216 表示的是16384*3+64
,即从第 3 个页内偏移量 64 位置开始读取 10 个字节,前两个字节为 PAGE_LEVEL,后 8 个字节是 index_id,就是上图中看到的 index_id=811(0x032b=811)的聚簇索引,这里 PAGE_LEVEL 为 00 01,那么索引树的高度就为 2。
综上,查看索引真实高度的方法总结如下:
通过
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 即为索引的高度。
四、验证索引的真实高度
我们创建一个 user 表,其结构如下:
持续向表中插入数据,card_id
字段跟 id 一样从 1 开始,name
为 32 个随机字符,content
为长度在[500,1000]之间的随机字符。数据示例如下:
![](https://static001.geekbang.org/infoq/be/be3e60568799b5ddb83bd903ab965bc3.png)
我们通过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)等,那扇出系数就低了,整个索引看起来属于“瘦高”型,索引效率自然要低些。所以我们在字段选取类型时,其类型越简单效率越好。
看到这里,是不是有点心动了?那还不赶快用本文的方法去看下自己负责表的索引高度?
附赠快速查看命令:
转转研发中心及业界小伙伴们的技术学习交流平台,定期分享一线的实战经验及业界前沿的技术话题。
关注公众号「转转技术」(综合性)、「大转转 FE」(专注于 FE)、「转转 QA」(专注于 QA),更多干货实践,欢迎交流分享~
评论