B 树与 B + 树解析与实现

一、磁盘存储优化的核心逻辑

在大规模数据处理场景中，磁盘 I/O 效率是性能瓶颈的核心。磁盘访问具有以下特性：

随机访问成本高：磁头寻道时间（Seek Time）可达毫秒级，相比内存访问（纳秒级）慢百万倍。
顺序访问效率高：连续扇区的读取速度比随机读取快 10 倍以上。
页存储机制：磁盘以页（Page，通常 4KB/8KB/16KB）为单位读写数据，单次 I/O 操作读取完整一页。

B 树与 B + 树通过以下设计优化磁盘访问：

矮胖树结构：每个节点存储多个键值，减少树的高度（通常 3-4 层即可支撑百万级数据）。
顺序访问支持：B + 树的叶子节点通过链表连接，实现高效范围查询。
节点对齐页大小：节点大小等于磁盘页，单次 I/O 读取完整节点，减少碎片。

二、B 树：平衡多路搜索树的基石

2.1 核心结构与规则

B 树是一种自平衡的多路搜索树，其核心规则如下：

节点容量：每个节点最多有m个子节点（m为阶数），最少有⌈m/2⌉个子节点。
键值分布：节点内键值有序排列，左子树键值 < 当前键值 < 右子树键值。
平衡条件：所有叶子节点位于同一层，根节点至少有 2 个子节点（除非树高为 1）。
节点分裂与合并：插入 / 删除操作导致节点溢出或不足时，通过分裂 / 合并保持平衡。

示例结构（m=3）

2.2 关键操作详解

插入操作（以 m=3 为例）

查找插入位置：从根节点开始，逐层向下找到目标叶子节点。
处理节点溢出：
- 若叶子节点已满（键值数 = m-1），分裂为左右两部分，中间键值提升至父节点。
- 若父节点溢出，递归向上分裂，可能导致树高增加。

删除操作（以 m=3 为例）

查找删除位置：定位到包含目标键值的节点。
处理节点不足：
- 若删除后节点键值数 <⌈m/2⌉-1，从兄弟节点借键或与兄弟节点合并。
- 若父节点键值数不足，递归向上处理。

2.3 代码实现

#include <vector>
#include <algorithm>
#include <stdexcept>// B树节点类模板
template <typename T, int M>  // M为B树的阶数
class BTreeNode {
public:std::vector<T> keys;                  // 存储键值std::vector<BTreeNode<T, M>*> children;  // 存储子节点指针bool is_leaf;                         // 是否为叶子节点// 构造函数BTreeNode(bool leaf = true) : is_leaf(leaf) {}
};// B树类模板
template <typename T, int M>
class BTree {
private:BTreeNode<T, M>* root;  // 根节点指针// 分裂子节点：将full_child分裂为两个节点void splitChild(BTreeNode<T, M>* parent, int child_idx) {BTreeNode<T, M>* full_child = parent->children[child_idx];BTreeNode<T, M>* new_node = new BTreeNode<T, M>(full_child->is_leaf);int mid = M / 2;// 复制中间键右侧的键到新节点for (int i = mid + 1; i < M; ++i) {new_node->keys.push_back(full_child->keys[i]);}full_child->keys.resize(mid);  // 保留中间键左侧的键// 如果不是叶子节点，复制子节点指针if (!full_child->is_leaf) {for (int i = mid + 1; i <= M; ++i) {new_node->children.push_back(full_child->children[i]);}full_child->children.resize(mid + 1);}// 将新节点插入到父节点的子节点列表parent->children.insert(parent->children.begin() + child_idx + 1, new_node);// 将中间键提升到父节点parent->keys.insert(parent->keys.begin() + child_idx, full_child->keys[mid]);}// 插入非满节点void insertNonFull(BTreeNode<T, M>* node, const T& key) {int i = node->keys.size() - 1;// 如果是叶子节点，直接插入键if (node->is_leaf) {node->keys.push_back(key);// 保持键的有序性while (i >= 0 && key < node->keys[i]) {node->keys[i + 1] = node->keys[i];--i;}node->keys[i + 1] = key;} else {// 找到插入的子节点位置while (i >= 0 && key < node->keys[i]) {--i;}int child_idx = i + 1;// 检查子节点是否已满if (node->children[child_idx]->keys.size() == M - 1) {splitChild(node, child_idx);  // 分裂子节点// 确定插入到分裂后的哪个子节点if (key > node->keys[child_idx]) {child_idx++;}}insertNonFull(node->children[child_idx], key);  // 递归插入}}public:// 构造函数BTree() {root = new BTreeNode<T, M>();}// 插入键值void insert(const T& key) {BTreeNode<T, M>* r = root;// 如果根节点已满，分裂根节点if (r->keys.size() == M - 1) {BTreeNode<T, M>* new_root = new BTreeNode<T, M>(false);root = new_root;new_root->children.push_back(r);  // 旧根成为新根的子节点splitChild(new_root, 0);          // 分裂旧根insertNonFull(new_root, key);     // 插入键到新根} else {insertNonFull(r, key);  // 直接插入到非满的根节点}}// 查找键值（返回是否存在）bool search(const T& key) {return searchHelper(root, key);}private:// 查找辅助函数bool searchHelper(BTreeNode<T, M>* node, const T& key) {int i = 0;// 找到第一个大于等于key的位置while (i < node->keys.size() && key > node->keys[i]) {++i;}// 如果找到匹配的键，返回trueif (i < node->keys.size() && key == node->keys[i]) {return true;}// 如果是叶子节点且未找到，返回falseif (node->is_leaf) {return false;}// 递归查找子节点return searchHelper(node->children[i], key);}
};

三、B + 树：数据库索引的黄金标准

3.1 结构增强与优化

B + 树在 B 树基础上进行了以下改进：

数据全在叶子节点：内部节点仅存储键值和子节点指针，不存储实际数据。
叶子节点链表：所有叶子节点通过双向链表连接，支持高效范围查询。
更高的扇出：内部节点键值数更多，树高更低（通常比 B 树矮 1-2 层）。

3.2 核心操作优化

插入操作（以 m=3 为例）

分裂策略：仅分裂叶子节点，中间键值提升至父节点，内部节点键值数可能超过m-1。
链表维护：分裂后更新相邻叶子节点的前后指针。

删除操作（以 m=3 为例）

合并策略：若叶子节点键值数不足，优先从兄弟节点借键；若兄弟节点也不足，则合并并更新父节点指针。
链表调整：合并后重新连接链表指针。

3.3 代码实现

#include <vector>
#include <algorithm>
#include <stdexcept>// B+树节点类模板
template <typename T, int M>  // M为B+树的阶数
class BPlusTreeNode {
public:std::vector<T> keys;                       // 存储键值std::vector<BPlusTreeNode<T, M>*> children; // 存储子节点指针BPlusTreeNode<T, M>* next;                 // 叶子节点的链表指针（用于范围查询）bool is_leaf;                              // 是否为叶子节点// 构造函数BPlusTreeNode(bool leaf = true) : is_leaf(leaf), next(nullptr) {}
};// B+树类模板
template <typename T, int M>
class BPlusTree {
private:BPlusTreeNode<T, M>* root;    // 根节点指针BPlusTreeNode<T, M>* leaf_head;  // 叶子节点链表头（便于范围查询）// 分裂子节点void splitChild(BPlusTreeNode<T, M>* parent, int child_idx) {BPlusTreeNode<T, M>* full_child = parent->children[child_idx];BPlusTreeNode<T, M>* new_node = new BPlusTreeNode<T, M>(full_child->is_leaf);int mid = (M - 1) / 2;  // B+树分裂点（保留中间键在原节点）// 复制中间键右侧的键到新节点for (int i = mid + 1; i < M; ++i) {new_node->keys.push_back(full_child->keys[i]);}full_child->keys.resize(mid + 1);  // 保留中间键// 如果是叶子节点，处理链表指针if (full_child->is_leaf) {new_node->next = full_child->next;full_child->next = new_node;} else {// 非叶子节点复制子节点指针for (int i = mid + 1; i <= M; ++i) {new_node->children.push_back(full_child->children[i]);}full_child->children.resize(mid + 1);}// 插入新节点到父节点parent->children.insert(parent->children.begin() + child_idx + 1, new_node);// 父节点插入分裂点的键（B+树父节点存储子节点的最小键）parent->keys.insert(parent->keys.begin() + child_idx, full_child->keys[mid]);}// 插入非满节点void insertNonFull(BPlusTreeNode<T, M>* node, const T& key) {int i = node->keys.size() - 1;// 叶子节点直接插入if (node->is_leaf) {node->keys.push_back(key);// 保持有序while (i >= 0 && key < node->keys[i]) {node->keys[i + 1] = node->keys[i];--i;}node->keys[i + 1] = key;} else {// 找到子节点位置while (i >= 0 && key < node->keys[i]) {--i;}int child_idx = i + 1;// 检查子节点是否已满if (node->children[child_idx]->keys.size() == M) {splitChild(node, child_idx);if (key > node->keys[child_idx]) {child_idx++;}}insertNonFull(node->children[child_idx], key);}}public:// 构造函数BPlusTree() {root = new BPlusTreeNode<T, M>();leaf_head = root;  // 初始叶子头为根节点}// 插入键值void insert(const T& key) {BPlusTreeNode<T, M>* r = root;// 根节点已满，分裂根节点if (r->keys.size() == M) {BPlusTreeNode<T, M>* new_root = new BPlusTreeNode<T, M>(false);root = new_root;new_root->children.push_back(r);splitChild(new_root, 0);insertNonFull(new_root, key);} else {insertNonFull(r, key);}// 更新叶子头（如果根节点分裂后叶子头变化）if (!root->is_leaf) {BPlusTreeNode<T, M>* temp = root;while (!temp->is_leaf) {temp = temp->children[0];}leaf_head = temp;}}// 范围查询：返回[start, end]之间的所有键std::vector<T> rangeQuery(const T& start, const T& end) {std::vector<T> result;BPlusTreeNode<T, M>* current = leaf_head;// 找到起始叶子节点while (current != nullptr) {auto it = std::lower_bound(current->keys.begin(), current->keys.end(), start);if (it != current->keys.end()) {break;}current = current->next;}// 遍历叶子节点链表收集结果while (current != nullptr) {for (const T& key : current->keys) {if (key > end) {return result;}if (key >= start) {result.push_back(key);}}current = current->next;}return result;}// 点查询：返回是否存在bool search(const T& key) {BPlusTreeNode<T, M>* current = root;while (current != nullptr) {int i = 0;while (i < current->keys.size() && key > current->keys[i]) {++i;}// 叶子节点检查是否存在if (current->is_leaf) {return (i < current->keys.size() && current->keys[i] == key);}// 非叶子节点继续向下查找current = current->children[i];}return false;}
};

四、B 树与 B + 树深度对比

特性	B 树	B + 树
数据存储	所有节点均可存储数据	仅叶子节点存储数据
树高	较高（相同数据量下比 B + 树高 1-2 层）	较低（内部节点键值更多）
查询效率	点查询可能更快（非叶子节点命中）	点查询稳定（必须到叶子节点）
范围查询	需中序遍历，随机 I/O 多	顺序遍历链表，顺序 I/O 高效
磁盘利用率	内部节点存储数据，空间利用率低	内部节点紧凑，空间利用率高
应用场景	内存数据库、小规模索引	关系型数据库、文件系统