B+树

基本概念

B+树是B树的一种变形，专门为磁盘存储和数据库系统设计的平衡多路搜索树
关键特征
- 所有数据都储存在叶子节点
- 内部节点只存储键值，不存储数据
- 叶子节点之间用链表连接
- 支持高效的范围查询

B树的结构特点

示意图

graph TD subgraph "B+树结构示例 (m=4)" A["根节点
[30, 60]"] B["内部节点
[10, 20]"] C["内部节点
[40, 50]"] D["内部节点
[70, 80]"] E["叶子节点
[5, 8, 10]
data"] F["叶子节点
[15, 18, 20]
data"] G["叶子节点
[25, 28, 30]
data"] H["叶子节点
[35, 38, 40]
data"] I["叶子节点
[45, 48, 50]
data"] J["叶子节点
[55, 58, 60]
data"] K["叶子节点
[65, 68, 70]
data"] L["叶子节点
[75, 78, 80]
data"] M["叶子节点
[85, 88, 90]
data"] A --> B A --> C A --> D B --> E B --> F B --> G C --> H C --> I C --> J D --> K D --> L D --> M E -.-> F F -.-> G G -.-> H H -.-> I I -.-> J J -.-> K K -.-> L L -.-> M end style A fill:#ffcccc style B fill:#ffffcc style C fill:#ffffcc style D fill:#ffffcc style E fill:#ccffcc style F fill:#ccffcc style G fill:#ccffcc style H fill:#ccffcc style I fill:#ccffcc style J fill:#ccffcc style K fill:#ccffcc style L fill:#ccffcc style M fill:#ccffcc

节点结构

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


struct InternalNode{
    int keyCount;
    KeyType keys[m-1];
    Node* children[m];
    bool isLeaf = false;
}; //内部节点定义

struct LeafNode{
    int ketCount;
    KeyType keys[m];
    DataType data[m];
    LeafNode* next;
    bool isLeaf = true;
}; //叶子节点定义

B+树的性质定义

阶数(Order)的定义

对于m阶B+树
- 根节点：至少有2个子节点（非叶子根节点）
- 内部节点：至少有$\lceil m/2 \rceil$个子节点，至多有m个子节点
- 叶子节点：至少有$\lceil m/2 \rceil$个键值，至多有m个键值
- 所有叶子节点在同一层（完全平衡）

B+树的关键特性

特性1：叶子节点链表
- 所有叶子节点通过指针连接成有序链表
  - 支持高效的范围查询
  - 支持顺序访问
  - 支持快速的区间扫描
- 示例：查找范围[25, 65]
  1. 定位到第一个叶子节点（包含25）
  2. 沿着链表顺序访问，直到65
  3. 无需回到内部节点
特性2：数据存储的分离
- 内部节点
  - 只存储键值和指针
  - 不存储实际数据
  - 纯粹的索引结构
- 叶子节点
  - 存储键值和对应地数据
  - 是唯一地数据存储位置
  - 所有查询最终都要到达叶子节点
特性3：键值的冗余
- B+树中的键值存在冗余
  - 内部节点的键值也会出现在叶子节点中
  - 内部节点的键值起到路标作用
  - 叶子节点的键值关联实际数据
- 示例：
  - 内部节点有键30：表示“大于等于30的数据在右子树”
  - 叶子节点有间30：表示存储键30对应的实际数据

B+树的基本操作

查找

单点查找

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27


DataType search(KeyType key) {
    Node* current = root;
    
    // 从根节点向下搜索到叶子节点
    while (!current->isLeaf) {
        InternalNode* internal = (InternalNode*)current;
        int i = 0;
        
        // 找到合适的子节点
        while (i < internal->keyCount && key >= internal->keys[i]) {
            i++;
        }
        current = internal->children[i];
    }
    
    // 在叶子节点中查找
    LeafNode* leaf = (LeafNode*)current;
    for (int i = 0; i < leaf->keyCount; i++) {
        if (leaf->keys[i] == key) {
            return leaf->data[i];
        }
    }
    
    return NULL; // 未找到
}

// 时间复杂度：O(log_m n)

范围查找

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


vector<DataType> rangeSearch(KeyType start, KeyType end) {
    vector<DataType> result;
    
    // 1. 找到起始叶子节点
    LeafNode* current = findLeafNode(start);
    
    // 2. 沿着叶子链表扫描
    while (current != nullptr) {
        for (int i = 0; i < current->keyCount; i++) {
            if (current->keys[i] >= start && current->keys[i] <= end) {
                result.push_back(current->data[i]);
            }
            if (current->keys[i] > end) {
                return result; // 超出范围，结束
            }
        }
        current = current->next; // 移到下一个叶子节点
    }
    
    return result;
}

// 范围查询的优势：
// - 只需要一次定位到起始位置
// - 后续是顺序的链表遍历
// - 无需重复搜索内部节点

插入操作

插入过程

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


void insert(KeyType key, DataType data) {
    // 1. 找到应该插入的叶子节点
    LeafNode* leaf = findLeafNode(key);
    
    // 2. 在叶子节点中插入
    insertIntoLeaf(leaf, key, data);
    
    // 3. 检查是否需要分裂
    if (leaf->keyCount > m) {
        splitLeaf(leaf);
    }
}

叶子节点分裂

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


void splitLeaf(LeafNode* oldLeaf) {
    // 创建新的叶子节点
    LeafNode* newLeaf = new LeafNode();
    
    int mid = (m + 1) / 2;
    
    // 将一半键值移到新节点
    for (int i = mid; i < oldLeaf->keyCount; i++) {
        newLeaf->keys[i - mid] = oldLeaf->keys[i];
        newLeaf->data[i - mid] = oldLeaf->data[i];
    }
    
    newLeaf->keyCount = oldLeaf->keyCount - mid;
    oldLeaf->keyCount = mid;
    
    // 更新链表指针
    newLeaf->next = oldLeaf->next;
    oldLeaf->next = newLeaf;
    
    // 向父节点插入新的键值
    KeyType upKey = newLeaf->keys[0];
    insertIntoParent(oldLeaf, upKey, newLeaf);
}

内部节点分裂

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


void splitInternal(InternalNode* oldNode) {
    InternalNode* newNode = new InternalNode();
    
    int mid = m / 2;
    KeyType upKey = oldNode->keys[mid];
    
    // 移动键值和子节点
    for (int i = mid + 1; i < oldNode->keyCount; i++) {
        newNode->keys[i - mid - 1] = oldNode->keys[i];
    }
    
    for (int i = mid + 1; i <= oldNode->keyCount; i++) {
        newNode->children[i - mid - 1] = oldNode->children[i];
    }
    
    newNode->keyCount = oldNode->keyCount - mid - 1;
    oldNode->keyCount = mid;
    
    // 向上传播
    insertIntoParent(oldNode, upKey, newNode);
}

删除操作

删除过程

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


void remove(KeyType key) {
    // 1. 找到包含key的叶子节点
    LeafNode* leaf = findLeafNode(key);
    
    // 2. 从叶子节点删除key
    removeFromLeaf(leaf, key);
    
    // 3. 检查是否需要合并或重分布
    if (leaf->keyCount < ceil(m / 2.0)) {
        handleUnderflow(leaf);
    }
}

处理下溢出

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


void handleUnderflow(LeafNode* node) {
    LeafNode* sibling = findSibling(node);
    
    if (sibling->keyCount > ceil(m / 2.0)) {
        // 情况1：兄弟节点有多余键值，重分布
        redistribute(node, sibling);
    } else {
        // 情况2：兄弟节点也是最少键值，合并
        merge(node, sibling);
    }
}