当前位置:网站首页>MySQL索引的B+树到底有多高?

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

2022-08-09 10:18:00 InfoQ

一、问题

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

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

  • h:统称索引的高度;
  • h1:聚簇索引的高度;
  • h2:二级辅助索引的高度;
  • k:中间结点的扇出系数。

二、分析

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

null
我们都知道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表中每个的索引高度》
一文中有介绍查看索引真实高度的方法。

null
如上图所示,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_NO
FROM information_schema.INNODB_SYS_INDEXES a,
 information_schema.INNODB_SYS_TABLES b
WHERE a.table_id = b.table_id 
 AND a.space <> 0;

运行结果如下:

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

$hexdump -C -s 49216 -n 10 user.ibd
0000c040 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。

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

  • 通过
    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表,其结构如下:

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]之间的随机字符。数据示例如下:

null
我们通过
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



关于作者

杜云杰,高级架构师,转转架构部负责人,转转技术委员会执行主席,腾讯云TVP。负责服务治理、MQ、云平台、APM、IM、分布式调用链路追踪、监控系统、配置中心、分布式任务调度平台、分布式ID生成器、分布式锁等基础组件。微信号:
waterystone
,欢迎建设性交流。

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

关注公众号「转转技术」(综合性)、「大转转FE」(专注于FE)、「转转QA」(专注于QA),更多干货实践,欢迎交流分享~
原网站

版权声明
本文为[InfoQ]所创,转载请带上原文链接,感谢
https://xie.infoq.cn/article/6e37240f3998e8120561ada9e