在数据库索引和文件系统中，B树与B+树是使用最广泛的多路平衡搜索树结构。和二叉搜索树每次只比较一个键不同，B树的一个节点可以容纳多个键值和多个子指针，这样可以显著降低树的高度，减少磁盘IO次数。本文先解释它们背后的存储原理，再用C++给出核心数据结构和插入、查找、范围查询的实现重点。

一、B树与B+树在数据库索引中的定位

数据库查询的时间大头通常不在内存比较，而在磁盘IO。磁盘读取以页为单位，一次IO会读出一个固定大小的数据块。如果使用二叉搜索树，即便完全平衡，树高也可能达到二十层以上，随机查找一条记录可能需要二十次以上的磁盘定位，性能很难接受。B树和B+树通过让一个节点持有多个键和多个子节点，把树高压缩到三层或四层，一次查找只需要三五次磁盘IO，这是它们成为索引默认结构的根本原因。

以常见的4KB磁盘页为例，假设一个键值对加指针占用约32字节，那么一个节点可以放大约128个键。一个四层的B+树，在叶子节点之前的三层全部用于路由，理论上可以索引128的3次方乘以叶子容量，达到千万级甚至亿级记录。这个数量级的覆盖能力，使得数据库即便存储上亿行数据，主键查询依然可以保持毫秒级响应。

B树允许内部节点也存储数据，因此查询可能在内节点提前命中。B+树则把数据全部放在叶子节点，内部节点只保存键和子指针，单个内节点能放更多路由键，树高进一步降低。同时B+树的所有叶子节点通过链表顺序串联，范围查询时只要先定位到起始叶子，再顺序遍历链表即可，不需要像B树那样反复回溯父节点。这一特性让B+树在关系型数据库中成为主流选择，比如MySQL的InnoDB引擎、PostgreSQL的B-Tree索引，本质上都是B+树的变体。

二、B树的C++实现重点：节点结构与分裂插入

一个m阶B树需要满足几个基本约束：每个节点最多有m-1个键，最多m个子节点；除根节点和叶子节点外，每个节点至少有ceil(m/2)-1个键；所有叶子节点位于同一层。以m等于5为例，节点最多存4个键、最多5个子节点，最少存2个键。实现时通常把键数组容量设为m，子节点指针数组容量设为m+1，有效键数用单独变量记录。

下面给出一个固定阶数为5、键类型为int的B树节点定义，侧重展示数组和子指针的关系。实际项目中可以使用模板把键类型和阶数参数化，但核心逻辑完全一致。

#include <iostream>
const int M = 5; // 5阶B树，最大5个子节点
struct BTreeNode {
    bool isLeaf;
    int n;                  // 当前有效键数量
    int keys[M];            // 最多M-1个有效键，这里留M个方便操作
    BTreeNode* children[M + 1];
    BTreeNode(bool leaf = true) : isLeaf(leaf), n(0) {
        for (int i = 0; i < M + 1; ++i) {
            children[i] = nullptr;
        }
    }
};

插入操作比二叉搜索树复杂，原因在于节点键数超过上限时需要分裂。做法是：从根开始递归查找合适子节点，如果待插入的节点未满则直接插入；如果已满，先分裂再把中间键上提到父节点。分裂时以中间键为界，左半部分留在原节点，右半部分移入新节点，中间键插入父节点。如果父节点也满了，就继续向上分裂，直到根节点分裂产生新的根，树高增加一层。

下面是分裂和插入的核心代码，包含了查找插入位置、搬运右侧键、挂接新子节点等步骤。

class BTree {
private:
    BTreeNode* root;
    // 将parent的第idx个子节点分裂
    void splitChild(BTreeNode* parent, int idx) {
        BTreeNode* child = parent->children[idx];
        BTreeNode* newChild = new BTreeNode(child->isLeaf);
        int mid = (M - 1) / 2;          // 中间键位置，M=5时mid=2
        // 右侧键数量：总共n个键，mid右侧有n-mid-1个
        newChild->n = child->n - mid - 1;
        // 拷贝右侧键
        for (int i = 0; i < newChild->n; ++i) {
            newChild->keys[i] = child->keys[mid + 1 + i];
        }
        // 如果不是叶子，拷贝右侧子指针
        if (!child->isLeaf) {
            for (int i = 0; i <= newChild->n; ++i) {
                newChild->children[i] = child->children[mid + 1 + i];
            }
        }
        child->n = mid; // 原节点只保留左侧键
        // 父节点腾出位置
        for (int i = parent->n; i > idx; --i) {
            parent->keys[i] = parent->keys[i - 1];
            parent->children[i + 1] = parent->children[i];
        }
        parent->keys[idx] = child->keys[mid];
        parent->children[idx + 1] = newChild;
        parent->n++;
    }
    // 插入到未满节点
    void insertNonFull(BTreeNode* node, int key) {
        int i = node->n - 1;
        if (node->isLeaf) {
            while (i >= 0 && node->keys[i] > key) {
                node->keys[i + 1] = node->keys[i];
                --i;
            }
            node->keys[i + 1] = key;
            node->n++;
        } else {
            while (i >= 0 && node->keys[i] > key) {
                --i;
            }
            ++i;
            if (node->children[i]->n == M - 1) {
                splitChild(node, i);
                if (node->keys[i] < key) {
                    ++i;
                }
            }
            insertNonFull(node->children[i], key);
        }
    }
public:
    BTree() : root(nullptr) {}
    void insert(int key) {
        if (root == nullptr) {
            root = new BTreeNode(true);
            root->keys[0] = key;
            root->n = 1;
            return;
        }
        if (root->n == M - 1) {
            BTreeNode* newRoot = new BTreeNode(false);
            newRoot->children[0] = root;
            splitChild(newRoot, 0);
            root = newRoot;
            insertNonFull(root, key);
            return;
        }
        insertNonFull(root, key);
    }
};

这段代码展示的是B树插入的完整闭环：根节点满时先分裂生成新根，再调用insertNonFull向下递归。注意每次分裂都会把中间键上提到父节点，因此父节点的键数组和子指针数组要同步后移，保证键与子指针的对应关系不被打乱。查找则相对简单，按照节点内的键顺序决定进入哪个子节点，直到命中断言或到达叶子返回空指针。

三、B+树的C++实现重点：叶子链表与范围查询

B+树与B树最大的不同在于数据只存储在叶子节点，内部节点只保存路由键。这样内部节点可以容纳更多索引项，降低树高；同时叶子节点之间通过链表连接，构成一个有序的数据序列。进行范围查询时，先定位到起始键所在的叶子节点，然后沿链表依次读取，直到超出上界，整个过程不需要回溯父节点。

为了演示方便，这里同样使用固定阶数M和int键类型。叶子节点存储键和对应的值，同时保存指向下一叶节点的指针。内部节点只存储键和子节点指针。一个通用的节点结构可以同时承载这两种角色，通过isLeaf标志区分。

#include <iostream>
const int M = 5;
struct BPlusNode {
    bool isLeaf;
    int n;
    int keys[M];              // 键数组
    BPlusNode* children[M + 1]; // 内部节点使用
    int values[M];            // 叶子节点使用
    BPlusNode* next;          // 叶子链表指针
    BPlusNode(bool leaf = true) : isLeaf(leaf), n(0), next(nullptr) {
        for (int i = 0; i < M + 1; ++i) {
            children[i] = nullptr;
        }
    }
};

B+树的插入分裂比B树多一步：叶子节点分裂后，新叶子要挂到链表上，同时把新叶子的第一个键（而不是中间键）上传到父节点作为分界键。这样父节点中的键仍然只用于路由，叶子节点才持有完整数据。内部节点分裂则和B树类似，只是不涉及数据搬运。

范围查询的代码可以这样实现：

void rangeQuery(BPlusNode* root, int low, int high) {
    if (root == nullptr) return;
    // 先走到包含low的叶子节点
    BPlusNode* cur = root;
    while (!cur->isLeaf) {
        int i = 0;
        while (i < cur->n && cur->keys[i] <= low) {
            ++i;
        }
        cur = cur->children[i];
    }
    // 沿叶子链表顺序扫描
    while (cur != nullptr) {
        for (int i = 0; i < cur->n; ++i) {
            int key = cur->keys[i];
            if (key > high) return;
            if (key >= low) {
                std::cout << key << " : " << cur->values[i] << std::endl;
            }
        }
        cur = cur->next;
    }
}

这段代码先根据内部节点的键比较找到起始叶子，然后利用next指针顺序遍历，读到超出high的键立即终止。由于叶子节点按键有序排列，范围查询的时间复杂度为O(log N + K)，其中K是返回的记录数。这正是B+树在数据库索引中占有绝对优势的原因之一。

四、B树与B+树的对比与索引选择

从存储位置看，B树的数据可以出现在任意层次的节点上，因此单点查询可能在内节点提前结束，最坏才到叶子。B+树则必须走到叶子节点，看起来多了一层，但由于内节点只存键，单页存放的路由信息更多，整体树高更低，平均IO次数反而更少。以4KB页、键长度为8字节、指针长度为8字节计算，B+树内节点大约可以放250个键和251个子指针，而B树叶节点中还要存数据，阶数通常小得多。

删除操作上，B树的删除可能因为节点键数低于最小限制而触发借键或合并，逻辑比插入还要复杂。B+树由于内部节点不存数据，删除时只需维护好叶子链表和路由键，当叶子节点下溢时向兄弟借键或合并，内部节点只需要更新键值，不需要搬运数据。因此B+树的删除实现相对清晰，也更容易保证并发场景下的一致性。

在数据库索引的具体选型上，MySQL的InnoDB引擎在聚簇索引中把主键记录直接存放在叶子节点，二级索引叶子节点存放主键值和索引键；PostgreSQL的B-Tree索引同样采用B+树变体，叶子节点通过双向链表连接。这些选择都充分利用了B+树范围查询快、树高稳定、删除维护简单的优点。而B树更多出现在文件系统的目录索引中，例如NTFS的主文件表MFT使用B树变体来管理目录项，因为这类场景更看重单点定位和结构稳定性。

理解B树与B+树的实现差异后，再去阅读数据库引擎源码会轻松很多。C++实现时不必追求一个通用到极致的模板类，先固定一个阶数把插入、分裂、查找和范围查询跑通，然后逐步泛化键类型和比较器，就能得到工程可用的索引结构。