Skip to content

B+树介绍

B+树（B+-Tree）是一种为磁盘或其他块存储设备优化的自平衡树数据结构，广泛应用于数据库和文件系统的索引。它是B树的一种变体，特别擅长范围查询和顺序访问。

B+树的主要特性

  1. 平衡性：所有叶子节点都在同一深度，确保了稳定的查询性能。
  2. 多路性：每个内部节点可以有多个子节点（远超2个），使得树的高度相对较低，减少磁盘I/O。
  3. 数据仅在叶子节点：所有数据记录（或指向数据的指针）都存储在叶子节点。内部节点仅存储键（作为索引）和指向子节点的指针。
  4. 叶子节点链表：所有叶子节点通过指针串联起来，形成一个有序链表，便于范围查询和顺序扫描。
  5. 键的冗余：内部节点中的键是其右子树中最小键的副本（或者是其左子树中最大键的副本，具体实现略有不同），这些键也会出现在叶子节点中。

B+树的查找过程始终是从根节点开始，逐层向下，最终在叶子节点中找到目标键（如果存在）或确定键不存在。

假设我们要查找一个键 target_key：

  1. 从根节点开始：

    • 读取根节点到内存中（如果它不在内存）。
    • 在当前节点（初始为根节点）的键列表中，通过比较 target_key 与节点中的各个键（K_1, K_2, ..., K_n），找到一个合适的区间。
      • 如果 target_key < K_1，则沿着第一个指针 P_0 指向的子节点继续查找。
      • 如果 K_i <= target_key < K_{i+1}，则沿着指针 P_i 指向的子节点继续查找。
      • 如果 target_key >= K_n（n是节点中最后一个键的索引），则沿着最后一个指针 P_n 指向的子节点继续查找。
    • 由于节点内的键是有序的，这个区间的查找可以使用二分查找（如果键较多）或顺序查找（如果键较少）。

  2. 递归/迭代向下：

    • 根据上一步确定的指针，移动到下一个子节点。
    • 重复步骤1中的比较和选择过程，在新的当前节点中找到下一个要访问的子节点。
    • 这个过程一直持续，直到到达一个叶子节点。

  3. 在叶子节点中查找：

    • 当到达叶子节点时，读取该叶子节点到内存。
    • 在叶子节点的键列表中查找 target_key。叶子节点中的键也是有序的，同样可以使用二分查找或顺序查找。
    • 如果找到了 target_key：
      • 那么与该键关联的数据（或指向数据的指针）也存储在这个叶子节点中，查找成功，返回数据。
    • 如果未找到 target_key：
      • 由于B+树的特性（所有键及其数据都在叶子节点，并且叶子节点有序），如果在叶子节点中都找不到，那么该键在整个B+树中就不存在。查找失败。

B+树查找的时间复杂度

B+树的查找时间复杂度主要由树的高度和在每个节点内部查找键的时间决定。

  • 树的高度（h）：

    • 一个m阶B+树（每个内部节点最多有m个子节点，最少有 ceil(m/2) 个子节点），如果包含N个键（通常指叶子节点中的键数量），其高度h大致为 O(log_m N)。
    • 由于m通常很大（例如，一个磁盘页可以容纳几十到几百个键和指针），所以树的高度h非常低。例如，一个千万级别记录的表，其B+树索引的高度可能只有3-4层。
    • 每次从一层移动到下一层，通常对应一次磁盘I/O操作（如果节点不在内存缓冲池中）。所以，查找过程中的主要时间开销是磁盘I/O的次数，它与树的高度成正比。

  • 节点内部查找时间：

    • 在每个节点内部（无论是内部节点还是叶子节点），需要查找合适的键或指针。如果一个节点内有k个键，使用二分查找的时间复杂度是 O(log k)。
    • 由于k（即节点内键的数量，通常与m相关）相对于N来说是一个很小的常数（或者说，m是固定的阶数，k <= m-1），所以节点内部的查找时间通常被认为是常数时间，或者是一个远小于树高度影响的因素。
    • 即使不使用二分查找，而是顺序扫描（对于k较小的情况可能更快），其时间也是与m相关的常数。

综合来看： * 查找操作需要从根节点到叶子节点访问h个节点。 * 每次访问一个节点，最坏情况需要一次磁盘I/O。 * 在每个节点内部查找的时间复杂度为 O(log m) 或 O(m)（如果顺序扫描）。

因此，B+树的查找时间复杂度通常表示为 O(h * log m) 或 O(h * m)。然而，在分析数据库索引性能时，更关注的是I/O次数，所以通常简化为 O(log_m N) 次磁盘I/O。由于CPU操作远快于磁盘I/O，所以磁盘I/O的次数是决定性因素。

如果考虑到数据完全在内存中的情况（例如，整个索引树都被缓存了），那么时间复杂度就是 O(h * log m)，这仍然是对数级别的，非常高效。

假设我们有一个3阶B+树（m=3），意味着每个内部节点最多有3个孩子和2个键，叶子节点也存储键和数据。

假设树结构如下（简化表示，K是键，P是指针，D是数据）：

           [K5, K10] (Root)
          /    |    \
   P0(<K5) P1(K5-K10) P2(>=K10)
      |        |          |
  [D1,D2,D3] [D6,D7,D8] [D11,D12,D13] (Leaf nodes, values represent keys, assume data Dx is associated with key x)
   (Keys:1,2,3) (Keys:6,7,8) (Keys:11,12,13)
   (Linked to next leaf) -> (Linked to next leaf) -> null

(实际B+树中内部节点只存键和指针，这里为了简化，假设K5, K10是分隔键，叶子节点D_x代表键为x的数据)

要查找键 target_key = 7：

  1. 从根节点 [K5, K10] 开始。

    • 比较 7 与 K5 (7 > 5)。
    • 比较 7 与 K10 (7 < 10)。
    • 所以 target_key 落在 K5 和 K10 之间，选择中间的指针 P1。

  2. 沿着指针 P1 到达其子节点，发现这是一个叶子节点 [D6,D7,D8] (键为6,7,8)。

    • 在该叶子节点中查找 7。
    • 找到键 7，获取其关联的数据 D7。
    • 查找成功。

如果要查找 target_key = 4： 1. 从根节点 [K5, K10] 开始。 * 比较 4 与 K5 (4 < 5)。 * 选择第一个指针 P0。

  1. 沿着指针 P0 到达其子节点，叶子节点 [D1,D2,D3] (键为1,2,3)。
    • 在该叶子节点中查找 4。
    • 4 大于叶子节点中所有键 (1,2,3)。
    • 查找失败，键 4 不存在。

![[1346871-20240730112327521-241140105.svg]]