面试题：MySQL 三层 B+ 树能存多少数据？

在 MySQL 中，B+ 树是一种常用的索引结构，通常用于 InnoDB 存储引擎。B+ 树的层数决定了其能存储的数据量。要计算三层 B+ 树能存储多少数据，需考虑以下几个因素：

1. B+ 树的结构

• 根节点：树的顶层，只有一个。
• 中间节点：树的中间层，可以有多个。
• 叶子节点：树的底层，存储实际数据。

2. 节点大小

InnoDB 中，默认页大小为 16KB（16384 字节）。每个节点的大小通常为一页。

3. 键值和指针大小

• 键值大小：假设主键为 BIGINT（8 字节）。
• 指针大小：InnoDB 中，指针通常为 6 字节。

4. 计算每个节点的键值数量

每个节点能存储的键值数量取决于键值和指针的大小。假设每个节点存储 n 个键值和 n+1 个指针，计算公式为：n×键值大小+(n+1)×指针大小≤页大小n×键值大小+(n+1)×指针大小≤页大小

代入数值：n×8+(n+1)×6≤16384n×8+(n+1)×6≤16384

简化：14n+6≤1638414n+6≤1638414n≤1637814n≤16378n≤1170n≤1170

因此，每个节点大约可以存储 1170 个键值。

5. 计算三层 B+ 树的数据量

• 根节点：1 个节点，1170 个键值。
• 中间层：1171 个节点（每个键值对应一个子节点），每个节点 1170 个键值，总计 1171×11701171×1170。
• 叶子层：1171×11701171×1170 个节点，每个节点存储实际数据。

假设每个叶子节点存储 15 条记录（具体取决于记录大小），则总记录数为：1171×1170×15≈20,000,0001171×1170×15≈20,000,000

总结

三层 B+ 树大约可以存储 2000 万条记录。实际存储量可能因记录大小、填充因子等因素有所不同。

注意事项

• 记录大小：记录越大，每个叶子节点存储的记录数越少。
• 填充因子：节点通常不会完全填满，实际存储量可能略低。
• 索引类型：主键索引和二级索引的存储方式不同，影响数据量。

这些计算基于典型配置，实际情况可能有所变化。