常见的搜索结构

1.我们学过很多的搜索结构，例如：

种类	数据格式	时间复杂度
顺序查找	无要求	O(N)
二分查找	有序	O( $log_2 N$ )
二叉搜索树	无要求	O(N)
二叉平衡树(AVL树和红黑树)	无要求	O( $log_2 N$ )
哈希	无要求	O(1)

①：这些结构适用的是数据量相对起来并不是很大的情况，能够一次性存放在内存中，进行数据查找的情况。但是如果说，我们要存储的数据有100G，那么内存基本上是不够的，所以这些数据要放在磁盘中，但是如果放在磁盘上了，我们要如何寻找我们要找的数据呢?

答：我们可以考虑存放关键字及其映射的数据的地址放到一个内存中的搜索树的节点中，那么要访问数据时，先去这个地址去磁盘访问数据。

在这里插入图片描述
就是假设我们使用一个树形结构，那么每个节点中保存的应该就是该数据在磁盘上存储的物理地址，然后我们去寻找我们要找到数据的时候，先在树形结构中在地址找到该节点的值，然后与我们要查找的数据进行比较，然后继续寻找。

②磁盘的结构如下：
在这里插入图片描述
我们可以看到，在磁盘上进行存储的时候(也就是我们进行IO操作的时候)，主要的时间还是浪费在了寻找数据位置的时候，因为磁盘旋转一周需要8.33ms，可见这个一周的时间还是很慢的，这也是我们使用B树，而不去使用我们现有的一些查找结构的原因之一。

2.内查找结构的缺陷(在内存上的查找)：

①使用平衡二叉搜索树的缺陷：

平衡二叉搜索树的高度是 $log_2 N$ ，这个查找速度在内存中是很快的。但是要是在外查找(在磁盘上的查找)，也是数据存储在磁盘上的时候，访问磁盘是很慢的，因为每次只能取出一个数据所存的地址，然后跟我们要查找的数据进行比较，而在外查找中进行查找时，主要的时间浪费还是出现在了查找数据位置的时候，所以它访问磁盘的速度是很慢的，数据量小的情况下，我们可能感受不到，但是如果说数据量很大，那么 $log_2 N$ 的磁盘访问，也是一个很难接收的结果。

②使用哈希表的缺陷：

哈希表的效率很高是O(1)，但是哈希表是存在哈希冲突的，如果说我们要存储的数据很大，那么映射在哈希表上的地址会存在很严重的哈希冲突，一些极端的场景下，使得一个位置上的冲突是非常严重的，这样会导致访问次数增加的很快，这也是非常浪费时间的。

3.经过上面两个内查找结构的情况，我们总结了在外查找结构中要提高的点：

提高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-树的插入分析

首先，我们在实现的时候，我们会将M设置为3，主要是为了我们在插入节点的时候，我们能更好的看到插入的情况。(正常情况下，投入使用的B树结构，基本上M的大小一般为1024)

1.M=3，那么就是三叉树，每个节点中存储两个数据，两个数据可以将区间分割成三个部分，因此节点就有三个孩子，如下：
在这里插入图片描述
如上图，我们进行了转变，主要的变化就是节点中存储数据的个数和存储孩子节点的个数有增加。(主要的原因就是，我们进行操作的时候，只有当这个节点进行了插入之后，我们才能进行操作，就是修改B树的操作；如果说我们就设置成M，那么我们就没有修改的空间了，此时插入第M个数据的时候，就即便是插入了，也无不能保证所有子节点在同一层这个性质的条件了)

注意：孩子永远比数据多一个。

2.用序列{53, 139, 75, 49, 145, 36, 101}构建B树的过程如下：
在这里插入图片描述
此时，如上图，75插入后，那么一个节点中数据的数量已经超过了M了，因为我们定义的M等于3(一个节点的孩子节点最大等于3，而一个节点的数据数量是少于孩子节点数量一个的)

所以说，此时75的插入，已经超过了节点的最大数量，所以必须进行修改了，那么如何修改呢？如下：
在这里插入图片描述
如上图，操作如上图所示，也就是取m/2大小的右边，进行分开，新建立一个节点，将原节点中m/2个大小的数据拷贝过去(注意：m/2是向上取整的，因为还要取中间的节点成为父节点连接左右孩子)，然后中间的数据建立一个父节点，然后连接两个子节点即可。

在这里插入图片描述
这次插入没有破坏B树的性质，所以不存在修改的操作

而插入36后，我们发现有节点不满足了，所以必须进行分裂操作，如上图。(操作方式还是类似的)，修改完如下图：

3.插入的第一步，那么就是在B树种找到我们要插入的位置，然后进行操作，而插入的位置包括节点和在节点的数组种插入的位置，所以说实现代码如下：

pair<BTreeNode*, int> _Findpos(const T& key)   //寻找要插入的节点数组的下标以及所在的节点
	{
		BTreeNode* p = _root;    //从根节点开始查找
		BTreeNode* parent = p;   //定义一个父节点
		size_t i;
		while (1)
		{
			i = 0;   //到达一个节点，从0开始
			for (; i < p->_size; ++i)
			{
				if (i == p->_size-1 && p->_key[i] < key)  //该节点的最后一个数据了，那么就退出
				{                                         //在下一个子节点进行查找
					parent = p;
					p = p->_pSub[i+1];
					break;
				}
				else if (p->_key[i] > key)              //该数据大于我们要插入的数据，那么就去他的
				{                                       //前一个子节点
					parent = p;
					p = p->_pSub[i];
					break;
				}
			}
			if (p == nullptr)   //此时查找到根节点了
			{
				break;
			}
		}
		return make_pair(parent, i);    //返回其要插入的节点，和对应要插入的位置
	}

而该代码的具体实现的操作如下：
在这里插入图片描述

4.插入过程的总结：

如果树为空，直接插入即可。
如果树不是空的，那么就要找到要插入数据的位置进行插入。(而插入的位置一定是叶子节点，因为上面的操作我们看出来，B树是天然平衡的，而平衡的原因是B树种每个叶子节点的父节点都是通过分裂生出来的)
插入的时候肯定要检测是该节点是否可以插入。(我们实现的时候是假设存在的key是不可以插入的)
插入完成后，就要检测插入的该节点的数据数量是否已经等于M了，如果等于，那么就要进行分裂操作。如果不等于，那么就不需要进行其他操作了。
如果需要进行分裂：
①：申请新节点。
②：找到要分割节点的数据部分的中间节点。
③：将右侧的所有数据以及节点搬移到新节点中。
④：将中间位置元素以及新节点往该节点的双亲节点中插入，即继续4操作。
如果向上已经分裂到根节点的位置，插入结束。

这基本上就是B树的插入操作流程。

B-树的插入实现

B-树的节点设计

节点的设计如下：

template<class T,int M = 3>   //3为可配置的大小，表示一个节点所存储的最大节点个数
struct BTreeNode
{
	T _key[M];                      //一个节点最多存M个元素
	BTreeNode<T, M>* _pSub[M + 1];  //那么孩子的数量就比节点数量多一个
	BTreeNode<T, M>* _pParent;     //存放孩子的父节点，为插入操作准备
	size_t _size; //当前节点的元素个数

	BTreeNode()
		:_pParent(nullptr)
		,_size(0)
	{
		for (size_t i = 0; i <= M; ++i)
		{
			_pSub[i] = nullptr;
		}
	}
};

如上述代码，我们将M的大小设置为3，为了我们更好的看到插入的流程。

插入key的过程

插入key的过程，是这样的：因为我们是通过寻找插入位置，返回的直接就是要插入的是节点和要插入在该节点数据向量的位置，所以直接进行插入，而插入的思想就是按照插入排序的思想进行的，如下：

	void _InsertKey(const T& key, BTreeNode* pCur,BTreeNode* pSub)   //将该数插入到该节点中
	{                                                                //插入的同时，将插入节点的
		size_t i = pCur->_size-1;                                    //孩子都插入了
		while(i >= 0)                              //寻找插入的节点
		{                                          //从后往前进行查找，主要的目的是在移动数据的同时
			if (key < pCur->_key[i])               //也要将移动该数据的子孩子进行移动
			{
				pCur->_key[i+1] = pCur->_key[i];
				pCur->_pSub[i + 2] = pCur->_pSub[i+1];
				i--;
			}
			else
			{
				break;
			}
		}
		pCur->_key[i + 1] = key;          //插入要插入的数据
		pCur->_pSub[i + 2] = pSub;        //将该插入数据的孩子也进行插入
		if (pSub)
		{
			pSub->_pParent = pCur;
		}
		pCur->_size++;
	}

因为我们进行插入的时候，插入的不一定是新的节点，有可能插入的是我们要进行分裂的节点，所以对于其插入时，移动数据的孩子节点和新插入数据的孩子都必须进行移动操作。

B-树的插入实现

template<class T,int M = 3>   //3为可配置的大小，表示一个节点所存储的最大节点个数
struct BTreeNode
{
	T _key[M];                      //一个节点最多存M个元素
	BTreeNode<T, M>* _pSub[M + 1];  //那么孩子的数量就比节点数量多一个
	BTreeNode<T, M>* _pParent;     //存放孩子的父节点，为插入操作准备
	size_t _size; //当前节点的元素个数

	BTreeNode()
		:_pParent(nullptr)
		,_size(0)
	{
		for (size_t i = 0; i <= M; ++i)
		{
			_pSub[i] = nullptr;
		}
	}
};
template<class T,int M = 3>
class BTree
{
	typedef struct BTreeNode<T, M> BTreeNode;
public:
	BTree():_root(nullptr)
	{}
public:
	pair<BTreeNode*, int> _Findpos(const T& key)   //寻找要插入的节点数组的下标以及所在的节点
	{
		BTreeNode* p = _root;    //从根节点开始查找
		BTreeNode* parent = p;   //定义一个父节点
		size_t i;
		while (1)
		{
			i = 0;   //到达一个节点，从0开始
			for (; i < p->_size; ++i)
			{
				if (i == p->_size-1 && p->_key[i] < key)  //该节点的最后一个数据了，那么就退出
				{                                         //在下一个子节点进行查找
					parent = p;
					p = p->_pSub[i+1];
					break;
				}
				else if (p->_key[i] > key)              //该数据大于我们要插入的数据，那么就去他的
				{                                       //前一个子节点
					parent = p;
					p = p->_pSub[i];
					break;
				}
			}
			if (p == nullptr)   //此时查找到根节点了
			{
				break;
			}
		}
		return make_pair(parent, i);    //返回其要插入的节点，和对应要插入的位置
	}
	void _InsertKey(const T& key, BTreeNode* pCur,BTreeNode* pSub)   //将该数插入到该节点中
	{                                                                //插入的同时，将插入节点的
		size_t i = pCur->_size-1;                                    //孩子都插入了
		while(i >= 0)                              //寻找插入的节点
		{                                          //从后往前进行查找，主要的目的是在移动数据的同时
			if (key < pCur->_key[i])               //也要将移动该数据的子孩子进行移动
			{
				pCur->_key[i+1] = pCur->_key[i];
				pCur->_pSub[i + 2] = pCur->_pSub[i+1];
				i--;
			}
			else
			{
				break;
			}
		}
		pCur->_key[i + 1] = key;          //插入要插入的数据
		pCur->_pSub[i + 2] = pSub;        //将该插入数据的孩子也进行插入
		if (pSub)
		{
			pSub->_pParent = pCur;
		}
		pCur->_size++;
	}
	bool Insert(const T& key)                      //B树的插入操作
	{
		if (_root == nullptr)                     //如果树是空树，直接插入返回
		{
			_root = new BTreeNode();
			_root->_key[0] = key;
			_root->_size = 1;
			return true;
		}

		pair<BTreeNode*,int> ret = _Findpos(key);

		BTreeNode* cur = ret.first;
		BTreeNode* brother = nullptr;
		T k = key;

		while(true)            
		{
			_InsertKey(k, cur, brother);
			if (cur->_size < M)     //证明插入节点后，没满
			{
				break;
			}
			size_t mid = M / 2;
			size_t j = 0;
			brother = new BTreeNode();         //首先分离出兄弟节点
			for (size_t i = mid+1; i < M; ++i)
			{
				brother->_key[j] = cur->_key[i];
				brother->_pSub[j] = cur->_pSub[i];
				if (cur->_pSub[i])                        //重要：更新孩子的父节点
				{
					cur->_pSub[i]->_pParent = brother;
				}
				j++;
			}

			brother->_pSub[j] = cur->_pSub[M];
			brother->_size = j;
			if (cur->_pSub[M])                         //重要：更新孩子的父节点
			{
				cur->_pSub[M]->_pParent = brother;
			}
			cur->_size = cur->_size-j-1;

			if (cur->_pParent == nullptr)          //如果分裂到根节点,那么分裂完就要返回
			{
				BTreeNode* Parent = new BTreeNode();
				Parent->_key[0] = cur->_key[mid];
				Parent->_pSub[0] = cur;
				Parent->_pSub[1] = brother;
				cur->_pParent = Parent;
				brother->_pParent = Parent;
				Parent->_size = 1;
				_root = Parent;
				break;
			}
			else
			{
				//如果分裂的节点不是根节点，那么就要继续向上分裂
				k = cur->_key[mid];
				cur = cur->_pParent;
			}
		}
		return true;
	}
private:
	BTreeNode* _root;
};

B-树的性能分析

1.对于一棵节点为N度为M的B-树，查找和插入需 $log{M1}N$ ~ $log{M/2}N$ 次比较，这个很好证明：对于度为M的B-树，每一个节点的子节点个数为M/2 ~(M-1)之间，因此树的高度应该在要 $log{M-1}N$ 和 $log{M/2}N$ 之间，在定位到该节点后，再采用二分查找的方式可以很快的定位到该元素。