数据结构：B-树
一、常见的搜索结构
以上结构适合用于数据量相对不是很大，能够一次性存放在内存中，进行数据查找的场景。如果数据量很大，比如有 100G 数据，无法一次放进内存中，那就只能放在磁盘上了。如果放在磁盘上，有需要搜索某些数据，那么如何处理呢？我们可以考虑将存放关键字及其映射的数据的地址放到一个内存中的搜索树的节点中，那么要访问数据时，先取这个地址去磁盘访问数据。
使用平衡二叉树搜索树的缺陷：
平衡二叉树搜索树的高度是 logN，这个查找次数在内存中是很快的。但是当数据都在磁盘中时，访问磁盘速度很慢，在数据量很大时，logN 次的磁盘访问，是一个难以接受的结果。
使用哈希表的缺陷：
哈希表的效率很高是 O(1)，但是一些极端场景下某个位置冲突很多，导致访问次数剧增，也是难以接受的。
那如何加速对数据的访问呢？
- 提高 IO 的速度（SSD 相比传统机械硬盘快了不少，但是还是没有得到本质性的提升）
- 降低树的高度---多叉树平衡树
二、B-树概念
1970 年，R.Bayer 和 E.Mccreight 提出了一种适合外查找的树，它是一种平衡的多叉树，称为 B 树（后面有一个 B 的改进版本 B+ 树，有些地方的 B 树写的是 B-树，注意不要误读成'B 减树'）。一棵 m 阶 (m>2) 的 B 树，是一棵平衡的 M 路平衡搜索树，可以是空树或者满足以下性质：
- 根节点至少有两个孩子
- 每个分支节点都包含 k-1 个关键字和 k 个孩子，其中 ceil(m/2) ≤ k ≤ m（ceil 是向上取整函数）
- 每个叶子节点都包含 k-1 个关键字，其中 ceil(m/2) ≤ k ≤ m
- 所有的叶子节点都在同一层
- 每个节点中的关键字从小到大排列，节点当中 k-1 个元素正好是 k 个孩子包含的元素的值域划分
- 每个结点的结构为：（n，A0，K1，A1，K2，A2，… ，Kn，An），其中，Ki(1≤i≤n) 为关键字，且 Ki<Ki+1(1<=i<=n-1)。Ai(0≤i≤n) 为指向子树根结点的指针。且 Ai 所指子树所有结点中的关键字均小于 Ki+1，n 为结点中关键字的个数，满足 ceil(m/2)-1≤n≤m-1
三、B-树的插入分析及实现
1. 插入分析
为了简单起见，假设 M = 3，即三叉树，每个节点中存储两个数据，两个数据可以将区间分割成三个部分，因此节点应该有三个孩子。为了后续实现简单期间，节点的结构如下：
注意：孩子永远比数据多一个
用序列 {53, 139, 75, 49, 145, 36, 101} 构建 B 树的过程如下：
插入总结:
- 如果树为空，直接插入新节点中，该节点为树的根节点
- 树非空，找待插入元素在树中的插入位置（注意：找到的插入节点位置一定在叶子节点中）
- 检测是否找到插入位置（假设树中的 key 唯一，即该元素已经存在时则不插入）
- 按照插入排序的思想将该元素插入到找到的节点中
- 检测该节点是否满足 B-树的性质：即该节点中的元素个数是否等于 M，如果小于则满足
- 如果插入后节点不满足 B 树的性质，需要对该节点进行分裂：
- 申请新节点
- 找到该节点的中间位置
- 将该节点中间位置右侧的元素以及其孩子搬移到新节点中
- 将中间位置元素以及新节点往该节点的双亲节点中插入，即继续步骤 4
- 如果向上已经分裂到根节点的位置，插入结束
pair<Node*, int> Find(const K& key) {
Node* parent = nullptr;
Node* cur = _root;
while (cur) {
i = ;
(i < cur->_n) {
(key < cur->_keys[i]) {
;
} (key > cur->_keys[i]) {
++i;
} {
(cur, i);
}
}
parent = cur;
cur = cur->_subs[i];
}
(parent, );
}
