Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1023872
  • 博文数量: 242
  • 博客积分: 10209
  • 博客等级: 上将
  • 技术积分: 3028
  • 用 户 组: 普通用户
  • 注册时间: 2008-03-12 09:27
文章分类

全部博文(242)

文章存档

2014年(1)

2013年(1)

2010年(51)

2009年(65)

2008年(124)

我的朋友

分类: C/C++

2010-04-14 21:15:43



常见的 数据库系统,其索引使用的数据结构多是
B-Tree或者B+Tree。例如,MsSql使用的是B+TreeOracleSysbase使用的是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)应该是错了。
                }
            }
        }
    }
阅读(1400) | 评论(1) | 转发(0) |
给主人留下些什么吧!~~

chinaunix网友2010-08-17 19:50:31

我也看了一下午的B 树, 算法导论 " 1)如果关键字k在结点x中而且x是个叶结点,则从x中删除k " 这里面隐含着 x 至少有t个关键字. 情形 3)就是为了保证这个的。 老兄的代码看起来比书上的伪代码要容易得多, 可能因为具体代码更精确些吧. 不过你的代码没有严格区分三种情形, 我个人认为整个代码的思路是把所有可能情形都归结到叶结点,再做删除, 在此过程中做适当的合并. 欢迎交流,我的邮箱是 liu_de_yang@qq.com