B-树

B-树是一种平衡的多路查找树，它在文件系统中很有用。一棵m阶B-树有如下性质

1. 树中每个结点至多有m棵子树，m-1一个关键字
2. 若根结点不是叶结点，则至少有两个子树
3. 除根之外的所有非终端结点至少有⌈m/2⌉（向上取整）棵子树
4. 所有非终端结点包含关键字、关键字数量和指向子树根结点的指针
5. 所有叶子结点都出现在同一层次上，且不带信息

---

B-树的插入

B-树的插入分为几个步骤

1. 首先，将新的关键字添加到B-树最底层的某个非终端结点，然后考察该结点的关键字个数，如果结点的关键字个数满足要求（即小于树的阶数）则插入完成，否则，进行分裂。
2. 在分裂的过程中，以中间位置的关键字为界，小于该关键字部分留在原来的结点中，大于该关键字的部分分裂到新的结点中，中间位置的关键字本身则插入到双亲结点中。
3. 如果双亲结点在插入关键字后关键字个数大于等于于树的阶数，则对双亲结点进行类似步骤2的操作。
4. 重复2、3步，直到B-树的所有结点满足要求。

B-树的删除

B-树的插入也分为几个步骤

1. 如果删除的关键字 $X$ 在非终端结点，则需要将相应子结点的最小关键字 $Y$ 替代被删除关键字 $X$，然后删除子结点里的关键字 $Y$。
2. 如果删除的关键在终端结点，直接删除该关键字，然后考察结点中的关键字数量是否满足B-树要求（除根之外的所有非终端结点至少有⌈m/2⌉-1（向上取整）个），如果不满足，需要进行合并操作。
3. 如果被删关键字所在的结点有左（右）兄弟结点，考察该兄弟结点的关键字个数，如果关键字个数大于 ⌈m/2⌉ 个，则将该兄弟结点中最大（小）的关键字上移到双亲结点中，然后将双亲中紧邻大（小）于上移关键字的关键字下移到删关键字所在的结点。
4. 如果被删关键字所在的结点左、右兄弟结点的关键字数量均等于⌈m/2⌉-1个，则将被删除关键字结点中剩余的关键字连同双亲节点中对应的关键字一同合并到左（右）兄弟节点中。如果双亲结点在失去了一个关键字后其关键字数量均小于⌈m/2⌉-1个，则对双亲节点做类似的处理。

第2步例子：删除53

第4步例子：删除37

B-树的查找

从根结点开始，对结点内的关键字进行查找，如果找到则结束，否则进入查询关键字所属范围的子树根结点，继续进行关键字的查找。如此重复，直到找到目标关键字或到达叶子结点。

B-树的查找包含两种操作，在B-树中找结点，在结点中找关键字。如果B-树存储在磁盘上，那么找结点的过程在磁盘上进行，而找关键字的过程在内存中进行。磁盘上查找会耗费大量时间，而磁盘上的查找次数取决于待查关键字在B-树上的层次数。

总的来说，在含有 $n$ 个关键字的B-树上进行查找时，经过的结点数不超过 $lo{g}_{\lceil m/2\rceil }(\frac{n+1}{2}+1)$，其中，m为树的阶数，m/2计算时进行向上取整。

B+树

（感觉看了好多文章都各有不同，下面以个人的理解加以总结）

B+树属于B-树的一种变型树，一棵m阶的B+树有如下性质：

1. 根结点至少有两个子女。
2. 非终端结点至少包含⌈m/2⌉个子树，最多包含m个子树，且每个结点的关键字个数与子树的个数相等
3. 所有叶子结点处于同一层且全部关键字信息存储在叶子结点里，每个叶子结点至少包含⌈m/2⌉个元素，不超过m个元素，且叶子结点按自小到大顺序链接
4. 所有非终端结点是叶子结点的索引，结点中包含子树根节点中最大（小）的关键字

---

B+树的查找、插入和删除与B-树有相似之处

B+树的插入

B+树的在叶子结点上进行插入，当叶子结点的关键字数量超过树阶数时将节点分裂成两个，同时令它们的双亲结点包含两个节点中的最大关键字。如果双亲结点的关键字数量超过阶数则继续进行分裂，以此类推直到B+树中的所有节点满足要求。

B+树的删除

B+在叶子结点进行删除，如果删除关键字后叶子结点不满足B+树要求，则进行进一步处理，分为两种情况：

1. 如果被删关键字所在的结点有左（右）兄弟结点，考察该兄弟结点的关键字个数，如果关键字个数大于 ⌈m/2⌉ 个，则将该兄弟结点中最大（小）的关键字转移到删关键字所在的结点，同时修改双亲节点中用于索引的关键字。
2. 如果被删关键字所在的结点左、右兄弟结点的关键字数量均等于⌈m/2⌉个，则将被删除关键字结点中剩余的关键字合并到左（右）兄弟节点中。此时双亲结点中失去了一个关键字，如果双亲结点的关键字数量因此均小于⌈m/2⌉个，则对双亲节点做类似的处理。

B+树的查找

B+树有两种查找方式，因为叶子结点按顺序链接，所以可以直接对叶子结点中的关键字进行顺序查找。
另一种查找方式类似B-树的查找，从根节点开始，自上而下，一直找到叶子结点。注意是一直查找到叶子结点，不论成功与否每次都走一条从根到叶子结点的路径。

键树

键树又称数字查找树或字符树，树中的结点是组成关键字中的单个字符。树的根结点不存储任何字符，根节点的下一层结点存储第一个字符，再下一层存储第二个字符，以此类推。最后，每个字符串以符号 $ 作为结束符。把从根到叶子的路径上所有的节点连起来便是要找的关键字。

为了方便查找和插入，约定键树是有序树，即同一层中兄弟结点之间所含符号自左到右有序，并约定结束符 $ 小于任何字符。

键树的存储可以有两种方式：双链树和多重链表

---

使用双链树表示键树

如果使用双链树来表示键树，则树的结构如下图所示。其中，每个结点包含三个域，存储关键字字符的符号域，存储第一课子树的指针，还有存储右兄弟的指针。

键树的创建和删除

使用双链表实现的键树插入和删除关键字相当于在某一个节点插入或删除一个子树。
由于关键字可能有相同的开头，所以在插入和删除的时候都要注意，插入式不要重复插入这些重复部分，同样删除时不要删除这些部分。

键树的查找

双链树的查找从根节点开始，順指向子树根节点的指针到达第一课子树的根节点，令子树根节点符号域存储的字符与关键字的第一个字符进行比较。如果相同沿存储第一课子树的指针继续查找，如果不相同沿指向兄弟节点的指针继续查找。直到遇到空指针或叶子结点，查找结束。

使用多重链表表示键树

如果使用多重链表来表示键树此时键树又称为Trie树，则树的结构如下图所示。值得注意的是如果从键树的某个结点到叶子结点的路径上的每个结点都只有一个孩子，则将这条路径上的所有结点汇总到一个叶子结点，并用该叶子结点代替路径中的所有节点。

键树的查找

以多重链表表示的键树查找非常简单，从根结点出发，也相应的字符逐层向下就行了。
键树的查找时间依赖于它的深度，我们可以对关键字选择一种合适的分隔以减少树的深度，即我们可以不按顺序对关键字中的字符进行选择，如第一层仍以首字符分隔，第二程以最后一个字符分割，第三层以第二个字符分割…

另外还可限制树的深度，当结点到达某个深度后不再划分子树，而是把剩下的所有字符都存入叶子结点。

通常情况下，如果键树中结点的度较大，采用Tire树相对双链树更为合适。

（本文完）

---

B-树的C++代码实现
（包括搜索和插入，未经优化，仅用于个人纪录）

#define DEGREE 3
struct B_Tree {int data[DEGREE];int keynum;B_Tree* parent;B_Tree* children[DEGREE+1];B_Tree() :keynum(0) {for (int i = 0; i < DEGREE+1; i++) {if(i<DEGREE)data[i] = 0x3f3f3f3f;children[i] = NULL;}parent = NULL;};~B_Tree() {for (int i = 0; i < DEGREE+1; i++) {if(children[i]!=NULL)delete children[i];}}
};
bool Search(B_Tree* tree, int value, B_Tree** targetNode = NULL, int* order = NULL);
void Insert(B_Tree** tree, int value);
void InsertValueToNode(B_Tree* node, int order, int value, B_Tree* child);
void InsertDivision(B_Tree* targetNode, B_Tree** tree);bool Search(B_Tree* tree, int value, B_Tree** targetNode,int* order) {B_Tree* node = tree;while (node!=NULL){*order = 0;for (int i = 0; i < DEGREE; i++) {if (order != NULL)*order = i;if (i < DEGREE - 1) {if (node->data[i] == value) {if (targetNode != NULL)*targetNode = node;	return true;}if (node->data[i] > value) {if (targetNode != NULL)*targetNode = node;node = node->children[i];break;}}else {if (targetNode != NULL)*targetNode = node;node = node->children[i];}}}return false;
}void Insert(B_Tree** tree, int value) {B_Tree* node = NULL;B_Tree** pointToNode = &node;int order = 0;if(!Search(*tree, value, pointToNode,&order)){InsertValueToNode(node, order, value,NULL);//在叶子结点上插入一个值InsertDivision(node,tree);}else {cout << "结点已插入" << endl;}
}void InsertValueToNode(B_Tree* node,int order,int value, B_Tree* child) {//需要交换for (int i = DEGREE - 1; i > order; i--) {node->data[i] = node->data[i - 1];node->children[i+1] = node->children[i];}node->data[order] = value;node->children[order+1] = child;node->keynum++;
}void InsertDivision(B_Tree* targetNode, B_Tree** tree) {B_Tree* node = targetNode;while (node->keynum>=DEGREE){B_Tree* newnode = new B_Tree();int ind = DEGREE / 2;for (int i = ind + 1; i < DEGREE+1; i++) {if (i < DEGREE) {newnode->data[i - ind - 1] = node->data[i];node->data[i] = 0x3f3f3f3f;newnode->children[i - ind - 1] = node->children[i];node->children[i] = NULL;}else {newnode->children[i - ind - 1] = node->children[i];node->children[i] = NULL;}}node->keynum = ind;newnode->keynum = ind;if (node->parent != NULL) {newnode->parent = node->parent;int order = 0;while (newnode->parent->data[order] < node->data[ind]) order++;InsertValueToNode(newnode->parent, order, node->data[ind], newnode);node->data[ind] = 0x3f3f3f3f;}else {B_Tree* headnode = new B_Tree();node->parent = headnode;newnode->parent = headnode;headnode->children[0] = node;InsertValueToNode(headnode, 0, node->data[ind], newnode);node->data[ind] = 0x3f3f3f3f;*tree = headnode;}node = node->parent;}}