1.B树的介绍

2.B树节点的定义及其实现

2.1B树节点的定义：

2.2B树的查找

2.2B树的插入

2.3B树的删除

3.B+树和B*树

        4.总结

1.B树的介绍

1970年，R.Bayer和E.mccreight提出了一种适合外查找的树，它是一种平衡的多叉树，称为B树(有些地方写
的是B-树，注意不要误读成"B减树")。一棵M阶(M>2)的B树，是一棵平衡的M路平衡搜索树，可以是空树或者满足一下性质：

1. 根节点至少有两个孩子
2. 每个非根节点至少有M/2(上取整)个孩子,至多有M个孩子
3. 每个非根节点至少有M/2-1(上取整)个关键字,至多有M-1个关键字，并且以升序排列
4. key[i]和key[i+1]之间的孩子节点的值介于key[i]、key[i+1]之间
5. 所有的叶子节点都在同一层

我们之前学习了一些基础的搜索结构,如下表所示：

| 种类 |  数据格式 | 时间复杂度 |
|      顺序查找 | 无要求 | O（N） |
|     二分查找 | 有序 | O（log N) |
|     二叉搜索树 | 无要求 | O（N) |
|    平衡搜索树 | 无要求 | O(logN) |
|     哈西 | 无要求 | O(1) |
|    位图 | 无要求 | O(1) |
| 布隆过滤器 | 无要求 | O(k) |

既然有了这些搜索的数据结构为什么还有引入B树这种数据结构呢？我们之前学过的平衡搜索二叉树已经足够优秀了，时间复杂度O（log N）已经非常的优秀了，10亿数据只要查找30次左右。这是因为：如果数据量非常大，一次性无法加载到内存中，使用上述结构就
不是很方便。比如：使用平衡树搜索一个大文件：

而IO的速度是很慢的。

解决方案：

1. 提高IO的速度
2. 降低树的高度---多叉树平衡树

下面我们来看例子：

如果我们使用二叉搜索树作为索引结构，假设树的高度为4，查找10流程如下

二叉搜索树的结构：

** 第一次磁盘IO**：

第二次磁盘IO：

**第三次IO： **

第四次IO： 

我们可以发现磁盘的IO次数是由二叉搜索树的高度决定。所以才引入了B树

下面我们以三阶的B树为例：

这棵树中，咱们重点来看(2,6)节点。该节点有两个元素2和6，又有三个孩子1,(3,5)，8。其中1小于元素2，(3，5）在元素2,6之间，8大于(3,5)，正好符合刚刚所列的几条特征。

下面来看一下B树的查询过程：假设我们要找的是5

**第一次IO： **

在内存中和9进行比较：

第2次磁盘IO：

** 在内存中和2，6比较：**

第3次磁盘IO：

在内存中和3，5进行比较：

通过整个流程我们可以看出，B-树在查询中的比较次数其实不比二叉查找树少，尤其当单一节点中的元素数量很多时。可是相比磁盘I0的速度，内存中的比较耗时几乎可以忽略。所以只要树的高度足够低，IO次数足够少，就可以提升查找性能。相比之下节点内部元素多一些也没有关系，仅仅是多了几次内存交互，只要不超过磁盘页的大小即可。这就是B-树的优势之一

 2.B树节点的定义及其实现

2.1B树节点的定义：

template<class K,class V,size_t M>
struct BTreeNode {
	BTreeNode()
		:_kvSize(0)
		, _parent(nullptr)
	{
		for (size_t i = 0; i < M+1; i++) {//初始化
			_subs[i] = nullptr;
		}
	}
	pair<K, V>_kvs[M];//值
	BTreeNode<K, V,M>* _subs[M+1];//孩子的数量注意我们在这里面多看了一个空间方便后面的分裂
	BTreeNode<K, V,M>* _parent;//父亲指针
	size_t _kvSize;//个数
};

注意在这里我们多看了一个空间，方便后序插入节点时的分裂。

2.2B树的查找

在上面已经介绍过B树的查找在这里就只给出代码：

pair<Node*, int> Find(const K& key)
	{
		Node* parent = nullptr;//记录父亲节点
		Node* cur = _root;//从根开始找
		while (cur)
		{
			size_t i = 0;
			while (i < cur->_kvSize)   // 如果M比较大，这里应该改一改换成二分查找会快一些
			{
				if (cur->_kvs[i].first < key) // key大于当前位置key，往右找
					++i;
				else if (cur->_kvs[i].first > key) // key小于当前位置key，就往左孩子去找
					break;
				else
					return make_pair(cur, i);//找到了并返回对应的位置
			}

			parent = cur;//记录父亲节点
			cur = cur->_subs[i];
		}

		// 没有找到并将父亲节点返回
		return make_pair(parent, -1);
	}

2.2B树的插入

比如我们要在这颗B树上插入4：

自顶向下查找4的节点位置，发现4应当插入到节点元素3，5之间。

节点3，5已经是两元素节点，无法再增加。父亲节点 2， 6 也是两元素节点，也无法再增加。根节点9是单元素节点，可以升级为两元素节点。于是拆分节点3，5与节点2，6，让根节点9升级为两元素节点4，9。节点6独立为根节点的第二个孩子。

拆分时要将孩子节点也要带走： 

对应代码：

bool Insert(const pair<K, V>& kv)
	{
		if (_root == nullptr)//空树直接创建新节点
		{
			_root = new Node;
			_root->_kvs[0] = kv;
			_root->_kvSize = 1;

			return true;
		}

		pair<Node*, int> ret = Find(kv.first);//先进行查找
		// 已经有了，不能插入  (当前如果允许插入就是mutil版本)
		if (ret.second >= 0)
		{
			return false;
		}

		// 往cur节点中插入一个newkv和sub
		// 1、如果cur没满就结束
		// 2、如果满了就分裂，分裂出兄弟以后，往父亲插入一个关键字和孩子，再满还要继续分裂
		// 3、最坏的情况就是分裂到根，原来根分裂，产生出一个新的根，就结束了
		// 也就是说，我们最多分裂高度次
		Node* cur = ret.first;//当前节点
		pair<K, V> newkv = kv;
		Node* sub = nullptr;//实现后面的迭代逻辑

		while (1)
		{
			InsertKV(cur, newkv, sub); //插入

			// 1、如果cur没满就结束，判断是否要分裂
			if (cur->_kvSize < M)
			{
				return true;
			}
			else // 2、满了，需要分裂
			{
				// 分裂出一个兄弟节点
				Node* newnode = new Node;

				// 1、拷贝右半区间给分裂的兄弟节点
				// 
				int mid = M / 2;
				int j = 0;
				int i = mid + 1;
				newkv = cur->_kvs[mid];
				cur->_kvs[mid] = pair<K, V>();//清空原来的节点的值
				for (; i < M; ++i)//拷贝值并拷贝孩子节点
				{
					newnode->_kvs[j] = cur->_kvs[i];
					cur->_kvs[i] = pair<K, V>();
					newnode->_subs[j] = cur->_subs[i];
					cur->_subs[i] = nullptr;

					if (newnode->_subs[j])//链接父亲指针
					{
						newnode->_subs[j]->_parent = newnode;
					}

					j++;
					newnode->_kvSize++;//个数增加
				}

				// 还剩最后一个右孩子
				newnode->_subs[j] = cur->_subs[i];
				cur->_subs[i] = nullptr;
				if (newnode->_subs[j])//是否为空
				{
					newnode->_subs[j]->_parent = newnode;
				}

				cur->_kvSize = cur->_kvSize - newnode->_kvSize - 1;//重新计算大小

				// 1、如果cur没有父亲，那么cur就是根，产生新的根
				// 2、如果cur有父亲，那么就要转换成往cur的父亲中插入一个key和一个孩子newnode
				if (cur->_parent == nullptr)//说明当前节点没有父亲是根
				{
					//创建新的根，并链接关系
					_root = new Node;
					_root->_kvs[0] = newkv;
					_root->_subs[0] = cur;
					_root->_subs[1] = newnode;
					cur->_parent = _root;
					newnode->_parent = _root;

					_root->_kvSize = 1;

					return true;
				}
				else
				{//有父亲转化为迭代逻辑
					// 往父亲去插入newkv和newnode，转换成迭代逻辑
					sub = newnode;
					cur = cur->_parent;
				}
			}
		}

		return true;
	}

	void InsertKV(Node* cur, const pair<K, V>& kv, Node* sub)
	{
		// 将kv找到合适的位置插入进去
		int i = cur->_kvSize - 1;//从最后一个位置开始
		for (; i >= 0; )
		{
			if (cur->_kvs[i].first < kv.first)
			{
				break;
			}
			else
			{
				//kv[i]往后挪动，kv[i]的右孩子也挪动
				cur->_kvs[i + 1] = cur->_kvs[i];
				cur->_subs[i + 2] = cur->_subs[i + 1];
				--i;
			}
		}
		//插入并将孩子节点也链接上
		cur->_kvs[i + 1] = kv;
		cur->_subs[i + 2] = sub;
		cur->_kvSize++;
		if (sub)
		{
			sub->_parent = cur;//链接父亲节点
		}
	}

 2.3B树的删除

删除比插入复杂的多在这里就只给出思路：

Ｂ树中关键字的删除比插入更复杂，在这里，只介绍其中的一种方法：

在B树上删除关键字k的过程分两步完成：

（1）找出该关键字所在的结点。然后根据 k所在结点是否为叶子结点有不同的处理方法。
   （2）若该结点为非叶结点，且被删关键字为该结点中第i个关键字key[i]，则可从指针_son[i]所指的子树中
   找出最小关键字Y，代替key[i]的位置，然后在叶结点中删去Y。

因此，把在非叶结点删除关键字k的问题就变成了删除叶子结点中的关键字的问题了。

在B-树叶结点上删除一个关键字的方法：
首先将要删除的关键字 k直接从该叶子结点中删除。然后根据不同情况分别作相应的处理，共有三种可能情况：

（1）如果被删关键字所在结点的原关键字个数n>=ceil(m/2)，说明删去该关键字后该结点仍满足B树的定义。
这种情况最为简单，只需从该结点中直接删去关键字即可。

（2）如果被删关键字所在结点的关键字个数n等于ceil(m/2)-1，说明删去该关键字后该结点将不满足B树的定义，需要调整。

调整过程为：
   如果其左右兄弟结点中有“多余”的关键字,即与该结点相邻的右（左）兄弟结点中的关键字数目大于
ceil(m/2)-1。则可将右（左）兄弟结点中最小（大）关键字上移至双亲结点。而将双亲结点中小（大）于该上
移关键字的关键字下移至被删关键字所在结点中。
   如果左右兄弟结点中没有“多余”的关键字，即与该结点相邻的右（左）兄弟结点中的关键字数目均等于
ceil(m/2)-1。这种情况比较复杂。需把要删除关键字的结点与其左（或右）兄弟结点以及双亲结点中分割二者
的关键字合并成一个结点,即在删除关键字后，该结点中剩余的关键字加指针，加上双亲结点中的关键字Ki一起，
合并到Ai（是双亲结点指向该删除关键字结点的左（右）兄弟结点的指针）所指的兄弟结点中去。如果因此使双亲
结点中关键字个数小于ceil(m/2)-1，则对此双亲结点做同样处理。以致于可能直到对根结点做这样的处理而使
整个树减少一层。

总之，设所删关键字为非终端结点中的Ki，则可以指针Ai所指子树中的最小关键字Y代替Ki，然后在相应结点中删除Y。对任意关键字的删除都可以转化为对最下层关键字的删除。

下面举个简单的例子删除11这个节点：

首先找到11这个节点：

删除11后，节点12只有一个孩子，不符合B树规范。因此找出12,13,15三个节点的中位数13，取代节点12，而节点12自身下移成为第一个孩子。（这个过程称为左旋）

 3.B+树和B*树

B+树是B-树的变形，也是一种多路搜索树，其规则如下：

1. 其定义基本与B-树相同，除了：
2. 非叶子节点的子树指针与关键字个数相同
3. 非叶子节点的子树指针p[i]，指向关键字值属于【k[i]，k[i+1])的子树
4. 为所有叶子节点增加一个链指针
5. 所有关键字都在叶子节点出现

既然有了B树那为什么还要有B+树了？下面我们从各自的优点出发：

B树：

B树好处：

B树的每一个结点都包含key(索引值) 和 value(对应数据)，因此方位离根结点近的元素会更快速。（相对于B+树）

B树的不足：

不利于范围查找(区间查找)，如果要找 0~100的索引值，那么B树需要多次从根结点开始逐个查找。

B+树的优点：

1.B+树的层级更少：相较于B树B+每个非叶子节点存储的关键字数更多，树的层级更少所以查询数据更快；

2.B+树查询速度更稳定：B+所有关键字数据地址都存在叶子节点上，所以每次查找的次数都相同所以查询速度要比B树更稳定;

3.B+树天然具备排序功能：B+树所有的叶子节点数据构成了一个有序链表，在查询大小区间的数据时候更方便，数据紧密性很高，缓存的命中率也会比B树高。

4.B+树全节点遍历更快：B+树遍历整棵树只需要遍历所有的叶子节点即可，而不需要像B树一样需要对每一层进行遍历，这有利于数据库做全表扫描。

这就是为什么要有B+树的原因。

B*树：

B*树是B+树的变形，在B+树的非根和非叶子节点再增加指向兄弟节点的指针。

1.B树定义了非叶子结点关键字个数至少为(2/3)M，即块的最低使用率为2/3(代替B+树的1/2） 。
2.B+树的分裂:当一个结点满时，分配一个新的结点，并将原结点中1/2的数据复制到新结点，最后在父结点中增加新结点的指针﹔B+树的分裂只影响原结点和父结点，而不会影响兄弟结点,所以它不需要指向兄弟的指针。
3.B树的分裂:当一个结点满时，如果它的下一个兄弟结点未满，那么将一部分数据移到兄弟结点中，再在原结点插入关键字，最后修改父结点中兄弟结点的关键字(因为兄弟结点的关键字范围改变了〉﹔如果兄弟也满了，则在原结点与兄弟结点之间增加新结点，并各复制1/3的数据到新结点，最后在父结点增加新结点的指针;
4.所以，B树分配新结点的概率比B+树要低，空间使用率更高﹔
 

4.总结

B-树:多路搜索树，每个结点存储M/2到M个关键字，非叶子结点存储指向关键字范围的子结点;
所有关键字在整颗树中出现，且只出现一次，非叶子结点可以命中﹔
B+树:在B-树基础上，为叶子结点增加链表指针，所有关键字都在叶子结点中出现，非叶子结点作为叶子结点的索引;B+树总是到叶子结点才命中﹔
B*树:在B+树基础上，为非叶子结点也增加链表指针，将结点的最低利用率