当前位置：网站首页>MySQL索引的B+树到底有多高？
MySQL索引的B+树到底有多高？
2022-08-09 15:33:00 【InfoQ】
一、问题
经常遇到业务线的同学问，既然页面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_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;
复制代码运行结果如下：
其中<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]之间的随机字符。数据示例如下：
我们通过
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
复制代码
边栏推荐
- 巧用Prometheus来扩展kubernetes调度器
- 零基础爬虫regex练习「音乐抓取」
- Heap series_0x09: Example of heap corruption (illegal access + uninitialized + heap handle mismatch)
- resubmit 渐进式防重复提交框架简介
- 4. Using Local Geospatial Data
- 2022年华数杯C题插层熔喷完整解题思路（附代码+详细讲解视频）
- 初始C语言 C生万物
- Why does a four-byte float represent a wider range than an eight-byte long
- 前言：关于作者吴秋生博士与此书简介
- Two ways to find the factorial of n
猜你喜欢
智慧灯杆网关智慧交通应用
设计一个登录小程序（while和getchar实现）
Why does a four-byte float represent a wider range than an eight-byte long
初始C语言（2） C生万物
网络——TCP拥塞控制
uni-app中websocket的使用 断开重连、心跳机制
苹果开发者账号 申请 D-U-N-S 编号
![[Server data recovery] Data recovery case of file system data loss caused by SAN LUN mapping error](/img/fa/a6d9fdc17dd92f68f876df4a6e3ca6.jpg)
[Server data recovery] Data recovery case of file system data loss caused by SAN LUN mapping error
推荐一些面向 Web 开发者的杀手级网站
BETA：一个用于计算药物靶标预测的综合基准
随机推荐
C语言的常量和操作符
初识C语言，了解一下C语言轮廓
推荐一些面向 Web 开发者的杀手级网站
Redis Cache Expiration and Retirement Policy
【Web渗透】信息收集篇——Google搜索引擎（二）
三.两数交换 空指针 ＆＆ 野指针 解引用问题
＃yyds干货盘点＃ 面试必刷TOP101：删除有序链表中重复的元素-II
微服务框架笔记(1)
想通这点，治好 AI 打工人的精神内耗
C语言三子棋详解
5G NR Paging 寻呼
4. Using Local Geospatial Data
2022年8月9日：用C＃生成.NET应用程序--使用 Visual Studio Code 调试器，以交互方式调试 .NET 应用（不会，失败）
No need to pay for the 688 Apple developer account, xcode13 packaged and exported ipa, and provided others for internal testing
五.初始指针
yolov5训练并生成rknn模型以及3588平台部署
SQL抖音面试题：送你一个万能模板，要吗？(重点、每个用户每月连续登录的最大天数)
std::uniform_real_distribution的一个bug引发的服务器崩溃
第五章：可视化地理空间数据
Smart Light Pole Gateway Smart Transportation Application