B 树与 B + 树解析与实现

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

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

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

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

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

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

2.1 核心结构与规则

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

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

示例结构（m=3）

2.2 关键操作详解

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

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

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

1. 查找删除位置：定位到包含目标键值的节点。
2. 处理节点不足：
   • 若删除后节点键值数 <⌈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;
        }

        // 如果找到匹配的键，返回true
        if (i < node->keys.size() && key == node->keys[i]) {
            return true;
        }

        // 如果是叶子节点且未找到，返回false
        if (node->is_leaf) {
            return false;
        }

        // 递归查找子节点
        return searchHelper(node->children[i], key);
    }
};

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

3.1 结构增强与优化

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

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

3.2 核心操作优化

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

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

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

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

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 + 树深度对比

五、典型应用场景与优化策略

5.1 数据库索引设计

聚簇索引（Clustered Index）

• 实现：B + 树叶子节点存储完整数据行（如 InnoDB 主键索引）。
• 优势：范围查询性能极高（顺序扫描链表）。
• 优化：
  • 选择短主键（如自增整数），减少叶子节点大小。
  • 预分配连续页空间，减少页分裂。

非聚簇索引（Secondary Index）

• 实现：B + 树叶子节点存储主键值，需回表查询完整数据。
• 优化：
  • 使用覆盖索引（Covering Index），将常用字段包含在索引中。
  • 避免 SELECT *，减少回表次数。

5.2 文件系统目录管理

• 场景：NTFS、Ext4 等文件系统使用 B + 树管理目录结构。
• 优势：
  • 快速定位文件路径（逐层查找内部节点）。
  • 高效遍历目录下所有文件（叶子节点链表）。

5.3 内存缓存优化

• 策略：
  • 将 B + 树非叶子节点常驻内存，减少磁盘 I/O。
  • 利用 LRU 算法缓存高频访问的叶子节点。

六、性能对比与选型建议

6.1 性能测试数据（百万级数据）

6.2 选型指南

• 选 B 树：
  • 数据量小（<10 万条）。
  • 点查询占比极高，且内存足够容纳索引。
• 选 B + 树：
  • 数据量大（>10 万条）。
  • 范围查询、排序操作频繁。
  • 需要高效磁盘 I/O 性能。

七、可视化工具与学习资源

1. 动态演示工具：
   • B 树可视化
   • B + 树可视化
2. 教材推荐：
   • 《算法导论》第 18 章（B 树）
   • 《数据库系统概念》第 11 章（索引结构）
3. 实战案例：
   • MySQL InnoDB B + 树索引深度解析
   • Linux Ext4 文件系统 B + 树实现

八、总结

B 树与 B + 树是为磁盘存储优化而生的核心数据结构：

• B 树适合内存有限、点查询密集的场景，通过平衡多路搜索实现高效随机访问。
• B + 树通过叶子节点链表和更高扇出，成为数据库索引和文件系统的黄金标准，尤其擅长范围查询和顺序访问。