MySql InnoDB 三层B+树存储约2000万条数据的计算逻辑

总结/朱季谦

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对应页指针10的地址。页指针50。

二级节点为叶子节点，存储页数据，大小为16kb。页数据中每行的记录大小为1 kb。那么一个叶子节点页可以存储16条数据。

现在我们知道一个叶子节点page中可以存储16个数据，那么我们只需要知道根节点中存在多少个page地址指针即可，我们可以通过“页数根节点地址指针” * 单叶节点记录行数”。

根节点可以存储多少索引指针数据：页地址？

当节点大小为16kb时，我们只需要知道索引键值和页地址指针的大小之和。

根据一些资料，MySql数据库中指针地址大小为6字节。如果索引是bigint类型，则为8字节。总共有14个字节。

此外，您还可以通过以下计算步骤，计算出双层数B+——

1可以存储多少条数据。首先计算节点的字节大小：16 kb * 1024 = 16384 bytes 。

2。 16384字节/14字节=1170，即根节点有1170个页地址指针，每个页地址指针指向的尾节点可以存储16个数据。

3、然后根据“根节点地址指针的数量*一个叶子节点的记录行数”计算出1170 * 16 = 18720条记录。可见两层B+数可以存储18720条记录。当然，这个数字也有出入。 ，仅供参考。

既然我们知道两层B+数可以存储18720条数据，那我们不能再用三层来进一步计算吗？

简单画出存储数字B+——

1的三层数据计算逻辑。根节点最多有1170个指针；

2。这意味着第二层最多可以有1170个子节点。同时每个子节点最多有1170个指针；

3。那么第三层叶子节点的数量可以根据“第二层节点最大数量为1170 * 每个节点最大指针数量为1170”来确定，即1170 * 1170

4最后计算第三层所有叶子的数量*每个叶子节点存储的16条数据；

最终1170 * 1170 * 16 = 21902400，得到大约2000万条文章数据。

总结一下，如果你面试的时候遇到这样的问题，就可以按照这个流程算出答案。