定义

B树是为磁盘或其他直接存取的辅助存储设备而设计的一种平衡搜索树。B树类似于红黑树，但它在降低磁盘I/O操作方面要好一点。许多数据库系统使用B树或B树的变种来存储信息。

B树和红黑树的不同之处在于B树的结点可以有很多孩子，从数个到数千个。

如果B树的一个内部结点x包含x.n个关键字，那么结点x就有x.n+1个孩子，关键字是分隔点

性质

创建

typedef struct node {
    int key[length]; // 分隔值
    node *c[length+1]; // 指向孩子的指针 
    bool leaf; // 是否是叶子结点,true是叶子
    int n; // 分隔值的数量
} *NODE;

void B_tree_create(T) { //创建一个B树
    NODE x = allocate_node();
    x->leaf = true;
    x->n = 0;
    disk_write(x);
    T = x;
}

查找

NODE B_tree_search(NODE x, int k) {
    i = 1;
    while( i <= x->n && k > x->key[i]) {
        i = i + 1;
    }
    if(i <= x->n && k == x->key[i])
        return (x,i);
    else if(x->leaf == true) 
        return NULL;
    else {
        disk_read(x->c[i]);
        return B_tree_search(x->c[i], k);
    }
}

插入

分裂B树中的结点

typedef struct node {
    int key[length]; // 分隔值
    node *c[length+1]; // 指向孩子的指针 
    bool leaf; // 是否是叶子结点,true是叶子
    int n; // 分隔值的数量
} *NODE;

void B_tree_split_child(NODE x, int i,int t) { //分裂i点,t是度数
    NODE z = allocate_node() //创建结点，并不需要disk_read()
    NODE y = x->c[i];
    z.leaf = y.leaf;
    z->n = t-1;
    for(int j = 1; j <= t-1; j++) { // y中i后面的赋值给z
        z->key[j] = y->key[j+t];
    }
    if(y->leaf != true) { //y不是叶子结点
        for(int j = 1; j <= t; j++) {
            z->c[j] = y->c[j+t];
        }
    }
    y->n = t-1;
    for(int j = x->n + 1; j >= i + 1; j--) { // x结点i后的指针往后退
        x->c[j+1] = x->c[j];
    }
    x->c[i+1] = z;
    for(int j = x->n; j >= i; j--) { // x结点i后的值往后退
        x->key[j+1] = x->key[j];
    }
    x->key[i] = y->key[i];
    x->n = x->n + 1;
    disk_write(y);
    disk_write(z);
    disk_write(x);

}

以沿树单程下行方式向B树插入关键字

代码对应上图
void B_tree_insert(NODE T, int k, int t) { //t代表最小度数
    NODE r = T; 
    if(r->n == (2*t - 1)) { //结点已满
        NODE s = allocate_node() 
        T = s;
        s->leaf = false;
        s->n = 0;
        s->c[1] = r;
        B_tree_split_child(s, i, t); //分裂该结点H
        B_tree_insert_nonfull(s, k); //因为该结点未满，插入k结点，该函数代码在下面

    }else{ //结点未满
        B_tree_insert_nonfull(r, k);
    }
}


上图为插入的例子    
void B_tree_insert_nonfull(NODE x, int k, int t) { //t代表最小度数, k要插入的值
    i = x->n;
    if(x->leaf == true) { //是叶子结点
        while(i >=1 && k < x->key[i]) { //升序，找到k点的正确位置
            x->key[i+1] = x->key[i];
            i = i - 1;
        }
        x->key[i+1] = k;
        x->n = x->n + 1;
        disk_write(x);

    }else { //不是叶子结点
        while( i >= 1 && k < x->key[i]) { //找到k点的正确位置，但是x->c[k] 可能是满叶子结点
            i = i - 1;
        }
        i = i + 1;
        disk_read(x->c[i]);
        if(x->c[i]->n == (2*t - 1)) { // 判断是否是满结点
            B_tree_split_child(x, i, t) //结点孩子分割
            if(k > x->key[i]) {
                i = i + 1;
            }
        }
        B_tree_insert_nonfull(x->c[i], k ,t); //再次插入到未满结点的地方
    }
}

删除