一颗高度为3的B+树到底能存多少数据呢

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》