B-Tree，B树原理及C++代码实现
B树是一种平衡搜索树，它可以看做是2-3Tree和2-3-4Tree的一种推广。CLRS上介绍了B树目前主要针对磁盘等直接存取的辅存设备，许多数据库系统也利用B树或B树的变种来存储信息。
本文主要针对代码实现作一些讲解。如果对B树性质或特点不了解的，请对照B树的定义来阅读本文。或先了解B树的定义，对定义了然于胸后，可以更好地把注意力放在逻辑实现上。
本文实现思路来自于CLRS，但书中只给出了search和insert的伪代码，和delete的思路，所以本文的实现细节都是自己想出来的，比较晦涩冗杂。（我自己都不能一下子看懂），所以特别针对自己深有体会的部分加以讲述。
开始。
#include <iostream>
#include <vector>
#include <utility>
using namespace std;
class BTree {
private :
struct Node {
//int n; //the number of the keys in this node
vector<int> key; //key.size() return n
vector<Node*> pToChild; //the pointer to the children,p.empty() return isLeaf
//bool isLeaf;
};
using PlaceOfChild = pair<Node*, int>;
private :
Node * root;
int t; //the minimum degree, more than or equal to 2
private :
void SplitChild(Node * x, const int i);
void Insert_notfull(Node * x, const int k);
PlaceOfChild search(Node * p, const int k);
PlaceOfChild predecessor(Node * x, int i);
PlaceOfChild successor(Node * x, int i);
Node * minimum(Node * p);
Node * maximum(Node * p);
void combine(Node * x, Node * y, PlaceOfChild z);
void remove(Node * x, const int k);
void inorderWalk(Node * p);
public :
BTree(int deg) : root(new Node), t(deg >= 2 ? deg : 2) {}
~BTree() {delete root;}
void insert(const int k);
void remove(const int k) {remove(root, k);}
bool search(const int k) {return (search(root, k).first ? true : false);}
int minimum() {return minimum(root)->key[0];} //can't be empty
int maximum() {return *(maximum(root)->key.end() - 1);} //can't be empty
void inorderWalk() {inorderWalk(root);}
};BTree类的定义如上，因为使用了pair记录结点关键值的准确位置，所以需要包含头文件<utility>，Btree的数据成员包含指向根结点的指针root和最小度数t，对B树最小度数不了解的一定要先看看它的定义，Btree的很多性质都与最小度数有关。
结点的数据成员包括两个vector，第一个用来存储关键字，第二个用来存储指向孩子结点的指针。书上给的实现还包括了两个bool值，一个是标识该结点是否为叶子结点，另一个记录结点key值的个数。因为我使用vector保存数据，所以直接可以用vector.size()和vector.empty()来判断是否是叶子和key的个数，但也因此导致代码比较复杂。另外我推荐大家自己实现的时候维护一个指向父结点的指针，后面实现删除的时候有指向父结点的指针就会更简单实现一些。
实现过程中值得注意的点和难点：
1.任何时候使用pToChild，一定要先检查结点是否为叶子结点，即先判断pToChild.empty()。
2.combine和split的时候，该pop的元素一定要记得pop。因为使用的是vector而不是固定数组，所以vector元素个数一定要保证绝对正确。
3.因为没有设置parent指针，所以找前驱和后继的时候使用stack来记录沿途的结点，这也是常用的手法。
4.remove的情况太过复杂，写的时候一定把每种情况都先写下来，再写代码，不然debug的时候就很难受了。
5.只有根结点的合并和分裂才会导致B树高度的变化。
6.删除的时候会保证经过的结点key值个数最小为t（除了root），所以不必担心叶子结点被删除某一个key后，key的个数小于t-1。
7.删除的时候，combine的过程中一定要递归删除而不是直接从内部结点中直接删除（当初我纠结了好久），因为直接从内部删除结点会导致下一层结点，即combine最后留下的结点有两个指针没有关键字分割。
8.删除的时候，如果是使用前驱（后继）替换需要删除的结点的情况，再递归删除的时候也一定要一层一层地递归，而不是直接对前驱（后继）所在的结点递归。因为需要一层一层的递归来保证删除函数的前提（删除函数访问的结点的key值个数最小为t，除了根结点）被满足。
9.自己动手模拟了100个结点的insert和remove过程，而且还模拟了好几遍。（因为不得不debug...）到最后对各种情况基本上可以胸有成竹了。建议有耐心的小伙伴也试试自己模拟构建B树，一定会有更深地领悟。
代码如下：（仅供参考）
1 //if child is full and the parent is not full, split the child.
2 void BTree::SplitChild(Node * x, const int i) { //O(t)
3 Node * y = x->pToChild[i];
4 Node * z = new Node;
5
6 for (int j = 0; j < t - 1; ++j) //right half side of key
7 z->key.push_back(y->key[j+t]);
8
9 if (!y->pToChild.empty()) {//y is not a leaf
10 for (int j = 0; j < t; ++j) //right half side of pointer
11 z->pToChild.push_back(y->pToChild[j+t]);
12 for (int j = 0; j < t; ++j)
13 y->pToChild.pop_back();
14 }
15
16 x->key.insert(x->key.begin() + i, y->key[t-1]);
17 x->pToChild.insert(x->pToChild.begin() + i + 1, z);
18 for (int j = 0; j < t; ++j)
19 y->key.pop_back();
20 }
21
22 void BTree::Insert_notfull(Node * x, const int k) {
23 int i = x->key.size() - 1;
24 while (i >= 0 && k < x->key[i]) //find insertion place
25 --i;
26 if (x->pToChild.empty()) {
27 x->key.insert(x->key.begin() + i + 1, k);
28 }
29 else {
30 ++i;
31 if (x->pToChild[i]->key.size() == 2 * t - 1) {
32 SplitChild(x, i);
33 if (k >= x->key[i])
34 ++i;
35 }
36 Insert_notfull(x->pToChild[i], k);
37 }
38 }
39
40 void BTree::insert(const int k) { //O(t*(logn to t))
41 Node * r = root;
42 if (r->key.size() == 2 * t - 1) { //root is full
43 Node * s = new Node;
44 root = s;
45 s->pToChild.push_back(r);
46 SplitChild(s, 0);
47 Insert_notfull(s, k);
48 }
49 else
50 Insert_notfull(r, k);
51 }
52
53 BTree::PlaceOfChild BTree::search(Node * p, const int k) {
54 int i = 0;
55 while (i < p->key.size() && k > p->key[i])
56 ++i;
57 if (i < p->key.size() && k == p->key[i])
58 return make_pair(p, i);
59 else if (p->pToChild.empty())
60 return make_pair(nullptr, 0);
61 else
62 return search(p->pToChild[i], k);
63 }
64
65 BTree::Node * BTree::minimum(Node * p) {
66 while (!p->pToChild.empty())
67 p = p->pToChild[0];
68 return p;
69 }
70
71 BTree::Node * BTree::maximum(Node * p) {
72 while (!p->pToChild.empty())
73 p = p->pToChild[p->pToChild.size()-1];
74 return p;
75 }
76
77 BTree::PlaceOfChild BTree::predecessor(Node * x, int i) {
78 if (!x->pToChild.empty()) {
79 x = maximum(x->pToChild[i]);
80 return make_pair(x, x->key.size() - 1);
81 }
82 else if (i != 0) {
83 return make_pair(x, i - 1);
84 }
85 int key = x->key[i];
86 Node * y = root;
87 vector<PlaceOfChild> stk;
88 while (1) {
89 if (y->key[0] == key)
90 break;
91 for (i = 0; i < y->key.size() && key > y->key[i]; ++i)
92 ;
93 stk.push_back(make_pair(y, i));
94 y = y->pToChild[i];
95 }
96 PlaceOfChild p;
97 while (!stk.empty()) {
98 p = stk.back();
99 stk.pop_back();
100 if (p.second != 0)
101 return p;
102 }
103 return make_pair(nullptr, 0);
104 }
105
106 BTree::PlaceOfChild BTree::successor(Node * x, int i) {
107 if (!x->pToChild.empty()) {
108 x = minimum(x->pToChild[i+1]);
109 return make_pair(x, 0);
110 }
111 else if (i != x->key.size() - 1) {
112 return make_pair(x, i + 1);
113 }
114 int key = x->key[i];
115 Node * y = root;
116 vector<PlaceOfChild> stk;
117 while (1) {
118 if (y->key.back() == key)
119 break;
120 for (i = 0; i < y->key.size() && key > y->key[i]; ++i)
121 ;
122 stk.push_back(make_pair(y, i));
123 y = y->pToChild[i];
124 }
125 PlaceOfChild p;
126 while (!stk.empty()) {
127 p = stk.back();
128 stk.pop_back();
129 if (p.second != p.first->key.size())
130 return p;
131 }
132 return make_pair(nullptr, 0);
133 }
134
135 void BTree::combine(Node * x, Node * y, PlaceOfChild z) {
136 x->key.push_back(z.first->key[z.second]);
137 for (int i = 0; i < t - 1; ++i)
138 x->key.push_back(y->key[i]);
139 if (!x->pToChild.empty())
140 for (int i = 0; i < t; ++i) {
141 x->pToChild.push_back(y->pToChild[i]);
142 }
143 delete y;
144
145 z.first->key.erase(z.first->key.begin() + z.second);
146 z.first->pToChild.erase(z.first->pToChild.begin() + z.second + 1);
147 if (z.first->key.empty()) {
148 root = z.first->pToChild[z.second];
149 delete z.first;
150 }
151 }
152
153 void BTree::remove(Node * x, const int k) { //This function guarantees x->key.size() >= t,except root
154 int i = 0;
155 while (i < x->key.size() && x->key[i] < k)
156 ++i;
157 if (i < x->key.size() && x->key[i] == k) {
158 if (x->pToChild.empty())
159 x->key.erase(x->key.begin() + i);
160 else {
161 if (x->pToChild[i]->key.size() >= t) {
162 PlaceOfChild preOfk = predecessor(x, i);
163 x->key[i] = preOfk.first->key[preOfk.second];
164 remove(x->pToChild[i], x->key[i]); //recursive in the child ,not the successor
165 }
166 else if (x->pToChild[i+1]->key.size() >= t) {
167 PlaceOfChild sucOfk = successor(x, i);
168 x->key[i] = sucOfk.first->key[sucOfk.second];
169 remove(x->pToChild[i+1], x->key[i]); //recursive in the child ,not the successor
170 }
171 else {
172 combine(x->pToChild[i], x->pToChild[i+1], make_pair(x, i));
173 remove(x->pToChild[i], k);
174 }
175 }
176 }
177 else {
178 if (x->pToChild.empty())
179 return ;
180 else if (x->pToChild[i]->key.size() != t - 1)
181 remove(x->pToChild[i], k);
182 else {
183 Node *y, *z;
184 if (i > 0 && x->pToChild[i-1]->key.size() != t - 1) {
185 y = x->pToChild[i-1];
186 z = x->pToChild[i];
187 z->key.insert(z->key.begin(), x->key[i-1]);
188 if (!y->pToChild.empty()) {
189 z->pToChild.insert(z->pToChild.begin(), y->pToChild.back());
190 y->pToChild.pop_back();
191 }
192 x->key[i-1] = y->key.back();
193 y->key.pop_back();
194 remove(z, k);
195 }
196 else if (i < x->pToChild.size() - 1 && x->pToChild[i+1]->key.size() != t - 1){
197 y = x->pToChild[i+1];
198 z = x->pToChild[i];
199 z->key.push_back(x->key[i]);
200 if (!y->pToChild.empty()) {
201 z->pToChild.push_back(y->pToChild[0]);
202 y->pToChild.erase(y->pToChild.begin());
203 }
204 x->key[i] = y->key[0];
205 y->key.erase(y->key.begin());
206 remove(z, k);
207 }
208 else if (i > 0) {
209 y = x->pToChild[i-1];
210 z = x->pToChild[i];
211 combine(y, z, make_pair(x, i-1));
212 remove(y, k);
213 }
214 else if (i < x->pToChild.size() - 1) {
215 y = x->pToChild[i];
216 z = x->pToChild[i+1];
217 combine(y, z, make_pair(x, i));
218 remove(y, k);
219 }
220 }
221 }
222 }
223
224 void BTree::inorderWalk(Node * p) {
225 int i;
226 if (!p->pToChild.empty()) {
227 for (i = 0; i < p->key.size(); ++i) {
228 inorderWalk(p->pToChild[i]);
229 cout << p->key[i] << ' ';
230 }
231 inorderWalk(p->pToChild[i]);
232 }
233 else {
234 for (i = 0; i < p->key.size(); ++i)
235 cout << p->key[i] << ' ';
236 }
237 }