Appearance
B-树与 B+树（B-Tree / B+ Tree）
B-树（多路平衡查找树）通过让每个节点存放多个关键字，显著降低树高，减少磁盘 I/O 次数，适合大规模数据的外存索引。 B+树是 B-树的变体：内部节点只存关键字不存数据，所有数据保存在叶子节点，叶子节点之间用链表相连，支持高效的顺序扫描。
B-树（B-Tree）
m 阶 B-树的性质：
- 每个节点最多含 m-1 个关键字；
- 非根非叶节点至少含 ⌈m/2⌉-1 个关键字；
- 所有叶节点在同一层（树高均衡）；
- 每个节点中关键字升序排列，n 个关键字对应 n+1 个子节点指针。
查找过程模拟
以 3 阶 B-树（每节点最多 2 个关键字）查找 target = 15 为例：
B+树（B+ Tree）
B+树与 B-树的主要区别：
- 内部节点：只存关键字（不含数据记录），起路由作用，单节点可容纳更多关键字，树更矮。
- 叶子节点：存放全部关键字及对应数据记录（或指针），叶子节点之间通过链表串联，支持顺序扫描。
- 查找：任何查找都必须到达叶子节点（查找路径等长），性能更稳定。
B-树与 B+树对比
| 特性 | B-树 | B+树 |
|---|---|---|
| 数据存放位置 | 内部节点和叶子节点均有 | 仅叶子节点 |
| 查找路径长度 | 可能在内部节点命中 | 总到叶子节点（等长） |
| 顺序扫描 | 需中序遍历 | 叶子链表直接遍历 |
| 单节点关键字数 | 较少（含数据记录） | 较多（只存关键字） |
| 典型应用 | 文件系统目录 | 数据库索引（MySQL InnoDB） |
算法特性
- 时间复杂度：O(log_m n)，m 为阶数；树高远低于 BST，磁盘 I/O 次数等于树高。
- 空间利用率：每个节点至少半满（⌈m/2⌉-1 个关键字），空间利用率高。
- 适合外存：每次 I/O 读取一整个节点（对应磁盘块），m 越大树越矮，I/O 越少。
Baseline 任务：B-树与 B+树实现
任务内容
完成 b_tree_b_plus_tree.cpp，实现以下功能：
- B-树
- 支持关键字查找、插入和遍历
- 使用多关键字节点降低树高，插入时处理节点分裂
- B+树
- 支持关键字查找、插入和叶子链遍历
- 全部有效关键字保存在叶子节点，维护叶子节点间的顺序链表
文件结构
b_tree_b_plus_tree.h：接口声明b_tree_b_plus_tree.cpp：核心实现test.cpp：测试程序
验证方式
- 编译：
g++ -std=c++17 test.cpp b_tree_b_plus_tree.cpp -o testBTreeBPlusTree - 运行：
./testBTreeBPlusTree