vlambda博客
学习文章列表

一般来说，一页的大小是16K，除了实际数据外，还会存放一些额外的信息，比如记录页指针、页目录、校验码等，如下：

我们可以估计这些额外信息大约占1k的空间，也就是说一页内有15K是给我们真正放数据用的。

图中标黄的部分是一个id=5的数据检索过程，确实是我们认知中的B+树检索。

• 非叶子结点内指向其他内存页的指针数量为 X；

• 叶子节点内能容纳的 record 数量为 Y；

• B+ 树的层数为 Z。

那么，这棵 B+ 树放的行数据总量等于 (X ^ (Z-1)) * Y。

这个公式如何得出的大家可以自行推算一把，如果不想费那功夫可以找几个值验证一下其准确性。

下面进入计算环节。

非叶子节点里主要放索引查询相关的数据，放的是主键和指向页号。

主键假设是 bigint（8Byte），而页号在源码里叫 FIL_PAGE_OFFSET（4 Byte），那么非叶子节点里的一条数据是 12 Byte 左右。

结合我们前面提到的，一页里大约有15K是数据空间，那么 15K 除以 12 Byte 等于 1280，也就是一个非叶子结点可以指向 X=1280 页。

回到  (X ^ (Z-1)) * Y 这个公式，已知 X=1280，Y=15。

假设 B+ 树是三层，那 Z=3。总行数 (1280 ^ (3-1)) * 15 ≈ 2.5千万

两千万终于来了！到这里我们基本得出了结论，在三层B+树下，可以存放约两千万数据！

那么为什么是三层树呢？想想前面提到的检索id=5数据的例子，一共查询了三次，使用三次磁盘IO，三次磁盘IO一般是我们一次检索操作可以接受的。