罗朝辉(飘飘白云)

关注嵌入式操作系统,移动平台,图形开发。-->加微博 ^_^

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  85 随笔 :: 0 文章 :: 169 评论 :: 0 Trackbacks

树算法之 B 树   

罗朝辉(http://www.cppblog.com/kesalin

转载请注明出处

树是一种被设计成专门存储在磁盘上的平衡查找树。因为磁盘的操作速度要大大慢于随机存取存储器,所以在分析树的性能时,不仅要看动态集合操作花了多少计算时间,还要看执行了多少次磁盘存储操作。 树与红黑树(下一篇介绍)类似,但在降低磁盘I/O 操作次数方面要更好一些。许多数据库系统就使用 树或 树的变形来存储信息,想象一下一棵每个节点包含 1001 个 key 的高度为 的 树能容纳多少数据啊,而在内存中我们只存储了一个节点,在需要的时候再从磁盘中读取所需的节点。

树红黑树比较:

树的节点有很多子女,从几个到几千,而红黑树只有左右两个;一棵含有 个节点的树与红黑树的高度均为 O(lgn),只不过 树的分支较多,因此高度一般要少于红黑树。

树到底是怎样一棵树呢,下面来看定义:

1),每个节点 有如下域:
        A),keyNum,节点中存储的关键字的个数。
        B),keyNum 个以非降序次序排列的关键字 key[0 ... keyNum - 1]
        C),isLeaf,判断是否是叶子节点还是内节点的标志。

2),每个内节点还包含 keyNum + 1 个指向其子女的指针 child[i] (i >= 0 && i <= keyNum)

3),各个关键字 key[i] 对存储在各子树中的关键字范围加以分隔:即 key[i] 大于等于其左侧子树中的所有关键字,而小于等于其右侧子树中的所有关键字。

4),每个叶节点具有相同的深度,即均为树的高度 h

5)每一个节点能包含的关键字有一个上限和下限。这些界限可以用一个称作 树的最小度数的固定整数 T >= 2 来表示。
        A),每个非根的节点必须至少有 T - 1 个关键字。每个非根的内节点至少有 个子女。如果树是非空的,则根节点至少包含一个关键字。
        B),每个节点可包含至多 2T - 1 个关键字。所以一个内节点至多有 2T 个子女。当一个节点正好有 2T - 1 个关键字时,我们就说这个节点是满的。

等于 2  时的树是最简单的。这时每个内节点有 个或 个或 个子女,这种 树也被称作为 2-3-4 树。当然在实际应用中 的取值比这个大得多。

下面我实现了 默认等于 的 树:

// 定义 B 树的最小度数
// 每个节点中关键字的最大数目 BTree_N = 2 * BTree_T - 1
#define    BTree_T        2
#define BTree_N        (BTree_T * 2 - 1)

struct BTNode {
    
int    keynum;                        // 结点中关键字的个数,keynum <= BTree_N
    int key[BTree_N];                // 关键字向量为key[0..keynum - 1]
    BTNode* child[BTree_T * 2];        // 孩子指针向量为child[0..keynum]
    bool isLeaf;                    // 是否是叶子节点的标志
}
;

typedef BTNode
* BTree;                // B树的类型


void BTree_create(BTree* tree, const int* data, int length);

void BTree_destory(BTree* tree);

void BTree_insert(BTree* tree, int key);

void BTree_remove(BTree* tree, int key);

void BTree_print(BTree tree, int her = 1);

// 在B树 tree 中查找关键字 key,
// 成功时返回找到的节点的地址及 key 在其中的位置 *pos
// 失败时返回 NULL 及查找失败时扫描到的节点位置 *pos
//
BTNode* BTree_search(const BTree tree, int key, int* pos);


下面来看具体的接口实现:

#define max(a, b) (((a) > (b)) ? (a) : (b))

//#define DEBUG_TREE

#ifdef DEBUG_TREE
#define debug_print(fmt,) printf(fmt, ## __VA_ARGS__)
#else
#define debug_print(fmt,)
#endif

// 模拟向磁盘写入节点
void disk_write(BTNode* node)
{
    printf(
"向磁盘写入节点\n");
}


// 模拟从磁盘读取节点
void disk_read(BTNode** node)
{
    printf(
"从磁盘读取节点\n");
}


// 按层次打印 B 树
void BTree_print(BTree tree, int her)
{
    
int i;
    BTNode
* node = tree;

    
if (node) {
        printf(
"第 %d 层, %d node : ", her, node->keynum);

        
for (i = 0; i < node->keynum; ++i) {
            printf(
"%c ", node->key[i]);
        }


        printf(
"\n");

        
++her;
        
for (i = 0 ; i <= node->keynum; i++{
            
if (node->child[i]) {
                BTree_print(node
->child[i], her);
            }

        }

    }

    
else {
        printf(
"树为空。\n");
    }

}


// 将非满的节点与其第 index 个满孩子节点合并
// parent 是一个非满的父节点
// node 是 tree 孩子表中下标为 index 的孩子节点,且是满的
void BTree_split_child(BTNode* parent, int index, BTNode* node)
{
    assert(parent 
&& node);

    
int i;

    
// 创建新节点,存储 node 中后半部分的数据
    BTNode* newNode = (BTNode*)calloc(sizeof(BTNode), 1);
    
if (!newNode) {
        printf(
"Error! out of memory!\n");
        
return;
    }


    newNode
->isLeaf = node->isLeaf;
    newNode
->keynum = BTree_T - 1;

    
// 拷贝 node 后半部分关键字
    for (i = 0; i < newNode->keynum; ++i){
        newNode
->key[i] = node->key[BTree_T + i];
        node
->key[BTree_T + i] = 0;
    }


    
// 如果 node 不是叶子节点,拷贝 node 后半部分的孩子节点
    if (!node->isLeaf) {
        
for (i = 0; i < BTree_T; i++{
            newNode
->child[i] = node->child[BTree_T + i];
            node
->child[BTree_T + i] = NULL;
        }

    }


    
// 将 node 分裂出 newNode 之后,里面的数据减半
    node->keynum = BTree_T - 1;

    
// 调整父节点
    for (i = parent->keynum; i > index; --i) {
        parent
->child[i + 1= parent->child[i];
    }


    parent
->child[index + 1= newNode;

    
for (i = parent->keynum - 1; i >= index; --i) {
        parent
->key[i + 1= parent->key[i];
    }


    parent
->key[index] = node->key[BTree_T - 1];
    
++parent->keynum;

    
// 清除 node 中的中后部数据
    
// 可以不处理,因为是通过 keynum 控制访问的
//     for (i = BTree_T - 1; i < BTree_N; ++i) {
//         node->key[i] = 0;
//         node->child[i + 1] = NULL;
//     }

    
// 写入磁盘
     disk_write(parent);
     disk_write(newNode);
     disk_write(node);
}


void BTree_insert_nonfull(BTNode* node, int key)
{
    assert(node);

    
int i;

    
// 节点是叶子节点,直接插入
    if (node->isLeaf) {
        i 
= node->keynum - 1;
        
while (i >= 0 && key < node->key[i]) {
            node
->key[i + 1= node->key[i];
            
--i;
        }


        node
->key[i + 1= key;
        
++node->keynum;

        
// 写入磁盘
        disk_write(node);
    }


    
// 节点是内部节点
    else {
        
// 查找插入的位置
        i = node->keynum - 1;
        
while (i >= 0 && key < node->key[i]) {
            
--i;
        }


        
++i;

        
// 从磁盘读取孩子节点
        disk_read(&node->child[i]);

        
// 如果该孩子节点已满,分裂调整值
        if (node->child[i]->keynum == BTree_N) {
            BTree_split_child(node, i, node
->child[i]);

            
if (key > node->key[i]) {
                
++i;
            }

        }


        BTree_insert_nonfull(node
->child[i], key);
    }

}


void BTree_insert(BTree* tree, int key)
{
    BTNode
* node;
    BTNode
* root = *tree;

    
// 树为空
    if (NULL == root) {
        root 
= (BTNode*)calloc(sizeof(BTNode), 1);
        
if (!root) {
            printf(
"Error! out of memory!\n");
            
return;
        }

        root
->isLeaf = true;
        root
->keynum = 1;
        root
->key[0= key;

        
*tree = root;

        
// 写入磁盘
        disk_write(root);

        
return;
    }


    
// 节点已满,需要进行分裂调整
    if (root->keynum == BTree_N) {
        
// 产生新节点当作根
        node = (BTNode*)calloc(sizeof(BTNode), 1);
        
if (!node) {
            printf(
"Error! out of memory!\n");
            
return;
        }


        
*tree = node;
        node
->isLeaf = false;
        node
->keynum = 0;
        node
->child[0= root;

        BTree_split_child(node, 
0, root);

        BTree_insert_nonfull(node, key);
    }


    
// 节点未满,在当前节点中插入 key
    else {
        BTree_insert_nonfull(root, key);
    }

}



// 对 tree 中的节点 node 进行合并孩子节点处理
// 注意:孩子节点的 keynum 必须均已达到下限,即均等于 BTree_T - 1
// 将 node 中索引为 index + 1 的孩子节点合并到索引为 index 的孩子节点中,
// 并将 tree 中索引为 index  的 key 下降到该节点中,调整相关的 key 和指针。
//
void BTree_merge_child(BTree* tree, BTNode* node, int index)
{
    assert(tree 
&& node && index >= 0 && index < node->keynum);

    
int i;

    
int key = node->key[index];
    BTNode
* prevChild = node->child[index];
    BTNode
* nextChild = node->child[index + 1];

    assert(prevChild 
&& prevChild->keynum == BTree_T - 1
        
&& nextChild && nextChild->keynum == BTree_T - 1);

    prevChild
->key[prevChild->keynum] = key;
    prevChild
->child[prevChild->keynum + 1= nextChild->child[0];
    
++prevChild->keynum;

    
// 合并
    for (i = 0; i < nextChild->keynum; ++i) {
        prevChild
->key[prevChild->keynum] = nextChild->key[i];
        prevChild
->child[prevChild->keynum + 1= nextChild->child[i + 1];
        
++prevChild->keynum;
    }


    
// 在 node 中移除 key 以及指向后继孩子节点的指针
    for (i = index; i < node->keynum - 1++i) {
        node
->key[i] = node->key[i + 1];
        node
->child[i + 1= node->child[i + 2];
    }


    node
->key[node->keynum - 1= 0;
    node
->child[node->keynum] = NULL;
    
--node->keynum;

    
// 如果根节点没有 key 了,删之,并将根节点调整为前继孩子节点。
    if (node->keynum == 0{
        
if (*tree == node) {
            
*tree = prevChild;
        }


        free(node);
        node 
= NULL;
    }


    free(nextChild);
}


void BTree_remove(BTree* tree, int key)
{
    
// B-数的保持条件之一:
    
// 非根节点的内部节点的关键字数目不能少于 BTree_T - 1

    
int i, j, index;
    BTNode 
*root = *tree;
    BTNode 
*node = root;
    BTNode 
*prevChild, *nextChild, *child;
    
int prevKey, nextKey;

    
if (!root) {
        printf(
"Failed to remove %c, it is not in the tree!\n", key);
        
return;
    }


    index 
= 0;
    
while (index < node->keynum && key > node->key[index]) {
        
++index;
    }


    
//
    
//  index of key:    i-1  i  i+1
    
//                +---+---+---+---+---+
    
//               +   + A +   +  
    
//                +---+---+---+---+---+
    
//                 /    |    \
    
//  index of C: i - 1   i    i + 1
    
//               /      |      \
    
//        +---+---+     +---+      +---+---+
    
//       +   +     +   +   +   +  
    
//        +---+---+     +---+      +---+---+
    
//      prevChild     child   nextChild

    
// Find the key.
    if (index < node->keynum && node->key[index] == key) {
        
// 1,所在节点是叶子节点,直接删除
        if (node->isLeaf) {
            
for (i = index; i < node->keynum; ++i) {
                node
->key[i] = node->key[i + 1];
                node
->child[i + 1= node->child[i + 2];
            }


            
--node->keynum;

            
if (node->keynum == 0{
                assert(node 
== *tree);
                free(node);
                
*tree = NULL;
            }


            
return;
        }


        
// 2a,如果位于 key 前的子节点的 key 数目 >= BTree_T,
        
// 在其中找 key 的前驱,用前驱的 key 值赋予 key,
        
// 然后在前驱所在孩子节点中递归删除前驱。
        else if (node->child[index]->keynum >= BTree_T) {
            prevChild 
= node->child[index];
            prevKey 
= prevChild->key[prevChild->keynum - 1];
            node
->key[index] = prevKey;

            BTree_remove(
&prevChild, prevKey);
        }


        
// 2b,如果位于 key 后的子节点的 key 数目 >= BTree_T,
        
// 在其中找 key 的后继,用后继的 key 值赋予 key,
        
// 然后在后继所在孩子节点中递归删除后继。
        else if (node->child[index + 1]->keynum >= BTree_T) {
            nextChild 
= node->child[index + 1];
            nextKey 
= nextChild->key[0];
            node
->key[index] = nextKey;

            BTree_remove(
&nextChild, nextKey);
        }


        
// 2c,前驱和后继都只包含 BTree_T - 1 个节点,
        
// 将 key 下降前驱孩子节点,并将后继孩子节点合并到前驱孩子节点,
        
// 删除后继孩子节点,在 node 中移除 key 和指向后继孩子节点的指针,
        
// 然后在前驱所在孩子节点中递归删除 key。
        else if (node->child[index]->keynum == BTree_T - 1
            
&& node->child[index + 1]->keynum == BTree_T - 1){
            prevChild 
= node->child[index];

            BTree_merge_child(tree, node, index);

            
// 在前驱孩子节点中递归删除 key
            BTree_remove(&prevChild, key);
        }

    }


    
// 3,key 不在内节点 node 中,则应当在某个包含 key 的子节点中。
    
//  key < node->key[index], 所以 key 应当在孩子节点 node->child[index] 中
    else {
        child 
= node->child[index];
        
if (!child) {
            printf(
"Failed to remove %c, it is not in the tree!\n", key);
            
return;
        }


        
if (child->keynum == BTree_T - 1{
            prevChild 
= NULL;
            nextChild 
= NULL;

            
if (index - 1 >= 0{
                prevChild 
= node->child[index - 1];
            }


            
if (index + 1 <= node->keynum) {
                nextChild 
= node->child[index + 1];
            }


            
// 3a,如果所在孩子节点相邻的兄弟节点中有节点至少包含 BTree_t 个关键字
            
// 将 node 的一个关键字下降到 child 中,将相邻兄弟节点中一个节点上升到
            
// node 中,然后在 child 孩子节点中递归删除 key。
            if ((prevChild && prevChild->keynum >= BTree_T)
                
|| (nextChild && nextChild->keynum >= BTree_T)) {

                
if (nextChild && nextChild->keynum >= BTree_T) {
                    child
->key[child->keynum] = node->key[index];
                    child
->child[child->keynum + 1= nextChild->child[0];
                    
++child->keynum;

                    node
->key[index] = nextChild->key[0];

                    
for (j = 0; j < nextChild->keynum - 1++j) {
                        nextChild
->key[j] = nextChild->key[j + 1];
                        nextChild
->child[j] = nextChild->child[j + 1];
                    }

                    
--nextChild->keynum;
                }

                
else {
                    
for (j = child->keynum; j > 0--j) {
                        child
->key[j] = child->key[j - 1];
                        child
->child[j + 1= child->child[j];
                    }

                    child
->child[1= child->child[0];
                    child
->child[0= prevChild->child[prevChild->keynum];
                    child
->key[0= node->key[index - 1];
                    
++child->keynum;

                    node
->key[index - 1= prevChild->key[prevChild->keynum - 1];

                    
--prevChild->keynum;
                }

            }


            
// 3b, 如果所在孩子节点相邻的兄弟节点都只包含 BTree_t - 1 个关键字,
            
// 将 child 与其一相邻节点合并,并将 node 中的一个关键字下降到合并节点中,
            
// 再在 node 中删除那个关键字和相关指针,若 node 的 key 为空,删之,并调整根。
            
// 最后,在相关孩子节点中递归删除 key。
            else if ((!prevChild || (prevChild && prevChild->keynum == BTree_T - 1))
                
&& ((!nextChild || nextChild && nextChild->keynum == BTree_T - 1))) {
                
if (prevChild && prevChild->keynum == BTree_T - 1{

                    BTree_merge_child(tree, node, index 
- 1);

                    child 
= prevChild;
                }


                
else if (nextChild && nextChild->keynum == BTree_T - 1{

                    BTree_merge_child(tree, node, index);
                }

            }

        }


        BTree_remove(
&child, key);
    }

}


BTNode
* BTree_search(const BTree tree, int key, int* pos)
{
    
if (!tree) {
        
return NULL;
    }


    
int i = 0;

    
while (i < tree->keynum && key > tree->key[i]) {
        
++i;
    }


    
// Find the key.
    if (i < tree->keynum && tree->key[i] == key) {
        
if (pos) {
            
*pos = i;
        }


        
return tree;
    }


    
// tree 为叶子节点,找不到 key,查找失败返回
    if (tree->isLeaf) {
        
return NULL;
    }


    
// 节点内查找失败,但 tree->key[i - 1]< key < tree->key[i],
    
// 下一个查找的结点应为 child[i]

    
// 从磁盘读取第 i 个孩子的数据
    disk_read(&tree->child[i]);

    
// 递归地继续查找于树 tree->child[i]
    return BTree_search(tree->child[i], key, pos);
}


void BTree_create(BTree* tree, const int* data, int length)
{
    assert(tree);

    
int i;

#ifdef DEBUG_TREE
    debug_print(
"\n 开始创建 B- 树,关键字为:\n");
    
for (i = 0; i < length; i++{
        printf(
" %c ", data[i]);
    }

    debug_print(
"\n");
#endif


    
for (i = 0; i < length; i++{
#ifdef DEBUG_TREE
        debug_print(
"\n插入关键字 %c:\n", data[i]);
#endif
        BTree_insert(tree, data[i]);

#ifdef DEBUG_TREE
        BTree_print(
*tree);
#endif
    }


    debug_print(
"\n");
}


void BTree_destory(BTree* tree)
{
    
int i;
    BTNode
* node = *tree;

    
if (node) {
        
for (i = 0; i <= node->keynum; i++{
            BTree_destory(
&node->child[i]);
        }


        free(node);
    }


    
*tree = NULL;
}


测试代码:

//==================================================================
//                    测试 B 树
//==================================================================
void test_BTree_search(BTree tree, int key)
{
    
int pos = -1;
    BTNode
*    node = BTree_search(tree, key, &pos);
    
if (node) {
        printf(
"在%s节点(包含 %d 个关键字)中找到关键字 %c,其索引为 %d\n",
            node
->isLeaf ? "叶子" : "非叶子",
            node
->keynum, key, pos);
    }
    
else {
        printf(
"在树中找不到关键字 %c\n", key);
    }
}

void test_BTree_remove(BTree* tree, int key)
{
    printf(
"\n移除关键字 %c \n", key);
    BTree_remove(tree, key);
    BTree_print(
*tree);
    printf(
"\n");
}

void test_btree()
{
    
const int length = 10;
    
int array[length] = {
        
'G''M''P''X''A''C''D''E''J''K',
        
//'N', 'O', 'R', 'S', 'T', 'U', 'V', 'Y', 'Z', 'F'
    };

    BTree tree 
= NULL;
    BTNode
* node = NULL;
    
int pos = -1;
    
int key1 = 'R';        // in the tree.
    int key2 = 'B';        // not in the tree.

    
// 创建
    BTree_create(&tree, array, length);

    printf(
"\n=== 创建 B- 树 ===\n");
    BTree_print(tree);
    printf(
"\n");

    
// 查找
    test_BTree_search(tree, key1);
    printf(
"\n");
    test_BTree_search(tree, key2);

    
// 插入关键字
    printf("\n插入关键字 %c \n", key2);
    BTree_insert(
&tree, key2);
    BTree_print(tree);
    printf(
"\n");

    test_BTree_search(tree, key2);

    
// 移除关键字
    test_BTree_remove(&tree, key2);
    test_BTree_search(tree, key2);

    key2 
= 'M';
    test_BTree_remove(
&tree, key2);
    test_BTree_search(tree, key2);

    key2 
= 'E';
    test_BTree_remove(
&tree, key2);
    test_BTree_search(tree, key2);

    key2 
= 'G';
    test_BTree_remove(
&tree, key2);
    test_BTree_search(tree, key2);

    key2 
= 'A';
    test_BTree_remove(
&tree, key2);
    test_BTree_search(tree, key2);

    key2 
= 'D';
    test_BTree_remove(
&tree, key2);
    test_BTree_search(tree, key2);

    key2 
= 'K';
    test_BTree_remove(
&tree, key2);
    test_BTree_search(tree, key2);

    key2 
= 'P';
    test_BTree_remove(
&tree, key2);
    test_BTree_search(tree, key2);

    key2 
= 'J';
    test_BTree_remove(
&tree, key2);
    test_BTree_search(tree, key2);

    key2 
= 'C';
    test_BTree_remove(
&tree, key2);
    test_BTree_search(tree, key2);

    key2 
= 'X';
    test_BTree_remove(
&tree, key2);
    test_BTree_search(tree, key2);

    
// 销毁
    BTree_destory(&tree);
}

测试结果:

=== 创建 B  树 ===

第 层, 1 node : E

第 层, 1 node : C

第 层, 1 node : A

第 层, 1 node : D

第 层, 1 node : M

第 层, 3 node : G J K

第 层, 2 node : P X

从磁盘读取节点

从磁盘读取节点

在树中找不到关键字 R

从磁盘读取节点

从磁盘读取节点

在树中找不到关键字 B

插入关键字 B

从磁盘读取节点

从磁盘读取节点

向磁盘写入节点

第 层, 1 node : E

第 层, 1 node : C

第 层, 2 node : A B

第 层, 1 node : D

第 层, 1 node : M

第 层, 3 node : G J K

第 层, 2 node : P X

从磁盘读取节点

从磁盘读取节点

在叶子节点(包含 个关键字)中找到关键字 B,其索引为 1

.......


参考资料:

1,《算法导论》


posted on 2011-03-21 23:10 罗朝辉 阅读(4032) 评论(5)  编辑 收藏 引用 所属分类: Algorithms

评论

# re: 【树】树算法之 B 树 2011-03-21 23:33 coreBugZJ
表示只略知理论,没写过代码  回复  更多评论
  

# re: 【树】树算法之 B 树 2011-03-23 11:33 望见
写入磁盘应该采取什么样的格式呢?读取又应该采取什么样的策略?  回复  更多评论
  

# re: 【树】树算法之 B 树 2011-03-23 16:06 罗朝辉
@望见

在 B 树的实际应用中,每个节点存储的关键字一般都较大(1千 ~ 几千不等),所以一般只存储 root 节点,以减少内存消耗,然后在需要的时候再从磁盘中读取或写入相应的节点,进行下一步操作。这里所说的从磁盘读取或写入就是从磁盘文件中读取或写入,一般都是从数据库文件中。
  回复  更多评论
  

# re: 【树】树算法之 B 树[未登录] 2011-12-13 09:35 peter
@罗朝辉
Hi, 最近在弄这个B-B+树~~继续前面兄台的问题:
B树的节点是怎么存储在磁盘上的了?也就是B树的序列化和解序列化一般是怎么样的了?  回复  更多评论
  

# re: 【树】树算法之 B 树 2011-12-13 20:55 罗朝辉
@peter
存储到磁盘上的方法有多种,可以写入文件,数据库,序列化等,至于序列化的具体实现要看具体语言/库的支持,或自己实现了  回复  更多评论
  


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理