B 树与 B+ 树详解：原理、实现及 MySQL 索引应用

3. B 树的插入逻辑分析

假设 M = 3，即三叉树，每个节点中存储两个数据，三个子节点。B 树插入操作的核心逻辑是节点分裂，完整流程如下：

1. 触发条件：向节点插入新键值后，节点键值数达到 M（超过最大容量 M-1），分裂出一个兄弟节点；
2. 中间位置计算：取 mid = M / 2；
3. 分裂规则：
   • 原节点保留 [0, mid-1] 范围的键值，以及**[0, mid] 范围的子节点**；
   • 新建兄弟节点，将原节点**[mid+1, M-1] 范围的键值**、[mid+1, M] 的子节点移入；
   • 原节点的第 mid 个键值（中间键值）提升至父节点，作为父节点区分原节点与兄弟节点的分界键；兄弟节点作为父节点的新子节点，插入到中间键值的右侧；

上面三叉树之所以多创建一个键值和子节点，就是为了可以先插入再分裂，避免分裂后再插入的复杂逻辑。

用序列 {75，49，139，150，36，40，53，55，25，52，60} 构建 B 树的过程如下：

插入步骤演示

（1）依次插入 75、49、139 找到该元素应插入的位置，按照插入排序的思想将元素插入到合适位置。检查该节点是否满足 B 树的性质，满足则插入结束，不满足则对节点进行分裂。 此时该节点已满，触发分裂：找到节点的中间位置，给出一个新建点，将中间位置之后的数据搬到新节点，中间位置键值提升到父节点，将节点连接好。

B 树的插入严格遵循'先查找，后插入'的逻辑，从根节点开始，根据键值的有序关系向下遍历，直到确定插入位置。

（2）接着插入 150，36，40 触发分裂，这里父节点移动的逻辑是：新提升上来的键值 40，从序列末尾依次向前比较，当原键值较大时，原键值向后移动一个位置，同时右子节点也向右移动，新键值继续向前比较，直到比原键值大或到第一个位置，插入并且该插入位置的右子节点指向新分裂出发节点。

void InsertKey(Node* node, const K& key, Node* child) { 
    // 从后往前，依次判断应插入位置 
    int end = node->_n - 1; 
    while (end >= 0 && key < node->_keys[end]) { 
        node->_keys[end + 1] = node->_keys[end]; 
        node->_subs[end + 2] = node->_subs[end + 1]; 
        --end; 
    } 
    node->_keys[end + 1] = key; 
    node->_subs[end + 2] = child; 
    if (child) child->_parent = node; 
    node->_n++; 
}

（3）插入 53，55 叶子节点分裂得到结果，此时的根节点继续分裂。

（4）插入 25，52，60

插入过程总结

1. 如果树为空，直接插入新节点中，该节点为树的根节点
2. 树非空，找待插入元素在树中的插入位置（注意：找到的插入节点位置一定在叶子节点中）
3. 检测是否找到插入位置（假设树中的 key 唯一，即该元素已经存在时则不插入）
4. 按照插入排序的思想将该元素插入到找到的节点中
5. 检测该节点是否满足 B 树的性质：即该节点中的元素个数是否等于 M，如果小于则满足
6. 如果插入后节点不满足 B 树的性质，需要对该节点进行分裂：
   • 申请新节点
   • 找到该节点的中间位置
   • 将该节点中间位置右侧的元素以及其孩子搬移到新节点中
   • 将中间位置元素以及新节点往该节点的父节点中插入，将父节点作为新的插入节点，判断是否满足 B 树性质，重复过程 6、7。
7. 如果向上已经分裂到根节点的位置，插入结束。

节点设计与性能分析

template<class K, size_t M> struct BTreeNode { 
    // 为了方便先插入再分裂，多给一个空间 
    K _keys[M]; 
    BTreeNode<K, M>* _subs[M+1]; 
    BTreeNode<K, M>* _parent; 
    size_t _n; // 记录有多少个关键字 
    BTreeNode() :_parent(nullptr), _n(0) { 
        for (int i = 0; i < M - 1; ++i) { 
            _keys[i] = K(); 
            _subs[i] = nullptr; 
        } 
        _subs[M - 1] = nullptr; 
    } 
};

B 树性能分析： 对于度为 M 的 B 树，因每个节点的子节点数介于⌈M/2⌉（即 M/2 向上取整）和 M 之间，树的高度范围为 log_M N ~ log_{⌈M/2⌉} N，对应查找 / 插入操作的节点定位比较次数为 log_{M-1} N ~ log_{M/2} N（节点内键值数为子节点数 - 1）；定位到目标节点后，可通过二分查找快速找到元素。B 树效率极高：以 620 亿个节点（N=62×10⁹）、度 M=1024 为例，log_{M/2} N ≤ 4，即仅需不到 4 次节点定位即可找到目标节点，大幅减少磁盘 IO 次数（磁盘 IO 的核心开销在于节点加载，而非节点内二分）。

4. B 树删除逻辑简介

删除的核心规则：节点键值数低于最小值时，要么向兄弟节点'借键'，要么与兄弟节点合并。节点空则合并 / 借键。

流程：

1. 找到要删除的键值，若为非叶子节点：用'后继键值'（右子树最小键值）替换该键值，转为删除后继键值（保证只删叶子节点）；
2. 从叶子节点删除键值后，检查节点键值数：
   • 若≥最小值：删除完成；
   • 若 < 最小值：
     • 尝试向相邻节点'借键'：父节点的一个键值下移，兄弟节点的一个键值上移（保持有序）；
     • 若兄弟节点也无键可借：与兄弟节点合并（父节点的一个键值下沉到合并节点）；
3. 若父节点合并后键值数不足，重复上述流程（直到根节点）；
4. 若根节点合并后无键值，删除根节点（树高 - 1）。

5. B+ 树简介

5.1. B+ 树性质

B + 树是 B 树的变形，是在 B 树基础上优化的多路平衡搜索树，B + 树的规则跟 B 树基本类似，但是又在 B 树的基础上做了以下几点改进优化：

1. 分支节点的子树指针与关键字个数相同（相当于取消了 B 树最左边那个子树）。
2. 分支节点的子树指针 p[i] 指向关键字值大小在 [k[i], k[i+1]) 区间之间
3. 所有叶子节点增加一个链接指针链接在一起
4. 非叶子节点只存索引 key，不存数据；所有关键字及其映射的数据都存在叶子节点（聚簇索引叶子存整行数据，二级索引叶子存主键值）。
5. 分支节点跟叶子节点有重复的值，分支节点存的是叶子节点索引中的最小值。
6. 所有关键字都出现在叶子节点中，且链表中的节点是有序的。

5.2. B+ 树的分裂

当一个结点满时，分配一个新的结点，并将原结点中 1/2 的数据复制到新结点，中间关键字往上提，最后在父结点中增加新结点的指针。

B树的分裂：当一个结点满时，如果它的下一个兄弟结点未满，那么将一部分数据移到兄弟结点中，再在原结点插入关键字，最后修改父结点中兄弟结点的关键字（因为兄弟结点的关键字范围改变了）；如果兄弟也满了，则在原结点与兄弟结点之间增加新结点，并各复制 1/3 的数据到新结点，最后在父结点增加新结点的指针。所以，B树分配新结点的概率比 B+ 树要低，空间使用率更高。

通过以上介绍，大致将 B 树，B+ 树，B*树总结如下：

• B 树：有序数组 + 平衡多叉树；
• B+ 树：有序数组链表 + 平衡多叉树；
• B*树：一棵更丰满的，空间利用率更高的 B+ 树。

6. B 树的应用

6.1. MySQL 索引简介

B 树最常见的应用就是用来做索引。MySQL 官方对索引的定义为：索引（index）是帮助 MySQL 高效获取数据的数据结构。

当数据量很大时，为了能够方便管理数据，提高数据查询的效率，一般都会选择将数据保存到数据库，因此数据库不仅仅是帮助用户管理数据，而且数据库系统还维护着满足特定查找算法的数据结构，这些数据结构以某种方式引用数据，这样就可以在这些数据结构上实现高级查找算法，该数据结构就是索引。

MySQL 是一个非常流行的开源关系型数据库，不仅是免费的，可靠性高，速度也比较快，而且拥有灵活的插件式存储引擎。

MySQL 中索引属于存储引擎级别的概念，不同存储引擎对索引的实现方式是不同的。注意：索引是基于表的，而不是基于数据库的。

6.2. MyISAM

MyISAM 引擎是 MySQL5.5.8 版本之前默认的存储引擎，不支持事物，支持全文检索，使用 B+ 树作为索引结构，叶节点的 data 域存放的是数据记录的地址，其结构如下：

在 MyISAM 中，主索引和辅助索引在结构上没有任何区别，只是主索引要求 key 是唯一的，而辅助索引的 key 可以重复。

6.3. InnoDB

InnoDB 存储引擎支持事务，其设计目标主要面向在线事务处理的应用，从 MySQL 数据库 5.5.8 版本开始，InnoDB 存储引擎是默认的存储引擎。InnoDB 支持 B+ 树索引、全文索引、哈希索引。但 InnoDB 使用 B+ 树作为索引结构时，具体实现方式却与 MyISAM 截然不同：

1. InnoDB 的数据文件本身就是索引文件。MyISAM 索引文件和数据文件是分离的，索引文件仅保存数据记录的地址。而 InnoDB 索引，表数据文件本身就是按 B+ 树组织的一个索引结构，这棵树的叶节点 data 域保存了完整的数据记录。这个索引的 key 是数据表的主键，因此 InnoDB 表数据文件本身就是主索引。

上图是 InnoDB 主索引（同时也是数据文件）的示意图，可以看到叶节点包含了完整的数据记录，这种索引叫做聚簇索引。因为 InnoDB 的数据文件本身要按主键聚集，所以 InnoDB 要求表必须有主键（MyISAM 可以没有），如果没有，则选择一个唯一非空索引，如果还没有，则使用自增 ID（一个隐藏字段）作为聚簇索引。

2. InnoDB 的辅助索引 data 域存储相应记录主键的值而不是地址，所有辅助索引都引用主键作为 data 域。

聚簇索引这种实现方式使得按主键的搜索十分高效，但是辅助索引搜索可能需要检索两遍索引：首先检索辅助索引获得主键，如果使用辅助索引需要获得除主键外的其它字段值，则需要回表（使用主键值作为聚簇索引重新检索）。

7. B 树插入代码实现

以下是 C++ 实现的 B 树插入相关核心代码，包括查找、插入键值、整体插入逻辑以及中序遍历。

// 找到应插入位置
pair<Node*, int> Find(const K& key) {
    Node* cur = _root, *parent = nullptr;
    while (cur) {
        int i = 0;
        while (i < cur->_n) {
            if (key < cur->_keys[i]) break;
            else if (key == cur->_keys[i]) return make_pair(cur, i);
            else ++i;
        }
        parent = cur;
        cur = cur->_subs[i];
    }
    return make_pair(parent, -1);
}

// 插入键值
void InsertKey(Node* node, const K& key, Node* child) {
    // 从后往前，依次判断应插入位置
    int end = node->_n - 1;
    while (end >= 0 && key < node->_keys[end]) {
        node->_keys[end + 1] = node->_keys[end];
        node->_subs[end + 2] = node->_subs[end + 1];
        --end;
    }
    node->_keys[end + 1] = key;
    node->_subs[end + 2] = child;
    if (child) child->_parent = node;
    node->_n++;
}

// 插入主逻辑
bool Insert(const K& key) {
    if (_root == nullptr) {
        _root = new Node;
        _root->_keys[0] = key;
        _root->_n++;
        return true;
    }
    // 判断 key 是否已存在
    pair<Node*, int> ret = Find(key);
    if (ret.second >= 0) return false; // key 不存在，find 带回来要插入的那个节点

    // 循环每次往 parent 插入 newkey 和 child
    Node* parent = ret.first;
    Node* child = nullptr;
    K newKey = key;
    while (1) {
        InsertKey(parent, newKey, child);
        // 没有满，插入就结束了
        if (parent->_n < M) {
            return true;
        }
        // 满了就要分裂出兄弟节点，并将中间值插入父节点
        else {
            size_t mid = M / 2;
            Node* brother = new Node;
            size_t j = 0;
            size_t i = mid + 1;
            for (; i < M; ++i) {
                // 拷贝键值和左孩子到兄弟节点
                brother->_keys[j] = parent->_keys[i];
                brother->_subs[j] = parent->_subs[i];
                if (parent->_subs[i]) parent->_subs[i]->_parent = brother;
                ++j;
                // 清除原节点
                parent->_keys[i] = K();
                parent->_subs[i] = nullptr;
            }
            // 还有最后一个右孩子
            brother->_subs[j] = parent->_subs[i];
            if (parent->_subs[i]) parent->_subs[i]->_parent = brother;
            parent->_subs[i] = nullptr;
            brother->_n = j;
            parent->_n -= j + 1;
            K midKey = parent->_keys[mid];
            parent->_keys[mid] = K();
            if (parent->_parent == nullptr) // 说明刚才分裂的是根节点
            {
                _root = new Node;
                _root->_keys[0] = midKey;
                _root->_subs[0] = parent;
                _root->_subs[1] = brother;
                _root->_n = 1;
                parent->_parent = _root;
                brother->_parent = _root;
                break;
            }
            else {
                newKey = midKey;
                child = brother;
                parent = parent->_parent;
            }
        }
    }
    return true;
}

// 中序遍历
void _InOrder(Node* cur) {
    if (cur == nullptr) return;
    // 左子 根 左子 根 ... 右
    size_t i = 0;
    for (; i < cur->_n; ++i) {
        _InOrder(cur->_subs[i]);
        cout << cur->_keys[i] << " ";
    }
    // 最后的右子树
    _InOrder(cur->_subs[i]);
}