B-Tree

常见的 数据库系统，其索引使用的数据结构多是B-Tree或者B+Tree。例如，MsSql使用的是B+Tree，Oracle及Sysbase使用的是B-Tree。

这里主要讲一下B-Tree 的性质 以及其上的操作。B-Tree是一种多路平很查找树，当查找的文件较大，且存放在磁盘等直接存取设备中时，B-Tree可以减少查找过程中对磁盘的读写次数，提高查找效率。

B-Tree是一种有如下特征的树：

1.每个节点x有三个域：

                a. x中现有的keys的个数n；

                b. 所有keys的集合，按非递减顺序排列，k[0],k[1],k[2],k[3].......k[n-1]；

                c. 一个boolean类型的标志IsLeaf，标示x是否为叶节点；

                d.  每一个非叶节点还有一个域，这个域包含了n+1个指针，指向该节点的n+1个子节点

                     c[0],c[1],c[2]......c[n]。

2.节点 x 中的 n 个keys刚好把 x 的 n+1 个子树划分开来，设 m[i] 为 x 中 以 c[i] 为根的子树 中的任  意key值，则有如下关系成立：

                 m[0] <= k[0] <= m[1] <= k[1] .........m[m-1] <= k[n-1] <= m[n]。

3.所有的叶节点都有同样的深度，即树高 h。

4.B-Tree有一个参数叫做 最小度数，是一个大于等于2的整数，这里记为 t ，除了根以外的其他节点必须拥有至少 t-1 个keys； 每一个节点都最多拥有 2t-1 个keys。

磁盘存取次数取决于B-Tree的高度，对于 含有 n (n>=1)个节点，最小度数 为 t (t>=2) 的B-Tree，

其树高 h <= log t ((n+1)/2)。

思考一下用下述做法来表示B-Tree中的节点可以么？

struct b_tree_data{     //该结构用于记录存储数据，其中既有用于排序的keys，又有其他额外数据。

    int key;

    extra_infomation ......

    struct b_tree_data *next; //next 指针用于位于同一节点中的多个data的链接。

}

struct b_tree_node{

    int num_of_keys;

    boolean is_leaf;

    struct b_tree_data *data;  //相当于前面介绍的 k[0],k[1],k[2],k[3].......k[n-1]；

    struct b_tree_node *subnode_list; //相当于前面介绍的 c[0],c[1],c[2]......c[n]；

    struct b_tree_node *next;   //该指针将同一节点的所有子节点链接起来，也就是说不用数组

                                             //表示 c[0],c[1],......c[n]，而是用指针链接起来，这样有理由动态分派 内存。

}

其实，上述做法是不符合B-Tree的工作环境的，画蛇添足的味道十分明显。B-Tree本来就是用于排序

磁盘中的数据而非内存中的数据，B-Tree的节点和节点中的数据一般来说也是存放在磁盘中的，常驻内存的节点通常只有root和遍历时的某些，磁盘页中的节点就是有序存放的，所以用数组更符合

B-Tree的操作环境。

#define t 1000

struct b_tree_node{

    int num_of_keys;

    boolean is_leaf;

    int keys[2t-1];

    struct b_tree_node subnodes[2t];

}

B-Tree上操作：

1.搜索

    b_tree-search( x, k ){  //x是被搜索B-Tree的根节点或者某个子节点，k是要搜索的key值.

    //这里假设搜索开始时节点x已经在内存中，故这里没有DISK_READ。

        i = 0;

        while ( i < x->num_of_keys  &&  k>x->keys[i] )

            i++;

        if ( inum_of_keys && k=x->keys[i]){

            DISK_READ(x->subnodes[i]);

            return x->subnodes[i];

        }

        if (x->is_leaf == ture)

            return NULL;

        DISK_READ(x->subnodes[i]);

        return b_tree_search(x->subnode[i] , k);

    }

从上面程序可以看出，B-Tree搜索的DISK_READ次数为O(log t (n)) ,cpu算法复杂度为O(t * log t (n))

2.新建一个空的B-Tree

    b_tree_creat(tree){ //这里tree的结构定义我没有给出，大致就是定义一个t值和一个指向根的指针

        struct b_tree_node *x = (struct b_tree_node *)malloc(sizeof(struct b_tree_node ));

        x->is_leaf = true;

        x->num_of_keys = 0;

        DISK_WRITE(x)；

        tree->root = x;

    }

//这里我好像面临着一个设计上的问题：最小度数 t 应该是在tree结构中定义的？还是在creat的时候//作为参数传入的？我有怎么把这样的来的 t 值给 struct b_tree_node 结构定义时使用呢？

3.插入操作

    b_tree_split_child(x, i, y) {       //x的第 i 个子节点y满了,即subnodes[i]->num_of_keys为2t-1，

                                                 //需要分拆。

        struct b_tree_node *z = (struct b_tree_node *)malloc(sizeof(struct b_tree_node ));

        z->is_leaf = y->is_leaf;

        z->num_of_keys = t-1; //z中keys个数

        for (j=0; j

            z->keys[j] = y->keys[t+j];

       if (y->is_leaf == false)

           for(j=0; j<= t-1; j++)

               z->subnodes[j] = y->subnodes[t+j];//将y中后面t个subnodes给z中的subnodes。

        y->num_of_keys = t-1;//y中keys个数

        for (j=x->num_of_keys; j>=i+1; j--) //移动x中子节点位置，为新的子节点z腾位置

            x->subnodes[j+1] = subnodes[j];

        x->subnodes[i+1] = z;

        for (j=x->num_of_keys-1; j>=i; j++)//移动x中keys的位置，为新的key腾位置

            x->keys[j+1] = x->keys[j];

        x->keys[i] = y->keys[t];

        x->num_of_keys ++;

        DISK_WRITE(x)；

        DISK_WRITE(y);

        DISK_WRITE(z);

    }

    b_tree_insert(T, k){

        struct b_tree_node *r = T->root;

        if(r->num_of_keys == 2t-1){  //分成两种情况，根已满和根未满

            struct b_tree_node *s = (struct b_tree_node *)malloc(sizeof(struct b_tree_node ));

            T->root = s;

            s->is_leaf = false;

            s->num_of_keys = 0;

            s->subnodes[0] = r;

            b_tree_split_child(s, 0, r);

            b_tree_insert_nonfull(s, k);

        }else

            b_tree_insert_nonfull(r, k);

    }

    b_tree_insert_nonfull(x, k){

        int i = x->num_of_keys;

        if(x->is_leaf == true){  //分两种情况：x是根节点或是叶节点

            while(i>=0 && kkeys[i]){

                x->keys[i+1] = x->keys[i];

                i--;

            }

            x->keys[i+1] = k;

            DISK_WRITE(x);

        }else{

            while(i>=0 && kkeys[i])

                i--;

            i = i+1;

            //这里已经假定所插入的 k 在目前的B-Tree中还没有，所以并 没有判断是否已存在。

            DISK_READ(x->subnodes[i]);

            if(x->subnodes[i]->num_of_keys == 2t-1){

                b_tree_split_child(x, i, x->subnodes[i]);

                if(k > x->keys[i])

                    i = i+1;

            }

            b_tree_insert_nonfull(x->subnodes[i], k);

        }

    }

b_tree_insert()的磁盘存取复杂度为O(log t n), cpu 复杂度为O(t * log t n) , 任意时刻需要驻留在内存中的
磁盘页数为O(1)。

4.删除操作
    b_tree_delete(T, k){  //这里假设要delete的 k 在树中一定存在
       
        if (x->is_leaf == false){  // 假设(x->keys[i] ==k)
            if(x->subnodes[i]->num_of_keys >= t){
                y = x->subnodes[i];
                while(y->is_leaf != true)
                    y = y->subnodes[ y->num_of_keys ];
                x->keys[i] = y->keys[y->num_of_keys -1];
                b_tree_delete(y, y->keys[y->num_of_keys - 1]);
            }else if(x->subnodes[i+1]->num_of_keys >= t){
                z = x->subnodes[i+1];
                while(y->is_leaf != true)
                    z = z->subnodes[0];
                x->keys[i] = z->keys[0];
                b_tree_delete(z, y->keys[0]);
            }else{
                y = x->subnodes[i];
                z = x->subnodes[i+1];
                merge(y,z,k);  //把z中的所有keys和k一起加入y，这样y就有了2t-1个keys了。
                b_tree_delete(y, k);
            }
        }else{
            if(x->num_of_keys > t-1)
                for(j=i+1; jnum_of_keys;j++)
                    keys[j-1] = keys[j];
            else{  //假设 p->subnodes[m] == x
                if( m>0 && p->subnodes[m-1]->num_of_keys >= t){
                    //省略了，与下个else if中的类似
                }else if( mnum_of_keys && p->subnodes[m+1]->num_of_keys >=t ){
                    z = p->subnodes[m+1];
                    x->keys[x->num_of_keys-1] = p->keys[m];
                    p->keys[m] = z->keys[0];
                    for(j=0; jnum_of_keys-1; j++)
                        z->keys[j] = z->keys[j+1];
                    z->num_of_keys = z->num_of_keys - 1;
                }else{
                    //个人觉得算法导论图18.18(e)中所示的不是这种情况，从(d)到(e)应该是错了。
                }
            }
        }
    }