一、B 树插入概述
B 树允许一个节点拥有多个 key，这使得它相比二叉树更“矮胖”，在插入数据时效率更高。
插入时的核心问题是：
如何在节点满了之后分裂并保持 B 树性质？
二、节点分裂时机与两种方式
B 树插入中，当目标节点满了（即 key 个数 == 2t - 1）时，必须执行分裂操作。
🔧 插入有两种分裂方式：
| 插入模式 | 描述 | 优势 | 适用场景 |
| ⛏️ 自顶向下（Top-Down） | 在插入过程中就提前分裂满的子节点 | 避免递归回溯，逻辑清晰 | 工程中更常用 |
| 🧹 自底向上（Bottom-Up） | 插入到底再回溯并处理分裂 | 实现简单直观 | 教学场景常用 |
三、自顶向下插入（Top-Down）：核心流程
- 从根节点开始往下寻找插入位置
- 如果发现某个子节点已满，在继续之前就先把它分裂
- 将中间 key 提升到父节点中，分裂为两个子节点
- 插入继续向下，直到叶子
📐 示例：
插入 12 到如下 B 树中（2 阶）：
[10]/ \[5 7 8] [15 20 25]插入前，[5 7 8] 已满 ⇒ 分裂成 [5], [8]，中间值 7 上提到根：
[7 10]/ | \[5] [8] [15 20 25]插入 12 落到 [15 20 25] 前，正常插入变成 [12 15 20 25]
四、完整代码实现：B 树节点 + 插入（自顶向下）
我们实现一个最小度数为 t=2 的 B 树（最多 3 个 key）：
✅ BTreeNode.h
#ifndef BTREE_NODE_H
#define BTREE_NODE_H#include <iostream>
#include <vector>class BTreeNode {public:int t; // 最小度数bool isLeaf; // 是否为叶子节点std::vector<int> keys; // 关键字std::vector<BTreeNode*> children; // 子节点BTreeNode(int t, bool isLeaf);void traverse(); // 中序遍历BTreeNode* search(int k); // 查找 keyvoid insertNonFull(int k); // 插入非满节点void splitChild(int i, BTreeNode* y); // 分裂子节点friend class BTree;};#endif✅ BTreeNode.cpp
#include "BTreeNode.h"BTreeNode::BTreeNode(int t, bool isLeaf) {this->t = t;this->isLeaf = isLeaf;
}void BTreeNode::traverse() {int i;for (i = 0; i < keys.size(); ++i) {if (!isLeaf) children[i]->traverse();std::cout << keys[i] << " ";}if (!isLeaf)children[i]->traverse();
}BTreeNode* BTreeNode::search(int k) {int i = 0;while (i < keys.size() && k > keys[i])++i;if (i < keys.size() && keys[i] == k)return this;if (isLeaf)return nullptr;return children[i]->search(k);
}void BTreeNode::insertNonFull(int k) {int i = keys.size() - 1;if (isLeaf) {keys.resize(keys.size() + 1);while (i >= 0 && keys[i] > k) {keys[i + 1] = keys[i];--i;}keys[i + 1] = k;} else {while (i >= 0 && keys[i] > k)--i;if (children[i + 1]->keys.size() == 2 * t - 1) {splitChild(i + 1, children[i + 1]);if (k > keys[i + 1])++i;}children[i + 1]->insertNonFull(k);}
}void BTreeNode::splitChild(int i, BTreeNode* y) {BTreeNode* z = new BTreeNode(y->t, y->isLeaf);z->keys.resize(t - 1);for (int j = 0; j < t - 1; ++j)z->keys[j] = y->keys[j + t];if (!y->isLeaf) {z->children.resize(t);for (int j = 0; j < t; ++j)z->children[j] = y->children[j + t];}y->keys.resize(t - 1);children.insert(children.begin() + i + 1, z);keys.insert(keys.begin() + i, y->keys[t - 1]);
}✅ BTree.h
#ifndef BTREE_H
#define BTREE_H#include "BTreeNode.h"class BTree {BTreeNode* root;int t;public:BTree(int t) {this->t = t;root = nullptr;}void traverse() {if (root != nullptr) root->traverse();}BTreeNode* search(int k) {return (root == nullptr) ? nullptr : root->search(k);}void insert(int k);
};#endif✅ BTree.cpp
#include "BTree.h"void BTree::insert(int k) {if (root == nullptr) {root = new BTreeNode(t, true);root->keys.push_back(k);} else {if (root->keys.size() == 2 * t - 1) {BTreeNode* s = new BTreeNode(t, false);s->children.push_back(root);s->splitChild(0, root);int i = 0;if (s->keys[0] < k)++i;s->children[i]->insertNonFull(k);root = s;} else {root->insertNonFull(k);}}
}✅ 测试 main.cpp
#include "BTree.h"int main() {BTree t(2); // 最小度数 t=2std::vector<int> values = {10, 20, 5, 6, 12, 30, 7, 17};for (int v : values)t.insert(v);std::cout << "中序遍历：";t.traverse();std::cout << std::endl;int key = 6;std::cout << "搜索 " << key << ": ";auto node = t.search(key);std::cout << (node ? "找到" : "未找到") << std::endl;
}五、图解：插入流程图
如果你需要插入流程图，我可以为你生成一个，帮助理解分裂和节点移动过程。
六、本节总结
| 项目 | 内容说明 |
| 插入触发时机 | 节点 key 达到 2t - 1 个 |
| 插入策略 | 自顶向下分裂（提前分裂孩子）避免递归回溯 |
| 分裂操作 | 中间 key 上移，新建右侧节点 |
| 工程使用策略 | 自顶向下插入为主，性能更优 |
| 下一步 | 删除逻辑更复杂，需要借位、合并、重构 |
