MySql的InnoDB的三层B+树可以存储两千万左右条数据的计算逻辑

总结/朱季谦

B+树是一种在非叶子节点存放排序好的索引而在叶子节点存放数据的数据结构，值得注意的是，在叶子节点中，存储的并非只是一行表数据，而是以页为单位存储，一个页可以包含多行表记录。非叶子节点存放的是索引键值和页指针。

那么，在MySql数据库里，一个页的大小是多少呢？

可以通过查询语句进行查看：show variables like 'innodb_page_size'

查询结果16384字节，可以通过1kb等于1024字节方式，计算出16384/1024 = 16kb，说明MySql数据库默认页大小是16kb。

假设一行数据占用1kb的空间大小，然而实际上，除去字段很多的宽表外，其实很多简单的表行记录都远达不到1kb空间占比。这里我们用最坏的情况来假设一行记录大小为1kb，那么，一个16kb的页就可以存储16行数据。

接下来，我们先画一个只要两层高的B+树结构图。

假设第一层根节点存在以下情况：索引1对应页指针地址10，索引5对应页指针地址30，索引8对应页指针地址50。

第二层节点作为叶子节点，存放的是大小为16kb的页数据，页数据里每一行记录大小为1kb，那么，一个叶子节点的页里就可以存放16条数据。

既然已经知道一个叶子节点的页中可以存放16条数据，那么，只需要知道根节点存在多少页地址指针即可，就能通过 “根节点页地址指针数量 * 单个叶子节点记录行数”。

那么，根节点能存放多少个 索引：页地址指针的数据呢？

在一个节点大小为16kb的情况下，我们只需要知道索引键值和页地址指针两者大小总和即可。

根据一些资料得知，在MySql数据库当中，指针地址大小为6字节，若索引是bigint类型，那么就为8字节，两者加起来总共是14字节。

接下来，通过以下计算步骤，就可以统计出两层的B+数大概可以存储多少条记录数据——

一、先计算一个节点的字节大小：16kb * 1024 = 16384 字节。

二、16384 字节 / 14 字节 = 1170 ，意味着，根节点有1170个页地址指针，然后，每个页地址指针指向的叶子节点可以存放16条数据。

三、那么，根据“根节点页地址指针数量 * 单个叶子节点记录行数”，计算1170 * 16 = 18720 条记录，可见，两层B+数可以存放18720条记录，当然，这个数字是存在出入的，只是作为参考。

既然已经知道两层B+数可以存放18720条数据，那么，三层不就可以进一步算出了吗？

简单画一个三层B+数的存放数据计算逻辑——

一、根节点最多有1170个指针数；

二、说明第二层最多会有1170个子节点，同时，每个子节点里最多有1170个指针数；

三、那么，第三层叶节点数量，可以通过 “第二层最多有1170个节点数量 * 每个节点里最多有1170个指针数量”，也就是1170 * 1170

四、最后，计算第三层所有叶子数量 * 各个叶子节点存放的16条数据；

最后，1170 * 1170 * 16 = 21902400，得出两千万左右条数据。

综上所述，若面试当中遇到这样问题，可以按照这个流程计算回答。