高阶数据结构——B树

1. 常见的搜索结构

以上结构适适用于数据量相对不是很大，可以或许一次性存放在内存中，进行数据查找的场景。假如数据量很大，好比有100G数据，无法一次放进内存中，那就只能放在磁盘上了，假如放在磁盘上，有需要搜索某些数据，那么假如处理呢？那么我们可以考虑将存放关键字及其映射的数据的地址放到一个内存中的搜索树的节点中，那么要访问数据时，先取这个地址去磁盘访问数据。

使用平衡二叉树搜索树的缺陷：平衡二叉树搜索树的高度是logN，这个查找次数在内存中是很快的。但是当数据都在磁盘中时，访问磁盘速度很慢，在数据量很大时，logN次的磁盘访问，是一个难以担当的结果。
使用哈希表的缺陷：哈希表的服从很高是O(1)，但是一些极端场景下某个位置辩说许多，导致访问次数剧增，也是难以担当的
那如何加速对数据的访问呢？

• 1. 提高IO的速度(SSD相比传统机器硬盘快了不少，但是照旧没有得到本质性的提升)
  
• 2. 降低树的高度---多叉树平衡树
  

2. B树概念

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，如下图所示。
  
  
  

二叉树的示例图：

3. B-树的插入分析

为了简单起见，假设M = 3. 即三叉树，所以每个结点应该包罗两个关键字和三个孩子指针。但是为了方便写代码，我们增长一个关键字和孩子指针。

留意：孩子永远比数据多一个。
用序列{53, 139, 75, 49, 145, 36, 101}构建B树的过程如下：

前两个直接插入即可。

插入第三个时，则不满足我们的条件，每个结点最多只能有k - 1个关键字，所以这里要进行分裂。
分裂步骤：

• 分裂出一个兄弟结点，并拷贝一半的关键字和孩子指针给兄弟结点。
  
• 提取中位数给父亲，没有父亲则创建。
  
• 将根结点，兄弟结点和当前结点进行毗连。
  

中位数是75，所以将75后边的全部值拷贝给兄弟，而当前结点没有父亲结点，所以还要创建一个父亲结点，并将75拷给父亲。

留意，B是是一颗平衡搜索树，所以插入时要留意插入位置，保持有序。

插入36时，我们会发现，左下角的那个结点满了，此时又需要分裂，将中位数49给他的父亲，49背面的数给他的兄弟结点。

右下角的结点又不满足B树的条件了，开始分裂，和前面一样，将139交给父亲，145给兄弟结点。

此时，我们发现，根节点又不满足B树性质了，我们要对根节点进行分裂，如下图所示。

4. B树的插入实现

4.1 插入key的过程

我们可以将插入的过程分为这几步。

• 1. 判断树是否为空，为空则需要创建根结点。
  
• 2. 找到要插入的结点（肯定为叶子结点）。
  
• 3. 将key插入到结点中。
  
• 4. 判断当前结点是否满了，假如满了，则需要开始分裂，没满则结束。
  
• 5. 假如当前结点是根节点（没有父亲），则重新创建一个结点当根，并毗连好相应关系，假如不是根节点，则将当前结点的中位数看成key，要插入的结点酿成了当前结点的父亲，回到第三步。
  

1 - 4步很好理解，可以对照前面的图来分析，第5步不好理解，我们举两个例子来看。
   1. 当前结点是根节点
  

比方这里，我们插入75，已经完成了第三步了，第四步是分裂，将一半的值拷贝给他的兄弟。

尚有最后的一步，我们就可以完成这个插入过程了，即将75给当前结点的父结点。但是当前结点没有父结点，所以我们直接创建一个新结点看成根结点即可。

   当前结点不是根节点
  

假如插入的是36，照旧一样要分裂一半给他兄弟。

现在我们需要将75插入父亲结点，我们会发现插入父结点和插入当前结点的逻辑其实都是一样的，所以我们，在分裂完之后，要将75当成新的key插入到父亲结点当中（一个很重要的逻辑）。所以我们现在又要到第三步去将75插入父亲结点。

第三步实行完，到第四步，发现父亲结点还没有满，插入过程结束。

4.2 B树结点的计划

1. //K是数据类型，M是树的路数，将来就是M叉树
2. template<class K, size_t M>
3. struct BTreeNode
4. {
5.         BTreeNode()
6.         {
7.                 for (size_t i = 0; i < M; i++)
8.                 {
9.                         _keys[i] = K();
10.                         _chlids[i] = nullptr;
11.                 }
12.                 _childs[M] = nullptr;
13.                 _parent = nullptr;
14.                 _size = 0;
15.         }
17.         //为了方便写代码，所以关键字和孩子指针我们都多开了一个空间。
18.         K _keys[M];  //关键字
19.         BTreeNode<K, M>* _childs[M + 1]; //孩子指针
20.         BTreeNode<K, M>* _parent;        //父亲指针
21.         size_t _size; //实际存储的个数
22. };

复制代码

我们使用一个类模板来适配各种类型，M表现树的路树，一个B树的结点中包罗以下几个内容：

• 1. _keys用来保存关键字的数组。
  
• 2. _childs是孩子的指针，指向他的孩子结点。
  
• 3. _parent是父亲指针，将来可以很容易找到当前结点的父亲。
  
• 4. _size是保存的关键字个数，也可以得到孩子的个数（B树结点中，孩子的数量永远比关键字多一个）。
  

4.3 B树的插入实现

B树的插入过程：

• 1. 判断树是否为空，为空则需要创建根结点。
  
• 2. 找到要插入的结点（肯定为叶子结点）。
  
• 3. 将key插入到结点中。
  
• 4. 判断当前结点是否满了，假如满了，则需要开始分裂，没满则结束。
  
• 5. 假如当前结点是根节点（没有父亲），则重新创建一个结点当根，并毗连好相应关系，假如不是根节点，则将当前结点的中位数看成key，要插入的结点酿成了当前结点的父亲，回到第三步。
  

1. bool Insert(const K& key)
2. {
3.         //1.如果是一颗空树，创建一个新结点即可。
4.         if (_root == nullptr)
5.         {
6.                 _root = new Node();
7.                 _root->_keys[0] = key;
8.                 _root->_size++;
10.                 return true;
11.         }
13.         //2.每次插入都是往叶子结点插入，所以先找到要插入的叶子结点。
14.         pair<Node*, int> ret = Find(key);
15.         if (ret.second >= 0)
16.         {
17.                 //找到了一个值为key的结点，不需要再插入了（当前B树不支持插入重复值）
18.                 return false;
19.         }
21.         //3.将key插入结点中
22.         //ret顺便将key应该插入的结点带回来了，我们直接将key插入该结点即可
23.         Node* cur = ret.first;
24.         K insertKey = key;
25.         Node* insertChild = nullptr;
26.         InsertKey(cur, insertKey, insertChild);
28.         return true;
29. }

复制代码

上面的代码已经完成了前三步的动作了，而第二步和第三步中的Find和InsertKey的函数我们还需要手动实现一下。

1. //返回一个pair，第一个参数是要查找的那个结点，第二个参数是要查找的位置下标，为-1表示查找失败。
2. pair<Node*, int> Find(const K& key)
3. {
4.         Node* cur = _root;
5.         Node* parent = nullptr;
6.         while (cur != nullptr)
7.         {
8.                 size_t i = 0;
9.                 parent = cur;
10.                 while (i < cur->_size)
11.                 {
12.                         if (cur->_keys[i] > key)       //向当前结点的孩子去查找
13.                         {
14.                                 break;
15.                         }
16.                         else if (cur->_keys[i] < key)  //比当前值大，继续向后查找
17.                         {
18.                                 i++;
19.                         }
20.                         else
21.                         {
22.                                 return make_pair(cur, i);  //查找成功，返回结果
23.                         }
24.                 }
25.                 cur = cur->_childs[i]; //向当前结点的孩子去查找。
26.         }
28.         //查找失败，不存在值为key的结点，我们将parent返回，为了方便以后将key插入parent
29.         return make_pair(parent, -1);
30. }

复制代码

首先是Find函数，以下图为例：

现在我们需要找到36要插入的结点，cur指向的就是最上面那个结点，从左向右判断，发现36比75小，那么就进入75对应下标的childs，也就是childs[0]，cur指向了右下角那个结点，再次从左往右判断，发现比49小，于是进入49对应下标的childs，也就是childs[0]，此时cur是nullptr，循环结束，我们此时需要返回cur的parent，也就是左下角的结点，这个结点也就是将来36要插入的结点。

1. void InsertKey(Node* cur, const K& key, Node* child)
2. {
3.         auto& childs  = cur->_childs;
4.         auto& keys = cur->_keys;
5.         size_t size = cur->_size - 1;
7.         while (size >= 0)
8.         {
9.                 if (keys[size] > key)
10.                 {
11.                         //将keys[size+1]和childs[size+2]向后移动，为了给key和child提供位置。
12.                         keys[size + 1] = keys[size];
13.                         childs[size + 2] = childs[size + 1];
14.                 }
15.                 else
16.                 {
17.                         break;
18.                 }
20.                 size--;
22.         }
24.         //将key和child插入进cur->_keys和cur->_childs中去。
25.         keys[size + 1] = key;
26.         childs[size + 2] = child;
28.         //不要忘记修改孩子的父亲
29.         if (child)
30.                 child->_parent = cur;
32.         //新插入了一个key，所以size要加1
33.         cur->_size++;
34. }

复制代码

将一个值和孩子插入一个结点，我们使用的是直接插入排序，如下图所示。

需要留意的是，不仅仅需要插入key，而且还需要插入child，由于B树的性质就是key永远比child少一个，也不要忘记插入结点的父亲指针需要改变。
现在我们可以开始实现第4和第5步了：

• 4. 判断当前结点是否满了，假如满了，则需要开始分裂，没满则结束。
  
• 5. 假如当前结点是根节点（没有父亲），则重新创建一个结点当根，并毗连好相应关系，假如不是根节点，则将当前结点的中位数看成key，要插入的结点酿成了当前结点的父亲，回到第三步。
  

1. bool Insert(const K& key)
2. {
3.         //1.如果是一颗空树，创建一个新结点即可。
4.         if (_root == nullptr)
5.         {
6.                 _root = new Node();
7.                 _root->_keys[0] = key;
8.                 _root->_size++;
10.                 return true;
11.         }
13.         //2.每次插入都是往叶子结点插入，所以先找到要插入的叶子结点。
14.         pair<Node*, int> ret = Find(key);
15.         if (ret.second >= 0)
16.         {
17.                 //找到了一个值为key的结点，不需要再插入了（当前B树不支持插入重复值）
18.                 return false;
19.         }
21.         //3.将key插入结点中
22.         //ret顺便将key应该插入的结点带回来了，我们直接将key插入该结点即可
23.         Node* cur = ret.first;
24.         K insertKey = key;
25.         Node* insertChild = nullptr;
27.         InsertKey(cur, insertKey, insertChild);
29.         4.如果没满就退出，满了就需要分裂
30.         if (cur->_size < M)
31.         {
32.                 break;
33.         }
34.         else
35.         {
36.                 //创建兄弟结点，拷贝一半的值给兄弟。
37.                 Node* brother = new Node;
38.                 size_t mid = cur->_size / 2;
39.                 size_t k = 0;
40.                 for (size_t i = mid + 1; i < cur->_size; i++)
41.                 {
42.                         brother->_keys[k] = cur->_keys[i];       //将关键字拷贝给兄弟
43.                         brother->_childs[k] = cur->_childs[i];   //将孩子拷给兄弟
44.                         if (cur->_childs[i])
45.                                 cur->_childs[i]->_parent = brother;  //将孩子的父亲改成兄弟
46.                         k++;
48.                         cur->_keys[i] = K();       //设置为默认值，方便观察
49.                         cur->_childs[i] = nullptr;
50.                 }
51.                 brother->_childs[k] = cur->_childs[cur->_size];  //将最后一个孩子拷给兄弟
52.                 if (cur->_childs[cur->_size])
53.                         cur->_childs[cur->_size]->_parent = brother; //将孩子的父亲改成兄弟。
54.                 cur->_childs[cur->_size] = nullptr;
55.                 brother->_size += k;  //更改兄弟结点的关键字个数
56.                 cur->_size -= k;   //当前结点的关键字数要减去拷贝给兄弟的。
58.                 size_t midKey = cur->_keys[mid];  //将中位数保存起来
59.                 cur->_keys[mid] = K();
60.                 cur->_size--;      //当前结点的关键字数还要减去拷贝给父亲的。
61.         }
63.         return true;
64. }

复制代码

先来看第四步，第四步是要将一半的结点拷贝给兄弟，代码如上图所示，为了方便观察，我们将拷贝过的值设置为默认值。留意的是，B树的指针错综复杂，需要非常小心，否则很容易堕落。
如何实现第五步，第五步的思想是将父结点看成一个新节点，也就是有了循环的思想，所以我们可以将3-5步放到一个循环中去。

1. bool Insert(const K& key)
2. {
3.         //1.如果是一颗空树，创建一个新结点即可。
4.         if (_root == nullptr)
5.         {
6.                 _root = new Node();
7.                 _root->_keys[0] = key;
8.                 _root->_size++;
10.                 return true;
11.         }
13.         //2.每次插入都是往叶子结点插入，所以先找到要插入的叶子结点。
14.         pair<Node*, int> ret = Find(key);
15.         if (ret.second >= 0)
16.         {
17.                 //找到了一个值为key的结点，不需要再插入了（当前B树不支持插入重复值）
18.                 return false;
19.         }
21.         //3.将key插入结点中
22.         //ret顺便将key应该插入的结点带回来了，我们直接将key插入该结点即可
23.         Node* cur = ret.first;
24.         K insertKey = key;
25.         Node* insertChild = nullptr;
27.         while (1)
28.         {
29.                 InsertKey(cur, insertKey, insertChild);
31.                 4.如果没满就退出，满了就需要分裂
32.                 if (cur->_size < M)
33.                 {
34.                         break;
35.                 }
36.                 else
37.                 {
38.                         //创建兄弟结点，拷贝一半的值给兄弟。
39.                         Node* brother = new Node;
40.                         size_t mid = cur->_size / 2;
41.                         size_t k = 0;
42.                         for (size_t i = mid + 1; i < cur->_size; i++)
43.                         {
44.                                 brother->_keys[k] = cur->_keys[i];       //将关键字拷贝给兄弟
45.                                 brother->_childs[k] = cur->_childs[i];   //将孩子拷给兄弟
46.                                 if (cur->_childs[i])
47.                                         cur->_childs[i]->_parent = brother;  //将孩子的父亲改成兄弟
48.                                 k++;
50.                                 cur->_keys[i] = K();       //设置为默认值，方便观察
51.                                 cur->_childs[i] = nullptr;
52.                         }
53.                         brother->_childs[k] = cur->_childs[cur->_size];  //将最后一个孩子拷给兄弟
54.                         if (cur->_childs[cur->_size])
55.                                 cur->_childs[cur->_size]->_parent = brother; //将孩子的父亲改成兄弟。
56.                         cur->_childs[cur->_size] = nullptr;
57.                         brother->_size += k;  //更改兄弟结点的关键字个数
58.                         cur->_size -= k;   //当前结点的关键字数要减去拷贝给兄弟的。
60.                         size_t midKey = cur->_keys[mid];  //将中位数保存起来
61.                         cur->_keys[mid] = K();
62.                         cur->_size--;      //当前结点的关键字数还要减去拷贝给父亲的。
65.                         //5.如果当前结点是根节点，则需要重新创建一个根。
66.                         //  如果当前结点不是根结点，则直接将当前结点当作新结点即可。
67.                         if (cur->_parent == nullptr)
68.                         {
69.                                 _root = new Node;
70.                                 _root->_keys[0] = midKey;
71.                                 _root->_childs[0] = cur;
72.                                 _root->_childs[1] = brother;
73.                                 cur->_parent = _root;
74.                                 brother->_parent = _root;
75.                                 _root->_size = 1;
77.                                 break;
78.                         }
79.                         else
80.                         {
81.                                 insertKey = midKey;
82.                                 insertChild = brother;
83.                                 cur = cur->_parent;
84.                         }
85.                 }
86.         }
88.         return true;
89. }

复制代码

4.4 B树的简单验证

到这里B树的插入过程的代码就写完了，我们可以做一个简单的验证，和前面的例子一样{ 53, 139, 75, 49, 145, 36, 101 }，将这组数插入到树中去，最终判断结果是否和我们分析的一样。

经过调试，可以看到结果是正确的：

这样大概不太方便观察，我在这里转换。

可以看到最终的结果是正确的，我们也可以使用前序遍历，假如结果是有序的阐明应该没什么大问题。

1. void InOrder()
2. {
3.         _InOrder(_root);
4. }
6. void _InOrder(Node* root)
7. {
8.         if (root == nullptr)
9.                 return;
11.         size_t i = 0;
12.         for (i = 0; i < root->_size; i++)
13.         {
14.                 _InOrder(root->_childs[i]);
15.                 cout << root->_keys[i] << " ";
16.         }
17.         _InOrder(root->_childs[i]);
18. }

复制代码

遍历结果：

4.5 B树的性能分析

B-树的服从是很高的
对于一棵节点为N度为M的B树，查找和插入需要log(M-1)N ~ log(M/2)N次比较，这个很好证明：对于度为M的B树，每一个节点的子节点个数为M/2 ~(M-1)之间，因此树的高度应该在要$log{M-1}N$和$log{M/2}N$之间，在定位到该节点后，再采用二分查找的方式可以很快的定位到该元素。
对于N = 62*1000000000个节点，假如度M为1024，则log{M/2}N <= 4，即在620亿个元素中，假如这棵树的度为1024，则需要小于4次即可定位到该节点，然后使用二分查找可以快速定位到该元素，大大减少了读取磁盘的次数

4.6 团体代码

1. #pragma once
3. #include <iostream>
4. #include <vector>
6. using namespace std;
8. //K是数据类型，M是树的路数，将来就是M叉树
9. template<class K, size_t M>
10. struct BTreeNode
11. {
12.         BTreeNode()
13.         {
14.                 for (size_t i = 0; i < M; i++)
15.                 {
16.                         _keys[i] = K();
17.                         _childs[i] = nullptr;
18.                 }
19.                 _childs[M] = nullptr;
20.                 _parent = nullptr;
21.                 _size = 0;
22.         }
24.         //为了方便写代码，所以关键字和孩子指针我们都多开了一个空间。
25.         K _keys[M];  //关键字
26.         BTreeNode<K, M>* _childs[M + 1]; //孩子指针
27.         BTreeNode<K, M>* _parent;        //父亲指针
28.         size_t _size; //实际存储的个数
29. };
31. //K是数据类型，M是树的路数，将来就是M叉树
32. template<class K, size_t M>
33. class BTree
34. {
35.         typedef BTreeNode<K, M> Node;
36. public:
37.         BTree()
38.                 : _root(nullptr)
39.         {}
41.         //返回一个pair，第一个参数是要查找的那个结点，第二个参数是要查找的位置下标，为-1表示查找失败。
42.         pair<Node*, int> Find(const K& key)
43.         {
44.                 Node* cur = _root;
45.                 Node* parent = nullptr;
46.                 while (cur != nullptr)
47.                 {
48.                         size_t i = 0;
49.                         parent = cur;
50.                         while (i < cur->_size)
51.                         {
52.                                 if (cur->_keys[i] > key)       //向当前结点的孩子去查找
53.                                 {
54.                                         break;
55.                                 }
56.                                 else if (cur->_keys[i] < key)  //比当前值大，继续向后查找
57.                                 {
58.                                         i++;
59.                                 }
60.                                 else
61.                                 {
62.                                         return make_pair(cur, i);  //查找成功，返回结果
63.                                 }
64.                         }
65.                         cur = cur->_childs[i]; //向当前结点的孩子去查找。
66.                 }
68.                 //查找失败，不存在值为key的结点，我们将parent返回，为了方便以后将key插入parent
69.                 return make_pair(parent, -1);
70.         }
72.         void InsertKey(Node* cur, const K& key, Node* child)
73.         {
74.                 auto& childs  = cur->_childs;
75.                 auto& keys = cur->_keys;
76.                 size_t size = cur->_size - 1;
78.                 while (size >= 0)
79.                 {
80.                         if (keys[size] > key)
81.                         {
82.                                 //将keys[size+1]和childs[size+2]向后移动，为了给key和child提供位置。
83.                                 keys[size + 1] = keys[size];
84.                                 childs[size + 2] = childs[size + 1];
85.                         }
86.                         else
87.                         {
88.                                 break;
89.                         }
91.                         size--;
93.                 }
95.                 //将key和child插入进cur->_keys和cur->_childs中去。
96.                 keys[size + 1] = key;
97.                 childs[size + 2] = child;
99.                 //不要忘记修改孩子的父亲
100.                 if (child)
101.                         child->_parent = cur;
103.                 //新插入了一个key，所以size要加1
104.                 cur->_size++;
105.         }
107.         bool Insert(const K& key)
108.         {
109.                 //1.如果是一颗空树，创建一个新结点即可。
110.                 if (_root == nullptr)
111.                 {
112.                         _root = new Node();
113.                         _root->_keys[0] = key;
114.                         _root->_size++;
116.                         return true;
117.                 }
119.                 //2.每次插入都是往叶子结点插入，所以先找到要插入的叶子结点。
120.                 pair<Node*, int> ret = Find(key);
121.                 if (ret.second >= 0)
122.                 {
123.                         //找到了一个值为key的结点，不需要再插入了（当前B树不支持插入重复值）
124.                         return false;
125.                 }
127.                 //3.将key插入结点中
128.                 //ret顺便将key应该插入的结点带回来了，我们直接将key插入该结点即可
129.                 Node* cur = ret.first;
130.                 K insertKey = key;
131.                 Node* insertChild = nullptr;
133.                 while (1)
134.                 {
135.                         InsertKey(cur, insertKey, insertChild);
137.                         4.如果没满就退出，满了就需要分裂
138.                         if (cur->_size < M)
139.                         {
140.                                 break;
141.                         }
142.                         else
143.                         {
144.                                 //创建兄弟结点，拷贝一半的值给兄弟。
145.                                 Node* brother = new Node;
146.                                 size_t mid = cur->_size / 2;
147.                                 size_t k = 0;
148.                                 for (size_t i = mid + 1; i < cur->_size; i++)
149.                                 {
150.                                         brother->_keys[k] = cur->_keys[i];       //将关键字拷贝给兄弟
151.                                         brother->_childs[k] = cur->_childs[i];   //将孩子拷给兄弟
152.                                         if (cur->_childs[i])
153.                                                 cur->_childs[i]->_parent = brother;  //将孩子的父亲改成兄弟
154.                                         k++;
156.                                         cur->_keys[i] = K();       //设置为默认值，方便观察
157.                                         cur->_childs[i] = nullptr;
158.                                 }
159.                                 brother->_childs[k] = cur->_childs[cur->_size];  //将最后一个孩子拷给兄弟
160.                                 if (cur->_childs[cur->_size])
161.                                         cur->_childs[cur->_size]->_parent = brother; //将孩子的父亲改成兄弟。
162.                                 cur->_childs[cur->_size] = nullptr;
163.                                 brother->_size += k;  //更改兄弟结点的关键字个数
164.                                 cur->_size -= k;   //当前结点的关键字数要减去拷贝给兄弟的。
166.                                 size_t midKey = cur->_keys[mid];  //将中位数保存起来
167.                                 cur->_keys[mid] = K();
168.                                 cur->_size--;      //当前结点的关键字数还要减去拷贝给父亲的。
171.                                 //5.如果当前结点是根节点，则需要重新创建一个根。
172.                                 //  如果当前结点不是根结点，则直接将当前结点当作新结点即可。
173.                                 if (cur->_parent == nullptr)
174.                                 {
175.                                         _root = new Node;
176.                                         _root->_keys[0] = midKey;
177.                                         _root->_childs[0] = cur;
178.                                         _root->_childs[1] = brother;
179.                                         cur->_parent = _root;
180.                                         brother->_parent = _root;
181.                                         _root->_size = 1;
183.                                         break;
184.                                 }
185.                                 else
186.                                 {
187.                                         insertKey = midKey;
188.                                         insertChild = brother;
189.                                         cur = cur->_parent;
190.                                 }
191.                         }
192.                 }
194.                 return true;
195.         }
197.         void InOrder()
198.         {
199.                 _InOrder(_root);
200.         }
202.         void _InOrder(Node* root)
203.         {
204.                 if (root == nullptr)
205.                         return;
207.                 size_t i = 0;
208.                 for (i = 0; i < root->_size; i++)
209.                 {
210.                         _InOrder(root->_childs[i]);
211.                         cout << root->_keys[i] << " ";
212.                 }
213.                 _InOrder(root->_childs[i]);
214.         }
216. private:
217.         Node* _root;
218. };

复制代码

5. B+树和B*树

5.1 B+树

B+树是B树的变形，是在B树底子上优化的多路平衡搜索树，B+树的规则跟B树根本类似，但是又在B树的底子上做了以下几点改进优化：

• 1. 分支节点的子树指针与关键字个数雷同
  
• 2. 分支节点的子树指针p指向关键字值巨细在[k，k[i+1])区间之间
  
• 3. 全部叶子节点增长一个链接指针链接在一起
  
• 4. 全部关键字及其映射数据都在叶子节点出现
  
• 5.分支结点存放的是叶子结点的索引
  
• 6.父亲用孩子的最小关键字来做索引的
  

B+树的特性：

• 1. 全部关键字都出现在叶子节点的链表中，且链表中的节点都是有序的。
  
• 2. 不大概在分支节点中掷中。
  
• 3. 分支节点相当于是叶子节点的索引，叶子节点才是存储数据的数据层。
  

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


5.2 B*树

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

B*树的分裂：
当一个结点满时，假如它的下一个兄弟结点未满，那么将一部门数据移到兄弟结点中，再在原结点插入关键字，最后修改父结点中兄弟结点的关键字（由于兄弟结点的关键字范围改变了）；假如兄弟也满了，则在原结点与兄弟结点之间增长新结点，并各复制1/3的数据到新结点，最后在父结点增长新结点的指针。
所以，B*树分配新结点的概率比B+树要低，空间使用率更高；

5.3 总结

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

单论树的高度，查找服从来看B树系列确实不错，但是也存在一些缺点。

• 1.空间使用率低，占用的空间大。
  
• 2.插入和删除数据时，需要进行分裂，涉及到数据的挪动，服从低。
  
• 3.虽然比起红黑树等，高度更低，但是在内存中都是一个量级的，搜索服从并不比红黑树快多少（在内存中没什么上风）
  

6. B树的应用

6.1 索引

B树最常见的应用就是用来做索引。索引通俗的说就是为了方便用户快速找到所寻之物，好比：书籍目次可以让读者快速找到干系信息，hao123网页导航网站，为了让用户可以或许快速的找到有代价的分类网站，本质上就是互联网页面中的索引结构。
MySQL官方对索引的界说为：索引(index)是帮助MySQL高效获取数据的数据结构，简单来说：索引就是数据结构。
当数据量很大时，为了可以或许方便管理数据，提高数据查询的服从，一般都会选择将数据保存到数据库，因此数据库不仅仅是帮助用户管理数据，而且数据库系统还维护着满足特定查找算法的数据结构，这些数据结构以某种方式引用数据，这样就可以在这些数据结构上实现高级查找算法，该数据结构就是索引。

6.2 MySQL索引

mysql是现在非常流行的开源关系型数据库，不仅是免费的，可靠性高，速度也比较快，而且拥有灵活的插件式存储引擎，如下：

MySQL中索引属于存储引擎级别的概念，不同存储引擎对索引的实现方式是不同的。
 
6.2.1 MyISAM

MyISAM引擎是MySQL5.5.8版本之前默认的存储引擎，不支持事物，支持全文检索，使用B+Tree作为索引结构，叶节点的data域存放的是数据记录的地址，其结构如下：

上图是以以Col1为主键，MyISAM的示意图，可以看出MyISAM的索引文件仅仅保存数据记录的地址。在MyISAM中，主索引和辅助索引（Secondary key）在结构上没有任何区别，只是主索引要求key是唯一的，而辅助索引的key可以重复。假如想在Col2上建立一个辅助索引，则此索引的结构如下图所示：

同样也是一棵B+Tree，data域保存数据记录的地址。因此，MyISAM中索引检索的算法为首先按照B+Tree搜索算法搜索索引，假如指定的Key存在，则取出其data域的值，然后以data域的值为地址，读取相应数据记录。MyISAM的索引方式也叫做“非聚集索引”的。


6.2.2 InnoDB

InnoDB存储引擎支持事务，其计划目标重要面向在线事务处理的应用，从MySQL数据库5.5.8版本开始，InnoDB存储引擎是默认的存储引擎。InnoDB支持B+树索引、全文索引、哈希索引。但InnoDB使用B+Tree作为索引结构时，具体实现方式却与MyISAM大相径庭。
第一个区别是InnoDB的数据文件本身就是索引文件。MyISAM索引文件和数据文件是分离的，索引文件仅保存数据记录的地址。而InnoDB索引，表数据文件本身就是按B+Tree构造的一个索引结构，这棵树的叶节点data域保存了完备的数据记录。这个索引的key是数据表的主键，因此InnoDB表数据文件本身就是主索引。

图是InnoDB主索引（同时也是数据文件）的示意图，可以看到叶节点包罗了完备的数据记录，这种索引叫做聚集索引。由于InnoDB的数据文件本身要按主键聚集，所以InnoDB要求表必须有主键（MyISAM可以没有），假如没有显式指定，则MySQL系统会主动选择一个可以唯一标识数据记录的列作为主键，假如不存在这种列，则MySQL主动为InnoDB表生成一个隐含字段作为主键，这个字段长度为6个字节，类型为长整型。
第二个区别是InnoDB的辅助索引data域存储相应记录主键的值而不是地址,全部辅助索引都引用主键作为data域。

聚集索引这种实现方式使得按主键的搜索非常高效，但是辅助索引搜索需要检索两遍索引：首先检索辅助索引得到主键，然后用主键到主索引中检索得到记录。
 

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。