B-树----(多插平衡树)

常见的搜索结构

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

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

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

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

②磁盘的结构如下：

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

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

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

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

②使用哈希表的缺陷：

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

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

• 提高IO的速度(SSD(固态硬盘)相比传统机械硬盘快了不少，但是还是没有得到本质性的提升)
• 降低树的高度—多叉树平衡树。

B-树的概念

1970年，R.Bayer和E.mccreight提出了一种适合外查找的树，它是一种平衡的多叉树，称为B树(后面有一个B的改进版本B+树，然后有些地方的B树写的的是B-树，注意不要误读成"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 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);    //返回其要插入的节点，和对应要插入的位置
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

而该代码的具体实现的操作如下：



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;
		}
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

如上述代码，我们将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++;
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

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

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;
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150

B-树的性能分析

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

2.B-树的效率是很高的，对于N = 62*1000000000个节点，如果度M为1024，则$lo{g}_{M/2}N$ <=4，即在620亿个元素中，如果这棵树的度为1024，则需要小于4次即可定位到该节点，然后利用二分查找可以快速定位到该元素，大大减少了读取磁盘的次数。

B+树和B*树

B+树

1.B+树是B树的变形，是在B树的基础上进行了优化，但是本质和B树是类似的，只不过进行了如下几个修改：

1. 分支上节点的子树指针和关键字个数相同。
2. 分支节点的子树指针p[i]指向关键字值大小在(k[i]，k[i+1])区间之间。
3. 所有叶子节点增加一个链接指针链接在一起。
4. 所有关键字及其映射数据都在叶子节点出现。

如下图：

就是对于这个节点而言，每个键值都对应一个孩子，并且一个节点的数据域的最左边数据一定是该节点的数据域中数据最小的那个节点。

2.B+树的特性：

1. 所有关键字都出现在叶子节点的链表中，且链表中的节点都是有序的。
2. 不可能在分支节点中命中。
3. 分支节点相当于是叶子节点的索引，叶子节点才是存储数据的数据层。

也就是，分支节点都是索引(只是索引)，要查找一个数据，就必须查找到叶子节点就可以了，这样看起来是比B树效率更差，但是其实B+树是B树的优化，主要优化的点如下：

①：优化了B树中孩子节点的数量多于数据的数量，这样在实现的时候较B树就会变得简单一些。
②：主要是优化了节点的空间大小，在B树中节点不存储数据，这样就可以存储更多的键值，可以使树变矮，减少IO次数。
③： 叶子节点相连，更便于进行范围查找。

B*树

1.B树：B树是B+树的变形，在B+树的非根和非叶子节点再增加指向兄弟节点的指针。
如下图：

2.B*树的特性

B树较B+树主要的优化点就是在B树进行分裂的时候存在的优化：
①B+树的分裂：
当一个结点满时，分配一个新的结点，并将原结点中1/2的数据复制到新结点，最后在父结点中增加新结点的指针；B+树的分裂只影响原结点和父结点，而不会影响兄弟结点，所以它不需要指向兄弟的指针。

②B*树的分裂：
当一个结点满时，如果它的下一个兄弟结点未满，那么将一部分数据移到兄弟结点中，再在原结点插入关键字，最后修改父结点中兄弟结点的关键字（因为兄弟结点的关键字范围改变了）；如果兄弟也满了，则在原结点与兄弟结点之间增加新结点，并各复制1/3的数据到新结点，最后在父结点增加新结点的指针。

所以，B*树分配新结点的概率比B+树要低，空间使用率更高(在新增节点的时候，尽量使用已经分配而还没利用的空间)。

总结

• B树：有序数组+平衡多叉树。
• B+树：有序数组链表+平衡多叉树。
• B*树：一棵更丰满的，空间利用率更高的B+树。