B 树

解释：

1. 最大子节点数：每个节点最多有 $5 + 1 = 6$ 个子节点（键数+1）。
2. B+ 树性质：非根节点的最小子节点数为 $\left\lceil \frac{6}{2} \right\rceil = 3$。
3. 最小键数计算：子节点数减 1 即为键数，因此最小键数为 $3 - 1 = 2$。

解释：

• 磁盘访问速度较慢，因此减少 I/O 操作次数至关重要
• B+ 树通过高扇出度（通常 100 或更多）显著降低树高度
• 相比二叉查找树，B+ 树能以更少层级完成查找
• 高扇出特性使每次磁盘访问能检索更多子节点信息

• 插入第 3 个键
  初始状态：10 20 30

• 插入第 4 个键（第一次分裂）
  插入 40 后触发分裂：

    30  
   / \  
  10*20  40
  

• 插入第 5 个键（无分裂）
  插入 5 至左子节点：

    30  
   / \  
  5*10*20  40
  

• 插入第 6 个键（第二次分裂）
  插入 8 触发分裂：

    8*30  
   / | \  
  5  10*20  40
  

• 插入第 7 个键（无分裂）
  插入 15 至右子节点：

    8*30  
   / | \  
  5  10*15*20  40
  

• 插入第 8 个键（第三次分裂）
  插入 12 触发分裂：

    8*12*30  
   / / \ \  
  5  10  15*20  40
  

• 插入第 9 个键（无分裂）
  插入 17 至右子节点：

    8*12*30  
   / / \ \  
  5  10  15*17*20  40
  

• 插入第 10 个键（第四次和第五次分裂）
  插入 13 导致两次分裂：

      12  
     / \  
    8   15*30  
   / \ / | \  
  5  10 13 17*20  40
  

结论：最大分裂次数为 5 次。
关键点：

1. 4 阶 B 树节点最多容纳 3 个键，满载后插入新键会触发分裂
2. 通过优先向有空间的节点插入，可最大化分裂次数
3. 最终分裂路径包含 5 次节点分裂操作

解析：

• 磁盘块大小 = 1024 字节
• 数据记录指针大小 $ r = 7 $ 字节
• 值域大小 $ V = 9 $ 字节
• 磁盘块指针 $ p = 6 $ 字节

设叶节点的阶数为 $ m $。B+ 树的叶节点最多包含 $ m $ 个记录指针、$ m $ 个值和一个磁盘块指针。
根据空间约束条件：
$$ r \cdot m + V \cdot m + p \leq 1024 $$
$$ (7 + 9)m + 6 \leq 1024 $$
$$ 16m + 6 \leq 1024 $$
$$ 16m \leq 1018 $$
$$ m \leq 63.625 $$

因此，最大整数 $ m = 63 $，对应选项 A。

• 单条记录大小：$8\ \text{字节} + 4\ \text{字节} = 12\ \text{字节}$
• 设阶数为 $N$
• 每个磁盘块存储的索引项数量满足：
  $$ (N - 1) \times 12\ \text{字节} + 4\ \text{字节} \leq 512\ \text{字节} $$
• 化简方程：
  $$ 12N - 8 = 512 \implies 12N = 520 \implies N = \frac{520}{12} \approx 43.33 $$
• 取整数部分作为最大可行解，故最佳阶数为 43

设 B+ 树的阶数为 $ m $

非叶节点存储结构需满足： $$ m \times 8 + (m - 1) \times 12 \leq 1024 $$

推导过程：

1. 块指针总占用：$ m \times 8 $
2. 搜索键总占用：$ (m - 1) \times 12 $
3. 总占用不超过块大小 1024 字节

解得： $$ m \leq 51 $$

由于非叶节点的键数量为 $ m - 1 $，故最大键数量为 50。

• 节点特性：一个节点的子节点数量等于其包含的键数加 1。
• 树高变化：给定的树有 4 层，若插入一个新键导致树的高度增加一层，则在此过程中最多可能创建的新节点数为 5 个。

当插入新键导致 B 树高度增加时，分裂会从叶子节点开始，逐层向上进行。对于 4 层的 B 树：

1. 叶子节点分裂 → 新增 1 个节点；
2. 第二层节点分裂 → 新增 1 个节点；
3. 第三层节点分裂 → 新增 1 个节点；
4. 根节点分裂 → 新增 2 个节点（原根节点拆分为两个子节点，新增一个根节点）。

总计新增 1 + 1 + 1 + 2 = 5 个新节点。

两者的渐进时间复杂度都是 O(log n) 级别。

• 理论分析：B/B+ 树与红黑树的查找时间复杂度均为 O(log n)，但 B/B+ 树的底数更大（取决于节点容量），因此实际层级更少。
• 实际表现：由于 B/B+ 树更适合磁盘 I/O 操作，其常数因子更优，但在内存数据结构中，红黑树的实现效率可能更高。
• 结论：选项 B 的表述存在误导性，因为“通常优于”忽略了具体应用场景的差异。

键值大小 = 14 字节（已知）
子指针 = 6 字节（已知）

计算公式推导
B+ 树内部节点存储结构满足：
$$ \text{块大小} \geq (n - 1) \times \text{键值大小} + n \times \text{子指针大小} $$
代入已知数值：
$$ 512 \geq (n - 1) \times 14 + n \times 6 $$
展开并化简：
$$ 512 \geq 14n - 14 + 6n \quad \Rightarrow \quad 512 \geq 20n - 14 $$
$$ 20n \leq 526 \quad \Rightarrow \quad n \leq \frac{526}{20} = 26.3 $$

结论
由于阶数 $n$ 必须为整数，向下取整后 $n = 26$。因此选项 (C) 正确。

注：B+ 树内部节点的阶数定义为最大子节点数，而非键值对数量。本题通过容量约束反推最大可能的 $n$ 值。

解析：

• 当 B 树需要分裂时，每个层级都可能产生一个新节点。
• 由于树有四层（根节点到叶节点），最坏情况下每层都会发生一次分裂，因此最多会创建 4 个新节点。
• 但根节点分裂时会产生两个子节点，因此总共有 4 + 1 = 5 个新节点。

我们需要计算 B+ 树中最多需要访问的节点数，因此需考虑最小填充因子。已知记录数=100 万=10⁶（给定），B+ 树的阶数=每个节点的指针数=p=100（给定）。

计算步骤：

1. 最小指针数：每个节点的最小指针数=⌈p/2⌉=⌈100/2⌉=50
2. 最后一层节点数：10⁶ / 50 = 2×10⁴
3. 倒数第二层节点数：2×10⁴ / 50 = 400
4. 倒数第三层节点数：400 / 50 = 8
5. 倒数第四层节点数：8 / 50 = 1

结论：
B+ 树的层级数=4，因此最多需要访问 4 个节点。选项 (B) 正确。

在 B 树和 B+ 树中，所有叶节点的深度（根节点到叶节点的路径长度）是相同的。插入和删除操作会确保这一点。具体特性包括：

• 严格平衡机制：通过插入时从根节点增加高度（而非像 BST 从叶节点增加），删除时将根节点下移一级（不同于 BST 从底部收缩），从而保证所有叶节点深度一致。
• 对比 BST 的差异：
  • BST 插入/删除可能导致树高变化集中在叶节点
  • B+ 树通过自顶向下的高度调整维持全局平衡
• 实现保障：这种设计使得查询性能具有确定性，所有查找路径长度相同，是数据库索引选择 B+ 树的核心原因。

逐一分析各个选项：

• 选项 A 错误：B 树和 B+ 树都用于磁盘存储数据。
• 选项 B 正确：B+ 树通过叶节点间的链式连接实现范围查询的线性遍历，而 B 树需遍历整棵树。数据库常用 B+ 树索引，因其叶节点链表特性显著提升范围查询效率。
• 选项 C 错误：B 树与 B+ 树均可用于主索引和次级索引，二者并无此限制。
• 选项 D 错误：树的高度由记录数量及节点最大键值数（树的阶数）共同决定。