1. 背景
同学在参加阿里面试的时候,被问到了B+树索引能存多少数据。这个问题挺有趣,要是对B+树不太了解,那么这个问题估计也不好回答
那么要回答这个问题,首先要知道B+树的结构是怎样的,存了什么数据,怎么存的,这些东西占多大等
先新建个表
CREATE TABLE IF NOT EXISTS `person`(
`id` INT UNSIGNED AUTO_INCREMENT,
`name` VARCHAR(64) NOT NULL,
PRIMARY KEY ( `id` )
)ENGINE=InnoDB DEFAULT CHARSET=utf8;
复制代码
2. InnoDB的页结构
-
在InnoDB中,索引默认使用的数据结构为B+树,而
B+树里的每个节点都是一个页
,默认的页大小为16KB
。 -
非叶子节点存的是索引值以及页的偏移量,而叶子节点上存放的则是完整的每行记录
大概认识了页里面存了什么,占多大空间,就可以估计能存放多少条数据了
这里重点关注绿色部分。我也没画太全,还有File Header、Page Header等是什么,有什么用这些就不展开说了,有兴趣的可以自己去翻一下《MySQL技术内幕》的4.4,或者去看我分析这个person表的ibd文件,怎么写出下面验证的小工具的
小工具链接:github.com/52123/innod…
3. B+树能存多少数据
3.1 非叶子节点能存多少数据
- 页默认16KB
- File Header、Page Header等一共占102个字节
- Infimum + Supremum分别占13个字节
- 记录头占5个字节
- id占为int,占4个字节
- 页目录的偏移量占4个字节
所以,非叶子节点能存多少条索引记录呢
非叶子节点能存放的索引记录
= (页大小 - File Header - Page Header - ...) / ( 主键 + 页偏移量 + 下一条记录的偏移量)
= (16KB - 128B) / (5B + 4B + 4B)
= 16256 / 13
= 1250 条
复制代码
3.2 叶子节点能存多少数据
叶子节点能存多少条数据记录呢
- 变长列表占1个字节
- null标志位忽略
- 记录头占5个字节
- id占为int,占4个字节
- name为VARCHAR,编码为UTF8,为了好算,所有行记录我都只用两个中文,那就是 2 * 3B = 6个字节
- 事务ID列占6个字节
- 回滚指针列占7个字节
叶子节点能存放的数据记录
= (页大小 - File Header - Page Header - ...) / ( 主键 + 字段 + 下一条记录的偏移量)
= (16KB - 128B) / (1B + 5B + 4B + 6B + 6B + 7B)
= 16256 / 29
= 560 条
复制代码
3.3 高为3的B+树能存多少行数据记录
- 根节点能放1250条索引记录
- 第二层能放1250 * 1250 = 1,562,500条索引记录
- 叶子节点 1250 * 1250 * 560 = 875,000,000条数据记录,八亿多条数据
也就是说,假如我的表里面只有id和name这两个字段的话,高为3的B+树能存八亿多条数据记录,好家伙
4. 验证一下
写了个脚本生成批量插入的SQL,插入了27,090,000条数据
根据File Header、Page Header、Infimum、Supremum和Record Header的大小以及含义,我用Python写了个小工具,用来帮忙验证每一页存的数据量是不是跟我上面猜想的一样
得到的数据:B+树高度为3,非叶子节点有46个,叶子节点52501个,索引记录的数量为52546, 行数据记录的数量为27090000
4.1 实际得到非叶子节点能存多少数据
实际得到的非叶子节点能存放的索引记录
= 索引记录的数量 / 非叶子节点数量
= 52546 / 46
= 1142
复制代码
跟我猜想里面算出来的数值(1250条)很接近了,至于为什么实际得到的会比猜想的要少呢
- 第一,我没有算Page Directory,但是我有打印出槽的数量,可以看到非叶子节点的槽有13150个,平均每一页就是 13150 / 46 = 286个,一个槽占两个字节,所以猜想应该是 (16256 - 286 * 2) / 13 = 1206 条
- 第二,实际上,并不是每一个非叶子节点,都是存满索引数据的,所以差个几十条我觉得挺正常的
4.2 实际得到叶子节点能存多少数据
实际得到的叶子节点能存放的索引记录
= 行数据记录的数量 / 叶子节点数量
= 27090000 / 52546
= 516
复制代码
好吧,跟我猜想算出来的(560)也很接近,也差那么一点点
- 把叶子节点的槽也算上,平均每一个叶子节点的槽就是 6825001 / 52501 = 130个,那么更准确的猜想应该是(16256 - 130 * 2)/ 29 = 551 条
- 跟上面一样,不是每个叶子节点都刚好存满的
4.3 有趣的点
刚才我们得到的数据
- 非叶子节点有46个,叶子节点52501个
- 索引记录的数量为52546, 行数据记录的数量为27090000
其实这个 索引记录的数量
跟 叶子节点的数量
跟是能对上的,我看了下根节点,它有45条索引记录,也就是说
- 根节点,存了45条索引记录
- 第二层,存了52546 - 45 = 52501条索引记录数据
- 第三层,叶子节点,有52501个
这个第二层跟第三层刚好就是一条索引记录对应一个叶子节点
复制代码
5. 举一反三
为什么InnoDB默认使用B+树作为索引的数据结构
本质:减少磁盘IO
InnoDB使用B+树的非叶子节点存储主键值和页目录,这样一个页能存下来的索引记录就会变多。叶子节点则拿来存真正的行记录,这样做的好处能让树的高度降下来,从而减少磁盘IO。结合上面,八亿多的数据,高度为3的B+树就能存下了,最多只需要3次磁盘IO,就能从八亿数据中得到想要的数据了。
为什么不用B树来作为索引的数据结构
B树跟B+树不一样,B树每一页都会存行数据,因为行数据占的空间比较大,所以每一页能存的数据就相应减少了,从而需要更多的页来存数据,因此,树也会相应变高,从八亿多的数据可能就要N次磁盘IO才能得到了
另外,B+树的页节点都是由双向列表连接的,而页里面的记录则是用单向链表连接的,所以获取区间数据也会更高效
6. 总结
InnoDB存储引擎默认使用的索引数据结构为B+树,而B+树里的每个节点都是一个页
,默认的页大小为16KB
B+树里的非叶子节点存的是索引记录,包含索引值和页偏移量,而叶子节点存的是行数据记录,包含真正的行数据
- File Header占38个字节
- Page Header占56个字节
- Infimum和Supremum各占13个字节
- File Trailer占8个字节
- Page Directory里每个槽占2个字节
- 每条记录的记录头占5个字节(不管是索引记录,行数据记录都有数据头)
结合表中定义的字段大小,可大致推断B+树能存多少数据
InnoDB使用B+树作为默认的索引数据结构的一个主要原因是,减少磁盘的IO次数
参考
- MySQL官方文档-The InnoDB Storage Engine
- 《MySQL技术内幕(InnoDB存储引擎)第2版》
- 《高性能MySQL》
近期评论