B树与B+树

B树（Balanced Tree）

引入

B树是一种 平衡的多叉树数据结构，曾经广泛应用于数据库和文件系统中，用于高效地管理大量数据。B树可以高效地支持查找、插入和删除操作，其时间复杂度为 $O(logn)$。

B树的结构

一个阶为 m 的 B 树满足以下性质：

1. 每个节点最多有 m 个子节点。
2. 除了根节点以外，每个非叶子节点至少有 $\lceil m/2\rceil$个子节点。
3. 如果根节点不是叶子节点，则至少有 2 个子节点。
4. 所有叶子节点都位于同一层。
5. 每个节点存储最多$m-1$ 个关键字，最少存储 $\lceil m/2\rceil -1$个关键字。

图示：

B树的特点

1. 平衡性：B树是一种平衡树，所有叶子节点在同一层上。
2. 节点的键值范围：
   • 一个 B 树节点最多可以包含 $m-1$ 个关键字（键值），其中 m 是 B 树的阶数（即节点的最大子节点数）。
   • 每个节点的关键字按照递增顺序排列。
   • 除了根节点以外，其他节点至少有 $\lceil m/2\rceil -1$ 个关键字（至少 $\lceil m/2\rceil$ 个子节点）。
3. 分支（子节点）规则：
   • 一个包含 k 个关键字的节点最多有 k+1 个子节点。
   • 子树中所有关键字的值都满足以下规则：
     • 左子树的所有关键字 < 当前节点的关键字 < 右子树的所有关键字。
4. 动态性：B树能够动态地增长或缩小，保持平衡。
5. 查找、插入和删除效率高：B树的高度随着数据量的增加增长较慢（对数关系），因此在海量数据下仍然可以高效操作。

B树的基本操作

1. 查找

B树的查找过程类似于二叉搜索树，但由于每个节点包含多个关键字，因此需要顺序地比较关键字：

1. 从根节点开始，顺序比较当前节点中的关键字。
2. 如果找到关键字，返回。
3. 如果关键字小于当前关键字，则转向左子树；如果关键字大于当前关键字，则转向右子树。
4. 重复上述过程，直到找到关键字或到达叶子节点（查找失败）。

查找的时间复杂度为 $O(logn)$。

---

2. 插入

B树的插入操作需要保证树的平衡性，遵循以下步骤：

1. 找到插入位置：根据查找操作，找到需要插入关键字的叶子节点。
2. 插入关键字：将关键字插入到叶子节点中。
3. 分裂节点（必要时）：
   • 如果插入后某个节点中的关键字数超过了 $m-1$（最大容量），则需要将该节点分裂：
     • 将中间的关键字提到父节点中。
     • 将分裂节点分为两个子节点。
   • 如果父节点也满了，则递归向上分裂，可能会导致根节点的分裂，树的高度增加。

---

3. 删除

B树的删除操作需要考虑多种情况，同时保持树的平衡性：

1. 删除叶子节点的关键字：直接删除关键字即可。
2. 删除非叶子节点的关键字：
   • 用前驱或后继关键字替代被删除的关键字，然后递归删除替代关键字。
3. 节点合并（必要时）：
   • 如果删除后节点中的关键字数少于 $\lceil m/2\rceil -1$，则需要与相邻节点合并，或者从相邻兄弟节点借关键字。
   • 如果父节点也因此不满足要求，则递归向上调整。

示例

3 阶 B-树依次插⼊ $\text{\&\#123;3, 2, 1, 4, 5, 6, 9 \&\#125;}$再按照同样的顺序删除。依次画出 B-树的变化

插入

1. 步骤 1：插入 3 初始为空树，将 3 插入根节点：

[3]

---

2. 步骤 2：插入 2 将 2 插入根节点（保持排序）：

[2, 3]

---

3. 步骤 3：插入 1 将 1 插入根节点（保持排序）：

[1, 2, 3]

节点已满（包含 3 个关键字），需要分裂：

1. 将中间关键字 2 提升为新根节点。
2. 将当前节点分裂为两个子节点：左子节点[1] 和右子节点 [3]。
3. 结果：

    [2]
   /   \
 [1]   [3]

---

4. 步骤 4：插入 4 将 4 插入到合适的子节点（右子节点 [3]）：

    [2]
   /   \
 [1]   [3, 4]

---

5. 步骤 5：插入 5 将 5 插入到右子节点 [3, 4]（保持排序）：

    [2]
   /   \
 [1]   [3, 4, 5]

右子节点已满（包含 3 个关键字），需要分裂：

1. 将中间关键字 4 提升到根节点。
2. 将右子节点分裂为两个子节点：左子节点 [3] 和右子节点 [5]。

结果：

      [2, 4]
     /  |   \
   [1] [3]  [5]

---

6. 步骤 6：插入 6 将 6 插入到合适的子节点（右子节点 [5]）：

      [2, 4]
     /  |   \
   [1] [3]  [5, 6]

---

7. 步骤 7：插入 9 将 9 插入到右子节点 [5, 6]：

      [2, 4]
     /  |   \
   [1] [3]  [5, 6, 9]

右子节点已满（包含 3 个关键字），需要分裂：

1. 将中间关键字 6 提升到根节点。
2. 将右子节点分裂为两个子节点：左子节点 [5] 和右子节点 [9]。 结果：

         [2, 4, 6]
        /   |   |   \
      [1]  [3] [5]  [9]

---

删除

初始 B 树结构 在插入了 3, 2, 1, 4, 5, 6, 9 后，得到的 3 阶 B 树结构如下：

         [2, 4, 6]
        /   |   |   \
      [1]  [3] [5]  [9]

---

1. 步骤 1：删除 3

• 3 是一个 叶子节点，直接删除即可。 结果：

         [2, 4, 6]
        /   |   |   \
      [1]   [] [5]  [9]

---

2. 步骤 2：删除 2

• 2 是一个 非叶子节点，需要用它的后继关键字 4 替代它（后继关键字是右子树的最小值）。
• 删除 2 后，还需调整节点结构。

结果：

         [4, 6]
        /   |   \
      [1]  []  [5] [9]

---

3. 步骤 3：删除 1

• 1 是一个 叶子节点，直接删除即可。 结果：

         [4, 6]
        /   |   \
      []  []  [5]  [9]

---

4. 步骤 4：删除 4

• 4 是根节点中的关键字，需要用后继关键字 5 替代它（右子树的最小值）。 结果：

         [5, 6]
        /   |   \
      []  []  []  [9]

---

5. 步骤 5：删除 5

• 5 是一个非叶子节点，用后继关键字 6 替代它。 结果：

         [6]
        /   \
      []   [9]

---

6. 步骤 6：删除 6

• 6 是根节点，用它的后继关键字 99 替代它。 结果：

         [9]

---

7. 步骤 7：删除 9

• 9 是根节点，也是唯一的节点，直接删除即可。 结果：

空树

---

最终结果 按照 3, 2, 1, 4, 5, 6, 9 的顺序删除后，B 树最终为空树。

B树的优点

1. 平衡性：所有叶子节点在同一层，避免了树的不平衡问题。
2. 高效性：由于每个节点可以存储多个关键字，B树的高度比二叉搜索树低，查找、插入、删除的效率更高。
3. 适合磁盘存储：B树的设计考虑了磁盘 I/O 的特性，通过减少树的高度和磁盘访问次数来提高性能。
4. 动态性：B树能够动态地调整大小，适用于动态变化的数据。

B树的应用

1. 数据库索引：
   • 大多数关系型数据库（如 MySQL 的 InnoDB）使用 B+树（B树的变种）作为索引结构。
2. 文件系统：
   • 文件系统（如 NTFS、EXT4）使用 B树或 B+树来管理目录和文件数据。
3. 键值存储：
   • 一些键值存储（如 LevelDB 和 SQLite）也使用 B树或其变种来管理存储。

参考资料

• B 树 - 维基百科，自由的百科全书
• B 树详解
• B 树、B + 树索引算法原理（上）
• B 树，B + 树详解

B+树

B+树是B树的一种变体，广泛用于数据库系统和文件系统中，尤其在索引结构中占据核心地位。相比于B树，B+树对查询、范围查找和磁盘存储做了优化，更加高效。

---

B+树的特点

B+树具有以下特点：

1. 多叉平衡树：和B树一样，B+树是一种多叉平衡树，所有的叶子节点都在同一层，树的高度是平衡的。
2. 数据仅存储在叶子节点：
   • 非叶子节点只存储索引键值（key），而不存储实际数据。
   • 所有实际数据都存储在叶子节点中。
3. 叶子节点链表：
   • 叶子节点通过指针按顺序连接，形成一个有序链表。
   • 这种设计使得范围查询、区间查询非常高效。
4. 磁盘友好：
   • B+树通过非叶子节点存储更多的索引键值，减少树的高度，从而减少磁盘I/O操作。

---

B+树的结构

1. 非叶子节点（索引节点）：
   • 非叶子节点只存储索引键值，用于引导查找的路径。
   • 一个非叶子节点最多包含 m−1 个键值和 m 个子节点指针（阶为 m）。
   • 非叶子节点的键值不会重复出现在叶子节点中。
2. 叶子节点：
   • 叶子节点包含所有的实际数据记录。
   • 叶子节点按键值顺序排列，并通过链表指针连接，形成一个有序链表。
   • 每个叶子节点存储 nn 个键值及对应的数据指针，$\lceil m/2\rceil \le n\le m-1$。

---

B+树的基本操作

1. 查找

• 查找操作的目标是从根节点开始，沿着索引键值找到叶子节点。
• 查找过程：
  1. 从根节点开始，按照索引键值的大小选择对应的子节点指针。
  2. 重复步骤1，直到到达叶子节点。
  3. 在叶子节点中查找目标键值，返回对应的数据指针。
• 范围查询：
  • 找到范围的起始叶子节点后，通过叶子节点链表直接遍历，获取所有符合范围的值。

时间复杂度：O(log⁡n)，树的高度是对数级的。

---

2. 插入

插入操作的目标是将新键值插入到B+树中，同时保证树的平衡性。

• 插入过程：
  1. 查找目标叶子节点，找到新键值的插入位置。
  2. 将新键值插入叶子节点中。
  3. 如果叶子节点的键值个数超过了最大限制（即 m−1），则需要进行分裂：
     • 将叶子节点分裂成两个节点，其中一半的键值移动到新节点中。
     • 将中间的键值提升到父节点，形成新的索引键值。
  4. 如果父节点也满了，则递归向上分裂，可能会导致根节点分裂，增加树的高度。

时间复杂度：O(log⁡n)，与树的高度相关。

---

3. 删除

删除操作的目标是从B+树中移除某个键值，同时保持树的平衡性。

• 删除过程：
  1. 查找目标键值所在的叶子节点。
  2. 从叶子节点中删除目标键值。
  3. 如果删除后叶子节点的键值个数少于最小限制（即 $\lceil m/2\rceil -1$），需要进行合并或借用：
     • 如果相邻的兄弟节点有多余的键值（超过最小限制），则从兄弟节点中借用一个键值。
     • 如果兄弟节点的键值个数也少于最小限制，则将当前节点和兄弟节点合并，删除父节点中的索引键值。
  4. 如果父节点也不满足最小限制，则递归向上调整，可能会导致树的高度减少。

时间复杂度：O(log⁡n)。

---

*+树的优点

1. 高效的查询和范围操作：
   • 通过叶子节点的链表结构，B+树对范围查询和顺序访问特别高效。
2. 稳定的查询性能：
   • 所有查询都必须访问到叶子节点，性能更稳定。
3. 磁盘I/O优化：
   • B+树的非叶子节点不存储数据，可以存储更多的索引键值，降低了树的高度，从而减少磁盘I/O次数。
4. 动态调整：
   • 支持动态插入和删除操作，能够自动保持平衡。

---

B+树的实际应用

1. 数据库索引：

   • MySQL 的 InnoDB 存储引擎使用 B+树作为其主键索引和二级索引。
   • 主键索引（聚簇索引）中的叶子节点存储实际的数据行。
   • 二级索引（非聚簇索引）中的叶子节点存储指向主键的指针。

2. 文件系统：

   • 文件系统（如 NTFS 和 EXT4）使用 B+树来管理文件元数据和目录信息。

3. 键值存储：

   • 一些键值存储系统（如 LevelDB 和 RocksDB）在存储索引时也使用 B+树。

---

总结

• B+树的结构：
  • 非叶子节点只存储索引，叶子节点存储所有实际数据。
  • 叶子节点通过链表相连，支持高效的范围查询。
• 优势：
  • 查询性能稳定。
  • 范围查询高效。
  • 磁盘友好。
• 应用：
  • 数据库系统（如 MySQL）。
  • 文件系统（如 NTFS、EXT4）。
  • 键值存储系统（如 LevelDB）。

通过 B+树的多层索引结构和叶子节点链表，B+树在大规模数据管理中非常高效，是现代数据库和文件系统的核心数据结构。

B+树和B树的主要区别

特点	B树	B+树
数据存储	数据和索引都存储在每个节点中。	数据仅存储在叶子节点中，非叶子节点只存储索引键值。
查询路径	查找时可能在非叶子节点停止（找到数据）。	查找时一定会找到叶子节点。
范围查询	范围查询效率低（需要中序遍历整个树）。	范围查询效率高（通过叶子节点链表直接遍历）。
空间利用率	较低（每个节点既存索引又存数据）。	较高（非叶子节点存储更多索引键值）。
查找性能	查询性能不稳定，可能在非叶子节点结束查询。	查询性能稳定，所有查询都需访问叶子节点。