目录
一、B树的由来
我们之前已经学习过了很多的搜索树，比如红黑树或者AVL树。他们都是属于二叉搜索树的范畴，在内存中的查找效率已经足够优秀了，为logN次（即树的高度次）。但是正是由于他们是二叉搜索树，这就注定导致其高度在数据量很大的时候同样不小。
由于二叉树树节点在磁盘中的存储的位置是不确定的，所以可能导致的结果就是：每一次往下走一层，磁盘就要重新定位，重新读数据。这就使得磁盘浪费在定位方面的时长较大，而真正取数据却只取到了一点点。（因为磁盘为了摊低定位的时间，是一次读一大片数据到缓存，如果你的数据比较连续存储的话，下一次就不用进行磁盘IO，而是在缓存中直接拿了）
二、B树的优势
举个例子，如果你的二叉树高度是30层，那么你想要找到一个数据的时间就是30次磁盘IO。由于早期的磁盘技术不够发达，会使得查找的效率极度降低。当时的工程师们为了解决这个问题而研究出了B树。
B树的优势在于：
（1）B树能够显著的降低树的高度，因为他不再局限于二叉搜索树，而是变多叉搜索树。
（2）且一个节点中不再仅仅存放一个数据，而是存放大量的数据，人为的让数据在一个节点中就能让他们在磁盘中连续存放。
一棵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。
三、B树的插入过程分析
为了简单起见，假设M = 3. 即三叉树，每个节点中存储两个数据（关键字），两个数据可以将区间分割成三个部分，因此节点应该有三个孩子，为了后续实现简单期间，节点的结构如下：
注意：孩子永远比数据多一个。
用序列{53, 139, 75, 49, 145, 36, 101}构建B树的过程如下：
第一步：
第二步：分裂
第三步：仍然直接插入
第四步：分裂
最后一步：第一层满了，再向上开辟一层，进行分裂
可以分析出：
（1）新的关键字只能在叶子节点插入（最后一层的节点），然后通过调整向上生长或者向右生长，维护树的相对关系。
（2）B树是天然的平衡树，因为他不存在向下生长，只会向右/向上生长。
（3）上一层一定要维护下一层的连接所以有了孩子节点，这是毋庸置疑的。但是要注意，因为存在向上生长的情况，所以孩子节点一定也要能直接连接到父亲节点，在设计BTreeNode的时候要注意。
四、B树插入和查找的实现
#pragma once
#include <utility>
template<class K,size_t M=3>
struct BTreeNode
{
size_t _n = 0; //当前节点的关键字数量
K _keys[M]; //关键字数组
BTreeNode<K, M>* _childs[M+1]; //孩子数组
BTreeNode<K, M>* _parent=nullptr; //当前节点的父亲指针
BTreeNode()
{
//构造函数把孩子数组和关键字数组置为空
for (size_t i=0;i<M;i++)
{
_keys[i] = K();
_childs[i] = nullptr;
}
//以为我们故意多存了一个孩子节点，也处理一下
_childs[M] = nullptr;
}
};
template<class K,size_t M>
class BTree
{
public:
typedef BTreeNode<K, M> Node;
private:
Node* _root;
public:
//1.查找key值是否在树中存在，存在返回该节点的指针，以及元素下标;不存在返回空，下标不可信
std::pair<Node*, int> Find(const K& key);
//2.向树中插入一个值
bool Insert(const K& key);
//3.向树的node节点，插入key值，和child子树
void InsertKeyAndChild(Node* node, const K& key, Node* child);
//4.中序遍历
void InOrder()
{
_InOrder(_root);
}
void _InOrder(Node* root)
{
if (root == nullptr)
{
return;
}
//每一个节点都要走中序
for (size_t i = 0;i < root->_n;i++)
{
_InOrder(root->_childs[i]); //左
cout << root->_keys[i] << " "; //根
}
_InOrder(root->_childs[root->_n]); //右
}
};
//这里使用typename是告诉编译器Node*是一个类型，而非BTree类中的一个成员（因为使用::符号编译器默认是成员）
template<class K, size_t M>
std::pair<typename BTree<K, M>::Node*, int> BTree<K, M>::Find(const K& key)
{
Node* parent = nullptr;
Node* cur = _root;
int pos = -1;
//当cur没有走到叶子节点的孩子，就一直往下走
while(cur!=nullptr)
{
size_t i = 0;
//遍历一个节点
while (i<cur->_n)
{
//1.如果key<cur->_keys[i],说明要去左孩子找，退出当前节点的循环
if (key < cur->_keys[i])
{
parent = cur;
cur = cur->_childs[i];
break;
}
//2.如果key>cur->_keys[i],说明这个节点的i位置不对，让i++，当i+到cur->_n的时候，就超出了这个节点，说明该节点没有，去右孩子找
else if (key > cur->_keys[i])
{
i++;
break;
}
//3.如果key==cur->_keys[i],说明找到了，直接退出循环返回
else
{
std::pair<Node*, int> ret = std::make_pair(cur,i);
return ret;
}
}
//当i == cur->_n的时候，说明该节点找完了，但是却没有找到,说明要去右子树找
if (i == cur->_n)
{
parent = cur;
cur = cur->_childs[i];
}
}
//当cur走到nullptr，说明整棵树都找完了，没有找到，则返回最后一次查找的叶子节点和-1.（方便以后插入）
std::pair<Node*, int> ret = std::make_pair(parent,-1);
return ret;
}
template<class K, size_t M>
void BTree<K, M>::InsertKeyAndChild(Node* node, const K& key, Node* child)
{
//1.插入排序，使得插入后仍然保持有序
//end是最后一个关键字数量-1，即最后一个关键字的下标
int end = node->_n - 1;
while (end>=0)
{
//从后往前插入，如果比key大就一个个往后挪动
if (key<node->_keys[end])
{
//为什么这里不用担心end+1会越界呢？因为他肯定不满，只要满了一定在上一次插入的时候就分裂了
node->_keys[end + 1] = node->_keys[end];
//还要把他的孩子往后挪动一格
node->_childs[end+2] = node->_childs[end + 1];
end--;
}
else
{
break;
}
}
//走到这里说明key到了合适的位置，直接插入到end+1的位置
node->_keys[end + 1] = key;
node->_n++;
//把自己的兄弟变成自己的右孩子
node->_childs[end + 2] = child;
//最后把孩子连接到父亲
if (child!=nullptr)
{
child->_parent = node;
}
}
template<class K, size_t M>
bool BTree<K, M>::Insert(const K& key)
{
//1.如果是空树，直接插入到root的第一个位置
if (_root==nullptr)
{
_root = new BTreeNode<K,M>();
_root->_n++;
_root->_keys[0] = key;
return true;
}
//2.如果不是空树，只能插入到叶子节点，然后进行调整
//先要找到在哪里插入
std::pair<Node*, int> ret = Find(key);
Node* cur = ret.first;
int pos = ret.second;
//如果pos!=-1，说明在树中能够找到，则返回错误插入失败
if (pos!=-1)
{
return false;
}
//如果pos==-1，说明不存在，可以插入
//而cur就是要插入的节点的指针,要插入的值就是key
//相当于插入一个key值和一个空树
//为什么要设置一个newkey呢？因为我们的参数是const的，无法修改，而真正的插入过程可能涉及插入后导致往上层插入，需要变换key值
K newkey = key;
Node* child = nullptr;
while (1)
{
InsertKeyAndChild(cur,newkey,child);
//判断此节点有没有满，如果满了则分裂，拷贝，往上插入
if (cur->_n<M)
{
return true;
}
else
{
size_t mid = M / 2;
//1.构造一个兄弟，把右半边拷贝给兄弟
Node* brother = new Node();
int j = 0;
for (int i=mid+1;i<=M-1;i++)
{
//拷贝关键字
brother->_keys[j] = cur->_keys[i];
//挪动孩子到兄弟
brother->_childs[j] = cur->_childs[i]; //左孩子
//修改孩子的父亲
if (cur->_childs[i]!=nullptr)
{
cur->_childs[i]->_parent = brother;
}
//对cur节点的右半区清空,防止下一次查找的时候错误找到了
cur->_keys[i] = K();
cur->_childs[i] = nullptr;
j++;
}
//右孩子一直没拷贝，最后再来拷贝最右的孩子（如果在循环中拷贝了，就会同一个位置覆盖拷贝的问题）
brother->_childs[j] = cur->_childs[M]; //右孩子
if (cur->_childs[M]!=nullptr)
{
cur->_childs[M]->_parent = brother;
}
//拷贝走了就清空原来节点对应位置的值，防止下一次查找错误
cur->_childs[M] = nullptr;
brother->_n = j;
cur->_n -= j;
//2.mid往上一层插入
K midKey = cur->_keys[mid];
cur->_keys[mid] = K();
//如果上一层不存在，则创建
if (cur->_parent=nullptr)
{
_root = new Node();
_root->_keys[0] = midKey;
_root->_childs[0] = cur;
_root->_childs[1] = brother;
_root->_n = 1;
cur->_parent = _root;
brother->_parent = _root;
break;
}
//如果上一层存在，则插入到上一层的最后(仍然是执行这个逻辑，只需要更新一下cur，child，newkey即可)，再进行调整
//变成了要在parent节点插入midKey和brother(因为上一层既然存在的话，左边就已经连接好了，只需要管右边)
else
{
newkey = midKey;
child = brother;
cur = cur->_parent;
}
}
}
return true;
}
B树虽然足够优秀了，但是却有着更强大的数据结构来代替他，即B+树和B*树。所以我们在数据库中使用的却不是他，而是B+树，但是B+树是由B树升级而来的，基础结构还是B树。