B树，B+树，B*树

下面我们来详细讲解一下 B树、B+树、B*树 这三种非常重要的多路平衡查找树。它们在数据库和文件系统中有着极其广泛的应用。

一、为什么需要这些树结构？

在开始之前，我们先思考一个问题：为什么已经有了二叉搜索树（BST）、AVL树、红黑树，还需要B树家族？

答案是：磁盘I/O。

• 内存访问：速度极快，纳秒级别。
• 磁盘访问：速度极慢，毫秒级别，比内存慢了几个数量级。

操作系统从磁盘读取数据时，并不是按需一个字节一个字节地读，而是以页（Page，通常为4KB或8KB）为单位进行预读。一次I/O操作会把一整页的数据都加载到内存中。

传统的二叉树（如红黑树）虽然内存中效率很高，但每个节点只存储少量数据，如果数据量巨大，树会变得很高。查询一个数据可能需要从根节点访问到叶子节点，这期间可能发生很多次磁盘I/O（因为节点可能不在同一页），性能会急剧下降。

B树家族的设计目标就是为了减少磁盘I/O次数。它们的核心思想是：

一个节点 = 一个磁盘页

通过在每个节点中存储更多的键和指针，让树变得更“矮胖”，从而降低树的高度，减少查询时的I/O次数。

二、B树 (B-Tree)

B树是一种自平衡的多路搜索树，它不是二叉的，一个节点可以有多个子节点。

1. 结构特点

• 平衡性：所有叶子节点都位于同一层，保证了查询性能的稳定。
• 多路性：一个节点可以拥有多于两个的子节点。这通常用“阶”（m）来定义。一棵m阶的B树满足以下条件：
  • 每个节点最多有 m 个子节点。
  • 除根节点和叶子节点外，每个节点至少有 ceil(m/2) 个子节点（ceil是向上取整）。
  • 根节点至少有2个子节点（除非它同时也是叶子节点）。
  • 所有叶子节点都在同一层。
  • 一个有 k 个子节点的非叶子节点，包含 k-1 个键（Key）。
  • 节点中的键是有序的。

2. 节点结构

一个典型的B树节点包含：

• n 个键 K₁, K₂, ..., Kₙ。
• n+1 个指针 P₀, P₁, ..., Pₙ。
• 指针指向子节点，键和指针的排列满足：P₀指向的子树中所有键 < K₁ < P₁指向的子树中所有键 < K₂ < … < Kₙ < Pₙ指向的子树中所有键。

示例（3阶B树，也叫2-3树）：

        [ 20 | 40 ]/     |     \[10, 15] [30, 35] [50, 60]

• 每个节点最多有3个子节点，至少有2个子节点。
• 每个节点最多有2个键，至少有1个键。

3. 操作

• 查找：从根节点开始，将待查找的键与节点中的键比较，确定下一步要进入哪个子树，直到找到或到达叶子节点。
• 插入：找到合适的叶子节点插入。如果插入后节点键的数量超过 m-1，则节点分裂。中间的键向上提升到父节点，如果父节点也满了，则继续向上分裂，可能一直到根节点。
• 删除：比较复杂，可能需要从兄弟节点“借”键，或者与兄弟节点合并，甚至可能导致父节点的合并，是一个递归的过程。

4. 优缺点

• 优点：
  • 矮胖，树的高度低，I/O次数少，非常适合磁盘存储。
  • 查询、插入、删除的时间复杂度都为 O(logₘN)，其中N是键的数量，m是阶数。
• 缺点：
  • 每个节点都存储了键和数据（如果数据很大，节点能存的键就变少了，树会变高）。
  • 范围查询效率不高，因为数据分散在所有节点中，需要进行中序遍历，这会涉及大量的随机I/O。

三、B+树 (B+ Tree)

B+树是B树的变种，也是目前数据库索引中最常用的数据结构（如MySQL的InnoDB引擎）。它对B树做了优化，使其更适合范围查询和全表扫描。

1. 结构特点（与B树的区别）

B+树在B树的基础上增加了以下特性：

• 数据只在叶子节点：
  • 非叶子节点（索引节点）：只存储键和指向子节点的指针，不存储数据。这使得非叶子节点可以存储更多的键，树的结构更“矮胖”，I/O效率更高。
  • 叶子节点（数据节点）：存储了所有的键和对应的数据。
• 叶子节点形成有序链表：
  • 所有的叶子节点通过指针连接成一个双向有序链表。
  • 这使得范围查询变得极其高效，只需定位到范围的起始点，然后沿着链表顺序遍历即可，几乎都是顺序I/O。
• 查询效率更稳定：
  • 任何查询都必须从根节点走到叶子节点才能获取到数据。而B树可能在非叶子节点就命中数据。这使得B+树的每次查询的I/O次数更加稳定。

2. 图示

        [ 20 | 40 ]/     |     \[ 10 ]   [ 30 ]   [ 50 ]/         |         \
[10, Data] [30, Data] [50, Data]<--------> <--------> <--------> (双向链表)

• 上面的非叶子节点只做索引，不存数据。
• 下面的叶子节点存数据，并且用链表连接。

3. 优缺点

• 优点：
  • 更矮胖：由于非叶子节点不存数据，能容纳更多键，树高更低，I/O次数更少。
  • 查询性能稳定：每次查询都必须查到叶子节点，性能稳定。
  • 范围查询极其高效：叶子节点的有序链表结构，使得范围查询和排序操作非常快。
  • 全表扫描快：只需遍历叶子节点的链表即可。
• 缺点：
  • 单点查询（根据主键查一条记录）可能比B树稍慢，因为B树可能在非叶子节点就找到数据，而B+树必须走到叶子节点。但在实际应用中，由于B+树更矮胖，这个劣势通常不明显，甚至可能更快。

四、B*树 (B* Tree)

B*树是B树的另一个变种，它的目标是进一步提高节点的空间利用率。

1. 结构特点（与B树的区别）

B*树的核心思想是增加节点的填充率，从而减少节点分裂的频率。

• 更高的填充因子：
  • B树要求每个非根、非叶节点至少半满（ceil(m/2)）。
  • B*树要求每个非根、非叶节点至少 2/3满（ceil(2m/3)）。
• 独特的分裂策略：
  • 当一个节点满了需要插入新数据时，B*树不会立即分裂。
  • 它会先检查其相邻的兄弟节点是否还有空间。
  • 如果兄弟节点未满：将当前节点和兄弟节点的键重新分配，让两个节点都达到2/3满。这个过程称为节点重分配。
  • 如果兄弟节点也满了：才会进行分裂。但B*树的分裂也与B树不同。它不是将一个节点分成两个，而是将当前节点和它的一个兄弟节点一起分裂成三个节点，并保证这三个节点都是2/3满的。

2. 优缺点

• 优点：
  • 极高的空间利用率：由于2/3的填充因子和延迟分裂策略，节点的空间利用率非常高，浪费的空间很少。
  • 更少的分裂操作：节点重分配和“分裂成三”的策略大大降低了节点分裂的频率，从而减少了I/O操作，提高了插入性能。
• 缺点：
  • 实现复杂：插入和删除的逻辑比B树和B+树复杂得多，需要处理节点重分配和复杂的分裂逻辑。
  • 应用较少：由于其复杂性，B*树在实际应用中不如B+树普及。但在一些对空间利用率和插入性能要求极高的文件系统中，可能会看到它的身影。

总结与对比

一句话总结

• B树：是“矮胖”的多路树，解决了磁盘I/O问题，但数据分散，不适合范围查询。
• B+树：在B树基础上，将数据全部移到叶子节点并用链表连接，完美优化了范围查询，成为数据库索引的事实标准。
• B*树：在B树基础上，通过提高填充率和改进分裂策略，极致地优化了空间利用率和插入性能，但实现复杂，应用较少。