一、普通B+树

1、B+ 树结构概述

B+ 树是一种平衡的多路搜索树，常用于数据库和文件系统中。在 B+ 树中，所有的数据记录都存储在叶子节点，非叶子节点只存储索引信息。B+ 树的高度从根节点开始计算，根节点高度为 1。

2、计算所需参数

要计算高度为 3 的 B+ 树能存储的数据量，需要知道两个关键参数：

非叶子节点的扇出系数（m）：表示一个非叶子节点最多能有多少个子节点。

叶子节点能存储的记录数（n）：即一个叶子节点最多能容纳多少条数据记录。

3、计算过程

高度为 1 的情况：根节点为叶子节点，此时能存储的数据量就是一个叶子节点能存储的记录数，即 n 条。

高度为 2 的情况：根节点为非叶子节点，其每个子节点为叶子节点。根节点最多有 m 个子节点，每个子节点能存储 n 条记录，所以能存储的数据量为 m * n 条。

高度为 3 的情况：根节点为非叶子节点，其每个子节点也是非叶子节点，这些子节点又各自有叶子节点。根节点最多有 m 个子节点，每个子节点最多又有 m 个叶子节点，每个叶子节点能存储 n 条记录，所以能存储的数据量为 m * m * n 条，即 m² * n 条。

4、示例计算

假设非叶子节点的扇出系数 m = 100，叶子节点能存储的记录数 n = 1000，则高度为 3 的 B+ 树能存储的数据量为：

m² * n = 100² * 1000 = 10000 * 1000 = 10000000（条）

总结

高度为 3 的 B+ 树能存储的数据量取决于非叶子节点的扇出系数 m 和叶子节点能存储的记录数 n，计算公式为 m² * n。不同的数据库系统和应用场景下，m 和 n 的值会有所不同。

二、MySQL 的 InnoDB 引擎

1、关键信息

页大小：InnoDB 中，数据是按页存储的，默认页大小是 16KB（即 16 * 1024 = 16384 字节）。

主键索引：这里以主键索引的 B+ 树为例进行计算，非叶子节点存储的是键值和指向子节点的指针，叶子节点存储的是完整的数据记录。

2、非叶子节点可容纳条目数量计算

非叶子节点主要存储键值和指向子节点的指针。假设主键为 BIGINT 类型，占 8 字节，指针占 6 字节，那么一个索引项（键值 + 指针）的大小就是 8 + 6 = 14 字节。

由于页大小为 16384 字节，要预留一部分空间用于页的其他管理信息，通常按 16384 - 200（预留空间） = 16184 字节来计算可用于存储索引项的空间。

则一个非叶子节点可容纳的索引项数量（扇出系数，设为 m）为：16184 ÷ 14 ≈ 1156 个。

3、叶子节点可容纳记录数量计算

假设每条记录大小为 1KB（1024 字节），同样要预留部分空间，按 16184 字节来计算可用于存储记录的空间。

则一个叶子节点可容纳的记录数量（设为 n）为：16184 ÷ 1024 ≈ 15 条。

4、高度为 3 的 B+ 树可存储数据量计算

在高度为 3 的 B+ 树中，根节点（第 1 层）是一个非叶子节点，第 2 层也是非叶子节点，第 3 层是叶子节点。

根节点有 m 个子节点（第 2 层的非叶子节点），每个第 2 层的非叶子节点又有 m 个子节点（第 3 层的叶子节点），每个叶子节点可存储 n 条记录。

所以，高度为 3 的 B+ 树可存储的数据量为：m * m * n = 1156 * 1156 * 15 ≈ 20000000 条记录。

注意事项

记录大小：上述计算假设每条记录大小为 1KB，如果实际记录大小不同，n 的值会发生变化，从而影响最终可存储的数据量。

索引类型：不同的索引类型（如联合索引）和字段类型，会使非叶子节点的索引项大小不同，进而影响 m 的值。

综上所述，在给定的假设条件下，MySQL InnoDB 引擎高度为 3 的 B+ 树大约可以存储 2000 万条记录。