下面给出一种用字母表示的完整推导过程，假设我们有如下符号定义：

• P：节点（数据页）的大小（单位：字节）
• A：每个索引键的大小（单位：字节）
• B：每个指针的大小（单位：字节）

在 B+ 树中，内部节点存储键和指向子节点的指针，而叶子节点存储数据项（键值及相应数据）。这里假设：

• 内部节点存储最多 n 个键，同时存储 (n + 1) 个指针。
• 叶子节点存储最多 n 个数据项。

1. 求内部节点的最大键数

内部节点所占用的空间为：

$\text{空间}=n\times A+(n+1)\times B$

要求该空间不超过页大小 P，因此有不等式：

$n\times A+(n+1)\times B\le P$

将不等式整理：

$nA+nB+B\le P⟹n(A+B)\le P-B$

解得：

$n\le \frac{P-B}{A+B}$

令

$M=\lfloor \frac{P-B}{A+B}\rfloor$

则我们可认为每个内部节点最多有 M 个键（以及 M+1 个指针）。

2. 三层 B+ 树的结构

假设 B+ 树只有三层：

1. 第一层（根节点）

   • 根节点为内部节点，最多有 M 个键和 M+1 个指针。

   • 此处我们记根节点的“扇出”为 F，其中

     $F=M+1$

2. 第二层（内部节点）

   • 每个内部节点同样最多有 M 个键和 M+1 个指针。
   • 第二层的节点数量最多为根节点的指针数，即 F 个。

3. 第三层（叶子节点）

   • 每个叶子节点存储数据项，最多存 M 个数据项。

   • 叶子节点的数量由第二层的所有指针决定，最多为

     $\text{叶子节点数}=F\times F=F^2$

3. 计算总存储数据项数

每个叶子节点最多存储 M 个数据项，因此整个 B+ 树中可存储的数据总数 T 为：

$T=\text{叶子节点数}\times M=F^2\times M$
将 F 代入得：

$T=(M+1{)}^2\times M$

4. 总结

• 内部节点最大键数：

  $M=\lfloor \frac{P-B}{A+B}\rfloor$

• 根节点的扇出：

  $F=M+1$

• 三层 B+ 树的数据存储能力：

  $T=(M+1{)}^2\times M$