🌈前言🌈
本文将讲解B树系列，包含 B-树，B+树，B*树，其中主要讲解B树底层原理，为什么用B树作为外查询的数据结构，以及B-树插入操作并用代码实现；介绍B+树、B*树。
📁常见的搜索结构
| 种类 | 数据格式 | 时间复杂度 |
| 顺序查找 | 无要求 | O(N) |
| 二分查找 | 有序 | O(logN) |
| 二叉搜索树 | 无要求 | O(N) |
| 二叉平衡树 | 无要求 | O(logN) |
| 哈希 | 无要求 | O(1) |
以上数据结构适用于数据量不大的情况下，能够一次性存放在内存中，进行数据查找的场景。
对内存进行访问是很快的，纳秒级别（10^-9）。但是同样时间内，访问磁盘的时间是很慢的，毫秒级别（10^-3）。
从表格可以看出，高效的查找结构是二叉平衡树和哈希表，但是他们都有一定的缺点。
对于二叉平衡树，时间复杂度还是很高，例如10亿的数据可能需要30次磁盘访问，这是难以接受的结果。
哈希表时间复杂度很低，但是哈希存在哈希冲突的问题，在某些极端场景下，某个位置冲突很多，导致访问次数剧增，也难以接受。
因此，就有了B-树系列，通过压缩树的高度，来减少磁盘访问次数，提高对数据的访问速度。
📁 B树
📂概念
1970年，R.Bayer和E.mccreight提出了一种适合外查找的树，它是一种平衡的多叉树，称为B树。
一棵m阶(m>2)的B树，是一棵平衡的M路平衡搜索树，可以是空树或者满足一下性质：
1. 根节点至少有两个孩子
2. 每个分支节点都包含k-1个关键字和k个孩子，其中 ceil(m/2) ≤ k ≤ m ceil是向上取整函数
3. 每个叶子节点都包含k-1个关键字，其中 ceil(m/2) ≤ k ≤ m
4. 所有的叶子节点都在同一层
5. 每个节点中的关键字从小到大排列，节点当中k-1个元素正好是k个孩子包含的元素的值域划分
6. 每个结点的结构为：（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。
📂 插入
插入流程：
1. 如果树为空，直接插入新节点，作为根节点。
2. 树非空，找到待插入元素在树的插入位置（维护B树的性质，一定要在叶子节点中插入）
3. 找到元素要插入的节点cur后，插入元素，注意元素一定是从小到大排序的。
4. 检测该节点cur是否满足B树性质：即节点中元素个数是否等于M，如果小于则满足
5. 如果不满足，就进行分裂：
a. 申请新节点brother。
b. 找到cur节点中间位置mid，mid之后的元素和孩子节点移到brother中。
c. mid元素及brother节点插入到上层节点parent，重复上述操作，指导节点满足B树性质。
一下代码是为了更好理解 B-树插入流程，并不是为了造更好的轮子，但是整体结构上大致是一样的。
template<class K, int M>
struct BTreeNode
{
typedef BTreeNode<K, M> Node;
K _keys[M];
Node* _subs[M + 1];
size_t _n = 0;
Node* _parent = nullptr;
BTreeNode()
{
for (int i = 0; i < M; ++i)
{
_keys[i] = K();
_subs[i] = nullptr;
}
_subs[M] = nullptr;
}
};
template<class K,int M = 3>
class BTree
{
typedef BTreeNode<K, M> Node;
public:
pair<Node*, int> Find(const K& key)
{
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
size_t i = 0;
while(i < cur->_n)
{
if (key < cur->_keys[i])
{
break;
}
else if (key > cur->_keys[i])
{
++i;
}
else
{
return make_pair(cur, 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)
{
if (node->_keys[end] >= key)
{
node->_keys[end + 1] = node->_keys[end];
node->_subs[end + 2] = node->_subs[end + 1];
--end;
}
else
{
break;
}
}
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 = 1;
return true;
}
//去重
pair<Node*, int> it = Find(key);
if (it.second != -1)
{
return false;
}
Node* cur = it.first;
insertKey(cur, key, nullptr);
//节点未满，可以继续存放关键码 , 不需要分裂直接返回
if (cur->_n != M)
{
return true;
}
//节点满了，向左 向上分裂
//1. 找到节点数据域中间位置
//2. 给一个新节点，将中间位置以后数据移动到brother
//3. 中间位置数据移动到父节点
//4. 节点连接
while (cur->_n == M)
{
Node* brother = new Node;
size_t mid = cur->_n >> 1;
int i = mid + 1, j = 0;
while (i < M)
{
//cur 把关键字及其左孩子给brother
brother->_keys[j] = cur->_keys[i];
brother->_subs[j++] = cur->_subs[i];
cur->_keys[i] = K();
cur->_subs[i] = nullptr;
++i;
}
//最后处理一下最右位置的孩子
brother->_subs[j] = cur->_subs[i];
cur->_subs[i] = nullptr;
K midKey = cur->_keys[mid];
cur->_keys[mid] = K();
brother->_n = j;
cur->_n = cur->_n - j - 1;
Node* parent = cur->_parent;
if (parent == nullptr)
{
//分裂的是根节点
_root = new Node;
_root->_keys[0] = midKey;
_root->_subs[0] = cur;
_root->_subs[1] = brother;
_root->_n = 1;
cur->_parent = _root;
brother->_parent = _root;
}
else
{
//不是根节点 处理完当前层后，继续往上处理
insertKey(parent, midKey, brother);
cur = parent;
parent = cur->_parent;
}
}
return true;
}
private:
Node* _root = nullptr;
};B-树效率是很高的，大多数场景下，M设为1024，因此对于10亿的数据量，我们只需要3次磁盘访问即可，对比二叉平衡树的十几次的磁盘访问是很快的，大大减少了读取磁盘的次数。
📁 B+树
B+树是B树的变形，是在B树基础上优化的多路平衡搜索树，B+树的规则跟B树基本类似，但是又在B树的基础上做了以下几点改进优化：
1. 分支节点的子树指针与关键字个数相同
2. 分支节点的子树指针p[i]指向关键字值大小在[k[i]，k[i+1])区间之间
3. 所有叶子节点增加一个链接指针链接在一起
4. 所有关键字及其映射数据都在叶子节点出现
B+树的特性：
1. 所有关键字都出现在叶子节点的链表中，且链表中的节点都是有序的。
2. 不可能在分支节点中命中。
3. 分支节点相当于是叶子节点的索引，叶子节点才是存储数据的数据层。
B+树的分裂：
当一个结点满时，分配一个新的结点，并将原结点中1/2的数据复制到新结点，最后在父结点中增加新结点的指针；B+树的分裂只影响原结点和父结点，而不会影响兄弟结点，所以它不需要指向兄弟的指针。
📁 B*树
B*树是B+树的变形，在B+树的非根和非叶子节点再增加指向兄弟节点的指针。
B*树的分裂：
当一个结点满时，如果它的下一个兄弟结点未满，那么将一部分数据移到兄弟结点中，再在原结点插入关键字，最后修改父结点中兄弟结点的关键字（因为兄弟结点的关键字范围改变了）；如果兄弟也满了，则在原结点与兄弟结点之间增加新结点，并各复制1/3的数据到新结点，最后在父结点增加新结点的指针。
所以，B*树分配新结点的概率比B+树要低，空间使用率更高；
📁 总结
B树：有序数组+平衡多叉树；
B+树：有序数组链表+平衡多叉树；
B*树：一棵更丰满的，空间利用率更高的B+树。
此外，B-树最常见的应用就是用来做索引。MySQL官方对索引的定义为：索引(index)是帮助MySQL高效获取数据的数据结构，简单来说：索引就是数据结构。
