B树和B+树是用于文件系统、数据库索引等场景中的平衡多路搜索树，它们旨在高效处理大规模数据的存储和查找，特别是在磁盘或外存中。

B树（B-Tree）

定义：

B树是一种自平衡的多路搜索树，它的每个节点可以有多个子节点和键值。它的高度始终接近对数级别，能高效支持插入、删除和查找操作。

特性：

  1. 节点的键值有序：

    • 每个节点存储 ( k )个键值，满足 ( t - 1 \leq k \leq 2t - 1 )（其中 ( t ) 是树的阶数）。
    • 所有键值从小到大排列，左子树的键值小于父节点键值，右子树的键值大于父节点键值。

  2. 平衡性：

    • 所有叶子节点位于同一层，树的高度始终保持平衡。

  3. 子节点个数：

    • 每个非叶子节点有 ( k+1 ) 个子节点，满足 ( t \leq k+1 \leq 2t )。

  4. 动态性：

    • 支持动态增删操作，插入和删除可能引发分裂或合并操作以维持平衡。

  5. 查找路径：

    • 查找某键值时，会在每个节点的键值数组中二分查找，然后递归到相应的子树。

操作复杂度：

  • 查找、插入、删除的时间复杂度均为 ( O(\log n) )。

B+树

定义：

B+树是B树的一种变体，优化了范围查询操作。在B+树中，所有数据都存储在叶子节点，非叶子节点仅存储索引信息。

特性：

  1. 数据存储在叶子节点：

    • 叶子节点包含所有键值和实际数据的指针。
    • 非叶子节点只存储键值，用作索引。

  2. 链表结构：

    • 所有叶子节点通过指针链接，形成一个有序链表，方便范围查询。

  3. 更高的节点利用率：

    • 因为非叶子节点只存储索引信息，单个节点可以容纳更多索引，树的高度比B树更低。

  4. 查找分两步：

    • 先在非叶子节点中定位区间，再在叶子节点中进行实际查找。

操作复杂度：

  • 查找、插入、删除的时间复杂度与B树相同，为 ( O(\log n) )。
  • 范围查询非常高效，因为叶子节点按顺序链表连接。

B树 vs B+树

特性 B树 B+树
数据存储位置 数据存储在非叶子节点和叶子节点。 数据只存储在叶子节点，非叶子节点仅存索引。
范围查询效率 需要在整棵树中查找多个节点。 叶子节点通过链表连接，范围查询更高效。
树的高度 较高，因为每个节点的存储效率稍低。 较低，因为非叶子节点只存索引，可存更多信息。
空间利用率 相对较低，因为节点存储数据和索引。 相对较高，因为非叶子节点只存索引。
查询复杂度 查询路径可能在非叶子节点找到结果。 查询必须到叶子节点，路径更固定。
适用场景 一般查找和插入较多的场景。 范围查询、顺序遍历操作频繁的场景（如数据库）。

总结

  • B树更通用，适合动态更新场景。
  • B+树优化了顺序存取和范围查询，特别适用于文件系统和数据库索引。