（学习的主要对象是《算法导论》上B-树章节）
应用环境：
辅存和主存的矛盾，主存只能维持有限的页数，其他页存于辅存上，使用时调入内存。
B树的定义：
是一个具有如下性质的有根树：
(1)每个结点x有以下域：
(a) n[x]，存放结点x的关键字数；
(b) n[x]个关键字本身，以非降序存放；
(c) leaf[x]，1代表x是叶子，0代表x是内结点。
(2)每个内结点包含n[x]+1各指向其子女的指针。叶结点对这个域没有定义。
(3)各关键字对其各子树关键字范围进行分隔。
(4)每个叶结点深度相同。
(5)每个结点包含的关键字有上界和下界，用t表示最小度数，则有
(a)每个非根结点至少t-1各关键字。每个非根的内结点至少t个子女。若树非空，则根至少有一个关键字。
(b)每个结点包含至多2t-1个关键字。因此一个内结点至多可以有2t个子女。
相关算法简述：
搜索算法：
类似于二叉查找树。
分裂算法：
对于关键字达到2t-1时的满结点（可能）将做的操作。简述为，将中间关键字提升至父结点，同时将原结点分裂成两个。
插入算法：
利用了分裂算法，在插入时，逐步下降到要查入的结点，沿途对满结点进行分裂，若不满，直接插入即可，用辅助算法insert_nonful实现。
删除算法：
比较复杂，逐步下降时，对于将来不满足关键字数大于t-1的结点做出调整。调整有多种形式：合并两个关键字为t-1的兄弟；下降父结点至一个关键字所在子树的子结点，同时上升它的一个关键字大于等于t的兄弟结点的关键字至父结点；对于逐步下降后含关键字的叶子，直接删除关键字。
这个简述看上去比较混乱，直接理解算法即可，或者参考算法导论上相关叙述。。
心得体会：
与红黑树相反，B-树的插入和删除在下降时进行调整，而前者是先操作，然后逐步向上调整使其满足性质。因此B-树不需要指向父亲的指针。
同时，B-树由于是在下降过程中调整，因此它不能直接对非根结点调用delete，这样会导致调整不完全。
而且对于B-树关键字和子结点指针操作时，下标比较容易引起混乱。有一个小技巧需要可以减少混乱：下标为i的关键字，其左边的孩子下标也是i。不过编写算法时最好画个示意图，比较清楚。
以下是自己编写的C语言版本的B-树，其中各个操作已经过验证和调整，暂未发现遗留的bug。如果想实现自己的测试过程，调整main函数里面的操作即可。
#include <stdio.h> #include <stdlib.h> #define BT_T 3//B树的度 struct bnode *bt_search(struct bnode *, char); struct bnode *bt_creat(); int bt_split_child(struct bnode *, int, struct bnode *); struct bnode *bt_insert(struct bnode *, char); int bt_insert_nonful(struct bnode *, char); int bt_delete(struct bnode*, char); struct bnode { int num; int leaf; //1 is leaf char value[2*BT_T -1]; struct bnode *child[2*BT_T]; }; struct bnode *bt_search(struct bnode *p, char k) { int i; i = 0; while ((i < p->num) && (k > p->value[i])) i++; if ((i<=p->num) && (k == p->value[i])) { printf("[search]%c's num is %d\n",k,i); return p; } if (p->leaf) { printf("not found.\n"); return NULL; } else { printf("DISK-READ: c%d\n", i); //DISK-READ() return bt_search(p->child[i],k); } } struct bnode *bt_creat() { struct bnode *p; p = (struct bnode *)malloc(sizeof(struct bnode)); p->leaf = 1; p->num = 0; printf("DISK-WRITE: root of new T\n"); return p; } int bt_split_child(struct bnode *x, int i, struct bnode *y) { int j; struct bnode *z; z = (struct bnode *)malloc(sizeof(struct bnode)); printf("in split\n"); z->leaf = y->leaf; z->num = BT_T -1 ; for (j=0;j<BT_T-1;j++) z->value[j] = y->value[j+BT_T]; if (!(y->leaf)) for(j=0;j<=BT_T-1;j++) //there was a bug. z->child[j] = y->child[j+BT_T]; y->num = BT_T -1; for(j=x->num +1;j>=i+1;j--)// x->child[j+1] = x->child[j]; x->child[i+1] = z; for(j=x->num -1;j>=i-1;j--) x->value[j+1] = x->value[j]; x->value[i] = y->value[BT_T-1]; x->num++; printf("DISK-WRITE(y):in split\n"); printf("DISK-WRITE(z):in split\n"); printf("DISK-WRITE(x):in split\n"); } struct bnode* bt_insert(struct bnode *x, char k) {//x is root struct bnode *s; if (x->num == 2*BT_T-1) { s = (struct bnode *)malloc(sizeof(struct bnode)); s->leaf = 0; s->num = 0; s->child[0] = x; bt_split_child(s,0,x); bt_insert_nonful(s,k); return s; } else { bt_insert_nonful(x,k); return x; } } int bt_insert_nonful(struct bnode *x, char k) { int i; struct bnode *p; i = x->num-1; if (x->leaf) { while((i>=0)&&(k<x->value[i])) { x->value[i+1] = x->value[i]; i--; } x->value[i+1] = k; printf("(!!!!)%c %d\n",x->value[i+1],i+1); x->num = x->num+1; printf("DISK-WRITE(x):in bt_insert_nonful\n"); } else { while((i>=0)&&(k<x->value[i-1])) i=i--; i++; printf("DISK-READ(c%d[x]):in insert_nonful\n",i); p = x->child[i]; if (p->num == (2*BT_T - 1)) { bt_split_child(x,i,p); if (k>x->value[i]) i++; } bt_insert_nonful(x->child[i],k);//there was a bug: bt_insert_nonful(p,k); } return 1; } int bt_delete(struct bnode* x, char k) { int i,j,lnum,rnum; struct bnode *p; i=0; while ((i<x->num) && (k>x->value[i])) i++; if ((i<=x->num) && (k == x->value[i])) { if(x->leaf) {//情况(1),不能对叶结点的指针直接调用bt_delete(),这样相当于跳过了情况(3) for(;i<x->num-1;i++) x->value[i] = x->value[i+1]; x->num --; return 1; } else { //情况2 lnum = x->child[i]->num; rnum = x->child[i+1]->num; if (lnum >= BT_T) { x->value[i] = x->child[i]->value[lnum-1]; bt_delete(x->child[i],x->value[i]); return 2; } else if (rnum >= BT_T) { x->value[i] = x->child[i+1]->value[0]; bt_delete(x->child[i+1],x->value[0]); return 2; } else { //合并k两个孩子结点,并把k下降到这个结点 x->child[i]->value[BT_T-1] = k; for(j=0;j<BT_T-1;j++) { x->child[i]->value[BT_T+j] = x->child[i+1]->value[j]; x->child[i]->child[BT_T+j] = x->child[i+1]->child[j]; } x->child[i]->num = 2*BT_T -1; //修改x,使其原k右边的孩子与x断开 for(j=i;j<x->num-1;j++) { x->value[j] = x->value[j+1]; x->child[j+1] = x->child[j+2]; } x->num--; //递归删除k bt_delete(x->child[i],k); return 2; } } } else { if(bt_search(x->child[i],k) == NULL) { printf("[delete]not found!"); return 0; } p = x->child[i]; if (x->child[i]->num >= BT_T) { bt_delete(x->child[i],k); return 3; } else if ((i>0)&&(x->child[i-1]->num >= BT_T)) {//情况3a其1,左兄弟可用 for(j=BT_T-2;j>=0;j--) p->value[j+1] = p->value[j]; p->value[0] = x->value[i-1]; for(j=BT_T;j>=1;j--) p->child[j] = p->child[j-1]; p->child[0] = x->child[i-1]->child[x->child[i-1]->num]; x->value[i-1] = x->child[i-1]->value[x->child[i-1]->num-1]; x->child[i-1]->num--; bt_delete(x->child[i],k); return 3; } else if ((i<x->num-1)&&(x->child[i+1]->num >= BT_T)) {//情况3b其2,右兄弟可用 p->num++; p->value[p->num-1] = x->value[i]; p->child[p->num] = x->child[i+1]->child[0]; x->value[i] = x->child[i+1]->value[0]; p=x->child[i+1];//为了便于编码 for(j=0;j<p->num-1;j--) p->value[j] = p->value[j+1]; for(j=0;j<p->num;j--) p->child[j] = p->child[j+1]; p->num--; bt_delete(x->child[i],k); return 3; } else if (i>0) {//情况3b其1,与左兄弟合并 x->child[i-1]->value[BT_T-1] = x->value[i-1]; for(j=0;j<BT_T-1;j++) x->child[i-1]->value[BT_T+j] = x->child[i]->value[j]; for(j=0;j<=BT_T-1;j++) x->child[i-1]->child[BT_T+j] = x->child[i]->child[j]; for(j=i-1;j<=x->num-2;j++) { x->value[j]=x->value[j+1]; x->child[j+1] = x->child[j+2]; } x->num--; x->child[i-1]->num = 2*BT_T -1; bt_delete(x->child[i-1],k); return 3; } else if (i<x->num-1) {//情况3b其2,与右兄弟合并 x->child[i]->value[BT_T-1] = x->value[i]; for(j=0;j<=BT_T-1;j++) x->child[i]->value[BT_T+j] = x->child[i+1]->value[j]; for(j=0;j<=BT_T;j++) x->child[i]->child[BT_T+j] = x->child[i+1]->child[j]; for(j=i;j<x->num-1;j++) { x->value[i] = x->value[i+1]; x->child[j+1] = x->child[j+2]; } x->num--; x->child[i]->num = 2*BT_T -1; bt_delete(x->child[i],k); return 3; } } } int main() { struct bnode *p,*root; char a; root = bt_creat(); for (a='A';a<='Z';a++) if ((a!='H')&&(a!='I')) root = bt_insert(root,a); bt_delete(root,'M'); bt_search(root,'N'); bt_search(root,'O'); return 1; }