B-tree的代码实现 - c / c++ 版本-阿里云开发者社区

//高大上

看到一篇相关的好文章，引用下：http://www.cnblogs.com/leoo2sk/archive/2011/07/10/mysql-index.html 。相当滴不错，备忘下。

在这篇文章中http://blog.csdn.net/weege/article/details/6526512介绍了B-tree/B+tree/B*tree,并且介绍了B-tree的查找，插入，删除操作。现在重新认识下B-TREE（温故而知新嘛~，确实如此。自己在写代码中会体会到，B-tree的操作出现的条件相对其他树比较复杂，调试也是一个理通思路的过程。)

B-tree又叫平衡多路查找树。一棵m阶的B-tree (m叉树)的特性如下：

（其中ceil(x)是一个取上限的函数）

1) 树中每个结点至多有m个孩子；

2) 除根结点和叶子结点外，其它每个结点至少有有ceil(m / 2)个孩子；

3) 若根结点不是叶子结点，则至少有2个孩子（特殊情况：没有孩子的根结点，即根结点为叶子结点，整棵树只有一个根节点）；

4) 所有叶子结点都出现在同一层，叶子结点不包含任何关键字信息(可以看做是外部结点或查询失败的结点，实际上这些结点不存在，指向这些结点的指针都为null)（PS:这种说法是按照严蔚敏那本教材给出的，具体操作不同而定，下面的实现中的叶子结点是树的终端结点，即没有孩子的结点）；

5) 每个非终端结点中包含有n个关键字信息： (n，P0，K1，P1，K2，P2，......，Kn，Pn)。其中：

a) Ki (i=1...n)为关键字，且关键字按顺序排序K(i-1)< Ki。

b) Pi为指向子树根的接点，且指针P(i-1)指向子树种所有结点的关键字均小于Ki，但都大于K(i-1)。

c) 关键字的个数n必须满足： ceil(m / 2)-1 <= n <= m-1。

具体代码实现如下：(这里只是给出了简单的B-Tree结构，在内存中的数据操作。具体详情见代码吧~！）

头文件：（提供B-Tree基本的操作接口)

[cpp]view plaincopyprint? 
   
 /***************************************************************************  
     @coder:weedge E-mail:weege@126.com  
     @date:2011/08/27  
     @comment:  
         参考：http://www.cppblog.com/converse/archive/2009/10/13/98521.html  
         实现对order序(阶)的B-TREE结构基本操作的封装。  
         查找：search，插入：insert，删除：remove。  
         创建：create，销毁：destory，打印：print。  
 **********************************************************/   
 #ifndef BTREE_H   
 #define BTREE_H   
    
 #ifdef __cplusplus   
 extern "C" {   
 #endif   
    
 ////* 定义m序(阶)B 树的最小度数BTree_D=ceil(m/2)*/   
 /// 在这里定义每个节点中关键字的最大数目为:2 * BTree_D - 1，即序(阶)：2 * BTree_D.   
 #define BTree_D        2   
 #define ORDER        (BTree_D * 2) //定义为4阶B-tree,2-3-4树。(偶序)   
 //#define ORDER        (BTree_D * 2-1)//最简单为3阶B-tree,2-3树。(奇序)   
    
     typedef int KeyType;   
     typedef struct BTNode{   
         int keynum;                        /// 结点中关键字的个数，ceil(ORDER/2)-1<= keynum <= ORDER-1   
         KeyType key[ORDER-1];                /// 关键字向量为key[0..keynum - 1]   
         struct BTNode* child[ORDER];        /// 孩子指针向量为child[0..keynum]   
         char isLeaf;                    /// 是否是叶子节点的标志   
     }BTNode;   
        
     typedef BTNode* BTree;  ///定义BTree   
        
     ///给定数据集data,创建BTree。   
     void BTree_create(BTree* tree, const KeyType* data, int length);   
    
     ///销毁BTree，释放内存空间。   
     void BTree_destroy(BTree* tree);   
        
     ///在BTree中插入关键字key。   
     void BTree_insert(BTree* tree, KeyType key);   
    
     ///在BTree中移除关键字key。   
     void BTree_remove(BTree* tree, KeyType key);   
    
     ///深度遍历BTree打印各层结点信息。   
     void BTree_print(const BTree tree, int layer);   
        
     /// 在BTree中查找关键字 key，   
     /// 成功时返回找到的节点的地址及 key 在其中的位置 *pos   
     /// 失败时返回 NULL 及查找失败时扫描到的节点位置 *pos   
     BTNode* BTree_search(const BTree tree, int key, int* pos);   
        
 #ifdef __cplusplus   
 }   
 #endif   
    
 #endif   

源文件：（提供B-Tree基本的基本操作的实现）

[cpp]view plaincopyprint? 
   
 /***************************************************************************  
     @coder:weedge E-mail:weege@126.com  
     @date:2011/08/27  
     @comment:  
         参考：http://www.cppblog.com/converse/archive/2009/10/13/98521.html  
         实现对order序(阶)的B-TREE结构基本操作的封装。  
         查找：search，插入：insert，删除：remove。  
         创建：create，销毁：destory，打印：print。  
 **********************************************************/   
 #include <stdlib.h>   
 #include <stdio.h>   
 #include <assert.h>   
 #include "btree.h"   
    
 //#define max(a, b) (((a) > (b)) ? (a) : (b))   
 #define cmp(a, b) ( ( ((a)-(b)) >= (0) ) ? (1) : (0) ) //比较a，b大小   
 #define DEBUG_BTREE   
    
    
 // 模拟向磁盘写入节点   
 void disk_write(BTNode* node)   
 {   
     int i;   
 //打印出结点中的全部元素，方便调试查看keynum之后的元素是否为0(即是否存在垃圾数据)；而不是keynum个元素。   
     printf("向磁盘写入节点");   
     for(i=0;i<ORDER-1;i++){   
         printf("%c",node->key[i]);   
     }   
     printf("\n");   
 }   
    
 // 模拟从磁盘读取节点   
 void disk_read(BTNode** node)   
 {   
     int i;   
 //打印出结点中的全部元素，方便调试查看keynum之后的元素是否为0(即是否存在垃圾数据)；而不是keynum个元素。   
     printf("向磁盘读取节点");   
     for(i=0;i<ORDER-1;i++){   
         printf("%c",(*node)->key[i]);   
     }   
     printf("\n");   
 }   
    
 // 按层次打印 B 树   
 void BTree_print(const BTree tree, int layer)   
 {   
     int i;   
     BTNode* node = tree;   
    
     if (node) {   
         printf("第 %d 层， %d node : ", layer, node->keynum);   
    
         //打印出结点中的全部元素，方便调试查看keynum之后的元素是否为0(即是否存在垃圾数据)；而不是keynum个元素。   
         for (i = 0; i < ORDER-1; ++i) {   
         //for (i = 0; i < node->keynum; ++i) {   
             printf("%c ", node->key[i]);   
         }   
    
         printf("\n");   
    
         ++layer;   
         for (i = 0 ; i <= node->keynum; i++) {   
             if (node->child[i]) {   
                 BTree_print(node->child[i], layer);   
             }   
         }   
     }   
     else {   
         printf("树为空。\n");   
     }   
 }   
    
 // 结点node内对关键字进行二分查找。   
 int binarySearch(BTNode* node, int low, int high, KeyType Fkey)   
 {   
     int mid;   
     while (low<=high)   
     {   
         mid = low + (high-low)/2;   
         if (Fkey<node->key[mid])   
         {   
             high = mid-1;   
         }   
         if (Fkey>node->key[mid])   
         {   
             low = mid+1;   
         }   
         if (Fkey==node->key[mid])   
         {   
             return mid;//返回下标。   
         }   
     }   
     return -1;//未找到返回-1.   
 }   
    
 //=======================================================insert=====================================   
    
 /***************************************************************************************  
    将分裂的结点中的一半元素给新建的结点，并且将分裂结点中的中间关键字元素上移至父节点中。  
    parent 是一个非满的父节点  
    node 是 tree 孩子表中下标为 index 的孩子节点，且是满的，需分裂。  
 *******************************************************************/   
 void BTree_split_child(BTNode* parent, int index, BTNode* node)   
 {   
     int i;   
     BTNode* newNode;   
 #ifdef DEBUG_BTREE   
     printf("BTree_split_child!\n");   
 #endif   
     assert(parent && node);   
    
    
     // 创建新节点，存储 node 中后半部分的数据   
     newNode = (BTNode*)calloc(sizeof(BTNode), 1);   
     if (!newNode) {   
         printf("Error! out of memory!\n");   
         return;   
     }   
    
     newNode->isLeaf = node->isLeaf;   
     newNode->keynum = BTree_D - 1;   
    
     // 拷贝 node 后半部分关键字,然后将node后半部分置为0。   
     for (i = 0; i < newNode->keynum; ++i){   
         newNode->key[i] = node->key[BTree_D + i];   
         node->key[BTree_D + i] = 0;   
     }   
    
     // 如果 node 不是叶子节点，拷贝 node 后半部分的指向孩子节点的指针，然后将node后半部分指向孩子节点的指针置为NULL。   
     if (!node->isLeaf) {   
         for (i = 0; i < BTree_D; i++) {   
             newNode->child[i] = node->child[BTree_D + i];   
             node->child[BTree_D + i] = NULL;   
         }   
     }   
    
     // 将 node 分裂出 newNode 之后，里面的数据减半   
     node->keynum = BTree_D - 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_D - 1];   
     ++parent->keynum;   
    
     node->key[BTree_D - 1] = 0;   
    
     // 写入磁盘   
      disk_write(parent);   
      disk_write(newNode);   
      disk_write(node);   
 }   
    
 void BTree_insert_nonfull(BTNode* node, KeyType key)   
 {   
     int i;   
     assert(node);   
    
     // 节点是叶子节点，直接插入   
     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 == (ORDER-1)) {   
             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, KeyType key)   
 {   
     BTNode* node;   
     BTNode* root = *tree;   
    
 #ifdef DEBUG_BTREE   
     printf("BTree_insert:\n");   
 #endif   
     // 树为空   
     if (NULL == root) {   
         root = (BTNode*)calloc(sizeof(BTNode), 1);   
         if (!root) {   
             printf("Error! out of memory!\n");   
             return;   
         }   
         root->isLeaf = 1;   
         root->keynum = 1;   
         root->key[0] = key;   
    
         *tree = root;   
    
         // 写入磁盘   
         disk_write(root);   
    
         return;   
     }   
    
     // 根节点已满，插入前需要进行分裂调整   
     if (root->keynum == (ORDER-1)) {   
         // 产生新节点当作根   
         node = (BTNode*)calloc(sizeof(BTNode), 1);   
         if (!node) {   
             printf("Error! out of memory!\n");   
             return;   
         }   
    
         *tree = node;   
         node->isLeaf = 0;   
         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);   
     }   
 }   
    
 //=================================================remove========================================   
 /***********************************************************************************  
 // 对 tree 中的节点 node 进行合并孩子节点处理.  
 // 注意：孩子节点的 keynum 必须均已达到下限，即均等于 BTree_D - 1  
 // 将 tree 中索引为 index  的 key 下移至左孩子结点中，  
 // 将 node 中索引为 index + 1 的孩子节点合并到索引为 index 的孩子节点中，右孩子合并到左孩子结点中。  
 // 并调相关的 key 和指针。  
 ***************************************************/   
 void BTree_merge_child(BTree* tree, BTNode* node, int index)   
 {   
     int i;   
     KeyType key;   
     BTNode *leftChild, *rightChild;   
 #ifdef DEBUG_BTREE   
     printf("BTree_merge_child!\n");   
 #endif   
     assert(tree && node && index >= 0 && index < node->keynum);   
    
    
     key = node->key[index];   
     leftChild = node->child[index];   
     rightChild = node->child[index + 1];   
    
     assert(leftChild && leftChild->keynum == BTree_D - 1   
         && rightChild && rightChild->keynum == BTree_D - 1);   
    
     // 将 node中关键字下标为index 的 key 下移至左孩子结点中，该key所对应的右孩子结点指向node的右孩子结点中的第一个孩子。   
     leftChild->key[leftChild->keynum] = key;   
     leftChild->child[leftChild->keynum + 1] = rightChild->child[0];   
     ++leftChild->keynum;   
    
     // 右孩子的元素合并到左孩子结点中。   
     for (i = 0; i < rightChild->keynum; ++i) {   
         leftChild->key[leftChild->keynum] = rightChild->key[i];   
         leftChild->child[leftChild->keynum + 1] = rightChild->child[i + 1];   
         ++leftChild->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 = leftChild;   
         }   
    
         free(node);   
         node = NULL;   
     }   
    
     free(rightChild);   
     rightChild = NULL;   
 }   
    
 void BTree_recursive_remove(BTree* tree, KeyType key)   
 {   
     // B-数的保持条件之一：   
     // 非根节点的内部节点的关键字数目不能少于 BTree_D - 1   
    
     int i, j, index;   
     BTNode *root = *tree;   
     BTNode *node = root;   
    
     if (!root) {   
         printf("Failed to remove %c, it is not in the tree!\n", key);   
         return;   
     }   
    
     // 结点中找key。   
     index = 0;   
     while (index < node->keynum && key > node->key[index]) {   
         ++index;   
     }   
    
 /*======================含有key的当前结点时的情况====================  
 node:  
 index of Key:            i-1  i  i+1  
                         +---+---+---+---+  
                           *  key   *  
                     +---+---+---+---+---+  
                            /     \  
 index of Child:           i      i+1  
                          /         \  
                     +---+---+      +---+---+  
                       *   *           *   *     
                 +---+---+---+  +---+---+---+  
                     leftChild     rightChild  
 ============================================================*/   
     /*一、结点中找到了关键字key的情况.*/   
     if (index < node->keynum && node->key[index] == key) {   
         BTNode *leftChild, *rightChild;   
         KeyType leftKey, rightKey;   
         /* 1，所在节点是叶子节点，直接删除*/   
         if (node->isLeaf) {   
             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;   
    
             if (node->keynum == 0) {   
                 assert(node == *tree);   
                 free(node);   
                 *tree = NULL;   
             }   
    
             return;   
         }   
         /*2.选择脱贫致富的孩子结点。*/   
         // 2a，选择相对富有的左孩子结点。   
         // 如果位于 key 前的左孩子结点的 key 数目 >= BTree_D，   
         // 在其中找 key 的左孩子结点的最后一个元素上移至父节点key的位置。   
         // 然后在左孩子节点中递归删除元素leftKey。   
         else if (node->child[index]->keynum >= BTree_D) {   
             leftChild = node->child[index];   
             leftKey = leftChild->key[leftChild->keynum - 1];   
             node->key[index] = leftKey;   
    
             BTree_recursive_remove(&leftChild, leftKey);   
         }   
         // 2b，选择相对富有的右孩子结点。   
         // 如果位于 key 后的右孩子结点的 key 数目 >= BTree_D，   
         // 在其中找 key 的右孩子结点的第一个元素上移至父节点key的位置   
         // 然后在右孩子节点中递归删除元素rightKey。   
         else if (node->child[index + 1]->keynum >= BTree_D) {   
             rightChild = node->child[index + 1];   
             rightKey = rightChild->key[0];   
             node->key[index] = rightKey;   
    
             BTree_recursive_remove(&rightChild, rightKey);   
         }   
         /*左右孩子结点都刚脱贫。删除前需要孩子结点的合并操作*/   
         // 2c，左右孩子结点只包含 BTree_D - 1 个节点，   
         // 合并是将 key 下移至左孩子节点，并将右孩子节点合并到左孩子节点中，   
         // 删除右孩子节点，在父节点node中移除 key 和指向右孩子节点的指针，   
         // 然后在合并了的左孩子节点中递归删除元素key。   
         else if (node->child[index]->keynum == BTree_D - 1   
             && node->child[index + 1]->keynum == BTree_D - 1){   
             leftChild = node->child[index];   
    
             BTree_merge_child(tree, node, index);   
    
             // 在合并了的左孩子节点中递归删除 key   
             BTree_recursive_remove(&leftChild, key);   
         }   
     }   
    
 /*======================未含有key的当前结点时的情况====================  
 node:  
 index of Key:            i-1  i  i+1  
                         +---+---+---+---+  
                           *  keyi *  
                     +---+---+---+---+---+  
                        /    |    \  
 index of Child:      i-1    i     i+1  
                      /      |       \  
             +---+---+   +---+---+      +---+---+  
              *   *        *   *          *   *     
         +---+---+---+   +---+---+---+  +---+---+---+  
         leftSibling       Child        rightSibling   
 ============================================================*/   
     /*二、结点中未找到了关键字key的情况.*/   
     else {   
         BTNode *leftSibling, *rightSibling, *child;   
         // 3. key 不在内节点 node 中，则应当在某个包含 key 的子节点中。   
         //  key < node->key[index], 所以 key 应当在孩子节点 node->child[index] 中   
         child = node->child[index];   
         if (!child) {   
             printf("Failed to remove %c, it is not in the tree!\n", key);   
             return;   
         }   
         /*所需查找的该孩子结点刚脱贫的情况*/   
         if (child->keynum == BTree_D - 1) {   
             leftSibling = NULL;   
             rightSibling = NULL;   
    
             if (index - 1 >= 0) {   
                 leftSibling = node->child[index - 1];   
             }   
    
             if (index + 1 <= node->keynum) {   
                 rightSibling = node->child[index + 1];   
             }   
             /*选择致富的相邻兄弟结点。*/   
             // 3a，如果所在孩子节点相邻的兄弟节点中有节点至少包含 BTree_D 个关键字   
             // 将 node 的一个关键字key[index]下移到 child 中，将相对富有的相邻兄弟节点中一个关键字上移到   
             // node 中，然后在 child 孩子节点中递归删除 key。   
             if ((leftSibling && leftSibling->keynum >= BTree_D)   
                 || (rightSibling && rightSibling->keynum >= BTree_D)) {   
                 int richR = 0;   
                 if(rightSibling) richR = 1;   
                 if(leftSibling && rightSibling) {   
                     richR = cmp(rightSibling->keynum,leftSibling->keynum);   
                 }   
                 if (rightSibling && rightSibling->keynum >= BTree_D && richR) {   
                     //相邻右兄弟相对富有，则该孩子先向父节点借一个元素，右兄弟中的第一个元素上移至父节点所借位置，并进行相应调整。   
                     child->key[child->keynum] = node->key[index];   
                     child->child[child->keynum + 1] = rightSibling->child[0];   
                     ++child->keynum;   
    
                     node->key[index] = rightSibling->key[0];   
    
                     for (j = 0; j < rightSibling->keynum - 1; ++j) {//元素前移   
                         rightSibling->key[j] = rightSibling->key[j + 1];   
                         rightSibling->child[j] = rightSibling->child[j + 1];   
                     }   
                     rightSibling->key[rightSibling->keynum-1] = 0;   
                     rightSibling->child[rightSibling->keynum-1] = rightSibling->child[rightSibling->keynum];   
                     rightSibling->child[rightSibling->keynum] = NULL;   
                     --rightSibling->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] = leftSibling->child[leftSibling->keynum];   
                     child->key[0] = node->key[index - 1];   
                     ++child->keynum;   
    
                     node->key[index - 1] = leftSibling->key[leftSibling->keynum - 1];   
    
                     leftSibling->key[leftSibling->keynum - 1] = 0;   
                     leftSibling->child[leftSibling->keynum] = NULL;   
    
                     --leftSibling->keynum;   
                 }   
             }   
             /*相邻兄弟结点都刚脱贫。删除前需要兄弟结点的合并操作,*/   
             // 3b, 如果所在孩子节点相邻的兄弟节点都只包含 BTree_D - 1 个关键字，   
             // 将 child 与其一相邻节点合并，并将 node 中的一个关键字下降到合并节点中，   
             // 再在 node 中删除那个关键字和相关指针，若 node 的 key 为空，删之，并调整根为合并结点。   
             // 最后，在相关孩子节点child中递归删除 key。   
             else if ((!leftSibling || (leftSibling && leftSibling->keynum == BTree_D - 1))   
                 && (!rightSibling || (rightSibling && rightSibling->keynum == BTree_D - 1))) {   
                 if (leftSibling && leftSibling->keynum == BTree_D - 1) {   
    
                     BTree_merge_child(tree, node, index - 1);//node中的右孩子元素合并到左孩子中。   
    
                     child = leftSibling;   
                 }   
    
                 else if (rightSibling && rightSibling->keynum == BTree_D - 1) {   
    
                     BTree_merge_child(tree, node, index);//node中的右孩子元素合并到左孩子中。   
                 }   
             }   
         }   
    
         BTree_recursive_remove(&child, key);//调整后，在key所在孩子结点中继续递归删除key。   
     }   
 }   
    
 void BTree_remove(BTree* tree, KeyType key)   
 {   
 #ifdef DEBUG_BTREE   
     printf("BTree_remove:\n");   
 #endif   
     if (*tree==NULL)   
     {      
         printf("BTree is NULL!\n");   
         return;   
     }   
    
     BTree_recursive_remove(tree, key);   
 }   
    
 //=====================================search====================================   
    
 BTNode* BTree_recursive_search(const BTree tree, KeyType key, int* pos)   
 {   
     int i = 0;   
    
     while (i < tree->keynum && key > tree->key[i]) {   
         ++i;   
     }   
    
     // Find the key.   
     if (i < tree->keynum && tree->key[i] == key) {   
         *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_recursive_search(tree->child[i], key, pos);   
 }   
    
 BTNode* BTree_search(const BTree tree, KeyType key, int* pos)   
 {   
 #ifdef DEBUG_BTREE   
     printf("BTree_search:\n");   
 #endif   
     if (!tree) {   
         printf("BTree is NULL!\n");   
         return NULL;   
     }   
     *pos = -1;   
     return BTree_recursive_search(tree,key,pos);   
 }   
    
 //===============================create===============================   
 void BTree_create(BTree* tree, const KeyType* data, int length)   
 {   
     int i, pos = -1;   
     assert(tree);   
    
 #ifdef DEBUG_BTREE   
     printf("\n 开始创建 B-树，关键字为:\n");   
     for (i = 0; i < length; i++) {   
         printf(" %c ", data[i]);   
     }   
     printf("\n");   
 #endif   
    
     for (i = 0; i < length; i++) {   
 #ifdef DEBUG_BTREE   
         printf("\n插入关键字 %c:\n", data[i]);   
 #endif   
    
         BTree_search(*tree,data[i],&pos);//树的递归搜索。   
         if (pos!=-1)   
         {   
             printf("this key %c is in the B-tree,not to insert.\n",data[i]);   
         }else{   
             BTree_insert(tree, data[i]);//插入元素到BTree中。   
         }   
    
 #ifdef DEBUG_BTREE   
         BTree_print(*tree,1);//树的深度遍历,从第一层开始。   
 #endif   
     }   
    
     printf("\n");   
 }   
 //===============================destroy===============================   
 void BTree_destroy(BTree* tree)   
 {   
     int i;   
     BTNode* node = *tree;   
    
     if (node) {   
         for (i = 0; i <= node->keynum; i++) {   
             BTree_destroy(&node->child[i]);   
         }   
    
         free(node);   
     }   
    
     *tree = NULL;   
 }   

测试文件：（测试B-Tree基本的操作接口)

[cpp]view plaincopyprint? 
   
 /***************************************************************************  
     @coder:weedge E-mail:weege@126.com  
     @date:2011/08/28  
     @comment:  
         测试order序(阶)的B-TREE结构基本操作。  
         查找：search，插入：insert，删除：remove。  
         创建：create，销毁：destory，打印：print。  
 **********************************************************/   
    
 #include <stdio.h>   
 #include "btree.h"   
    
 void test_BTree_search(BTree tree, KeyType 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, KeyType key)   
 {   
     printf("\n移除关键字 %c \n", key);   
     BTree_remove(tree, key);   
     BTree_print(*tree);   
     printf("\n");   
 }   
    
 void test_btree()   
 {   
    
     KeyType array[] = {   
         'G','G', 'M', 'P', 'X', 'A', 'C', 'D', 'E', 'J', 'K',   
         'N', 'O', 'R', 'S', 'T', 'U', 'V', 'Y', 'Z', 'F', 'X'   
     };   
     const int length = sizeof(array)/sizeof(KeyType);   
     BTree tree = NULL;   
     BTNode* node = NULL;   
     int pos = -1;   
     KeyType key1 = 'R';        // in the tree.   
     KeyType 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);   
    
     // 移除不在B树中的元素   
     test_BTree_remove(&tree, key2);   
     printf("\n");   
    
     // 插入关键字   
     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);   
    
     key2 = 'O';   
     test_BTree_remove(&tree, key2);   
     test_BTree_search(tree, key2);   
    
     key2 = 'V';   
     test_BTree_remove(&tree, key2);   
     test_BTree_search(tree, key2);   
    
     key2 = 'R';   
     test_BTree_remove(&tree, key2);   
     test_BTree_search(tree, key2);   
    
     key2 = 'U';   
     test_BTree_remove(&tree, key2);   
     test_BTree_search(tree, key2);   
    
     key2 = 'T';   
     test_BTree_remove(&tree, key2);   
     test_BTree_search(tree, key2);   
    
     key2 = 'N';   
     test_BTree_remove(&tree, key2);   
     test_BTree_search(tree, key2);   
     key2 = 'S';   
     test_BTree_remove(&tree, key2);   
     test_BTree_search(tree, key2);   
     key2 = 'Y';   
     test_BTree_remove(&tree, key2);   
     test_BTree_search(tree, key2);   
     key2 = 'F';   
     test_BTree_remove(&tree, key2);   
     test_BTree_search(tree, key2);   
     key2 = 'Z';   
     test_BTree_remove(&tree, key2);   
     test_BTree_search(tree, key2);   
    
     // 销毁   
     BTree_destroy(&tree);   
 }   
    
 int main()   
 {   
     test_btree();   
    
     return 0;   
 }   

另外参考《Data.structures.and.Program.Design.in.Cpp》-Section 11.3:EXTERNALSEARCHING:B-TREES的讲解实现，这边书个人认为比较经典，如果对数据结构和算法比较感兴趣的话，可以作为参考读物，不错的，根据数据结构上的操作与程序上的实现相结合，讲的很细。这本书好像没有中文版的，即使有，也推荐看原版吧，毕竟写代码都是用英文字符，实现也比较贴切易懂。去网上找这本书的资料还挺多的。而且国内有些大学也参考这本书讲解数据结构和算法。比如：http://sist.sysu.edu.cn/~isslxm/DSA/CS09/。

头文件：（采用C++模板（template）来实现B-Tree基本的操作接口)

[cpp]view plaincopyprint? 
   
 /***************************************************************************  
     @editer:weedge E-mail:weege@126.com  
     @date:2011/08/27  
     @comment:  
         Data.structures.and.Program.Design.in.Cpp  
         Section 11.3:EXTERNALSEARCHING:B-TREES  
         采用泛型编程（模板template），Record为关键字类型，order为序(阶)，  
         实现对order序(阶)的B-TREE结构基本操作的封装。  
         查找：search，插入：insert，删除：remove。  
 **********************************************************/   
    
 #ifndef B_Tree_H_   
 #define B_Tree_H_   
    
 enum Error_code{overflow=-2,duplicate_error=-1,not_present=0,success=1};   
    
 template <class Record, int order>   
 struct B_node {   
 ///  data members:   
    int count;   
    Record data[order - 1];   
    B_node<Record, order> *branch[order];///在大多数应用中，这些指针被不同的磁盘中块(block)的地址代替。   
 ///  constructor:   
    B_node();   
 };   
    
 template <class Record, int order>   
 class B_tree {   
 public:     
     ////*  Add public methods. */   
    
     Error_code search_tree(Record &target);   
    
     Error_code insert(const Record &new_entry);   
    
     Error_code remove(const Record &target);   
    
 protected:   
     ////*  data members */   
        
     ////*  Add protected auxiliary functions here in order to inherit for subclass. */   
     ///=============================search=========================================   
    
     Error_code recursive_search_tree(B_node<Record, order> *current, Record &target);   
        
     Error_code search_node(B_node<Record, order> *current, const Record &target, int &position);   
    
     ///=============================insert=========================================   
    
     Error_code push_down(B_node<Record, order> *current,const Record &new_entry,   
         Record &median,B_node<Record, order> *&right_branch);   
        
     void push_in(B_node<Record, order> *current, const Record &entry,    
         B_node<Record, order> *right_branch, int position);   
        
     void split_node(B_node<Record, order> *current,   const Record &extra_entry, B_node<Record, order> *extra_branch,   
         int position, B_node<Record, order> *&right_half, Record &median);   
    
     ///==============================remove========================================   
    
     Error_code recursive_remove(B_node<Record, order> *current, const Record &target);   
        
     void remove_data(B_node<Record, order> *current, int position);   
    
     void copy_in_predecessor(B_node<Record, order> *current, int position);   
        
     void restore(B_node<Record, order> *current,int position);   
        
     void move_left(B_node<Record, order> *current, int position);   
        
     void move_right(B_node<Record, order> *current,int position);   
        
     void combine(B_node<Record, order> *current, int position);   
    
 private:    
     ////*  data members */   
     B_node<Record, order> *root;   
    
     ////*  Add private auxiliary functions here. */   
 };   
    
 #endif //end B_Tree_H_   

原文件：（实现B-Tree基本的基本操作)

[cpp]view plaincopyprint? 
   
 /***************************************************************************  
     @editor:weedge E-mail:weege@126.com  
     @date:2011/08/27  
     @comment:  
         Data.structures.and.Program.Design.in.Cpp  
         Section 11.3:EXTERNALSEARCHING:B-TREES  
         采用泛型编程（模板template），  
         实现对B-TREE结构基本操作的封装。  
         查找：search，插入：insert，删除：remove。  
 **********************************************************/   
 #include "B_Tree.h"   
    
 template <class Record, int order>   
 Error_code B_tree<Record, order>::search_tree(Record &target)   
 /*  
 Post: If there is an entry in the B-tree whose key matches that in target,  
       the parameter target is replaced by the corresponding Record from  
       the B-tree and a code of success is returned.  Otherwise  
       a code of not_present is returned.  
 Uses: recursive_search_tree  
 */   
 {   
    return recursive_search_tree(root, target);   
 }   
    
    
 template <class Record, int order>   
 Error_code B_tree<Record, order>::recursive_search_tree(   
            B_node<Record, order> *current, Record &target)   
 /*  
 Pre:  current is either NULL or points to a subtree of the B_tree.  
 Post: If the Key of target is not in the subtree, a code of not_present  
       is returned. Otherwise, a code of success is returned and  
       target is set to the corresponding Record of the subtree.  
 Uses: recursive_search_tree recursively and search_node  
 */   
 {   
    Error_code result = not_present;   
    int position;   
    if (current != NULL) {   
       result = search_node(current, target, position);   
       if (result == not_present)   
          result = recursive_search_tree(current->branch[position], target);   
       else   
          target = current->data[position];   
    }   
    return result;   
 }   
    
    
 template <class Record, int order>   
 Error_code B_tree<Record, order>::search_node(   
    B_node<Record, order> *current, const Record &target, int &position)   
 /*  
 Pre:  current points to a node of a B_tree.  
 Post: If the Key of target is found in *current, then a code of  
       success is returned, the parameter position is set to the index  
       of target, and the corresponding Record is copied to  
       target.  Otherwise, a code of not_present is returned, and  
       position is set to the branch index on which to continue the search.  
 Uses: Methods of class Record.  
 */   
 {   
    position = 0;   
    while (position < current->count && target > current->data[position])   
       position++;         //  Perform a sequential search through the keys.   
    if (position < current->count && target == current->data[position])   
       return success;   
    else   
       return not_present;   
 }   
    
    
 template <class Record, int order>   
 Error_code B_tree<Record, order>::insert(const Record &new_entry)   
 /*  
 Post: If the Key of new_entry is already in the B_tree,  
       a code of duplicate_error is returned.  
       Otherwise, a code of success is returned and the Record new_entry  
       is inserted into the B-tree in such a way that the properties of a B-tree  
       are preserved.  
 Uses: Methods of struct B_node and the auxiliary function push_down.  
 */   
 {   
    Record median;   
    B_node<Record, order> *right_branch, *new_root;   
    Error_code result = push_down(root, new_entry, median, right_branch);   
    
    if (result == overflow) {  //  The whole tree grows in height.   
                               //  Make a brand new root for the whole B-tree.   
       new_root = new B_node<Record, order>;   
       new_root->count = 1;   
       new_root->data[0] = median;   
       new_root->branch[0] = root;   
       new_root->branch[1] = right_branch;   
       root = new_root;   
       result = success;   
    }   
    return result;   
 }   
    
    
 template <class Record, int order>   
 Error_code B_tree<Record, order>::push_down(   
                  B_node<Record, order> *current,   
                  const Record &new_entry,   
                  Record &median,   
                  B_node<Record, order> *&right_branch)   
 /*  
 Pre:  current is either NULL or points to a node of a B_tree.  
 Post: If an entry with a Key matching that of new_entry is in the subtree  
       to which current points, a code of duplicate_error is returned.  
       Otherwise, new_entry is inserted into the subtree: If this causes the  
       height of the subtree to grow, a code of overflow is returned, and the  
       Record median is extracted to be reinserted higher in the B-tree,  
       together with the subtree right_branch on its right.  
       If the height does not grow, a code of success is returned.  
 Uses: Functions push_down (called recursively), search_node,  
       split_node, and push_in.  
 */   
 {   
    Error_code result;   
    int position;   
    if (current == NULL) { //  Since we cannot insert in an empty tree, the recursion terminates.   
       median = new_entry;   
       right_branch = NULL;   
       result = overflow;   
    }   
    else {   //   Search the current node.   
       if (search_node(current, new_entry, position) == success)   
          result = duplicate_error;   
       else {   
          Record extra_entry;   
          B_node<Record, order> *extra_branch;   
          result = push_down(current->branch[position], new_entry,   
                             extra_entry, extra_branch);   
          if (result == overflow) {  //  Record extra_entry now must be added to current   
             if (current->count < order - 1) {   
                result = success;   
                push_in(current, extra_entry, extra_branch, position);   
             }   
    
             else split_node(current, extra_entry, extra_branch, position,   
                             right_branch, median);   
             //  Record median and its right_branch will go up to a higher node.   
          }   
       }   
    }   
    return result;   
 }   
    
    
 template <class Record, int order>   
 void B_tree<Record, order>::push_in(B_node<Record, order> *current,   
    const Record &entry, B_node<Record, order> *right_branch, int position)   
 /*  
 Pre:  current points to a node of a B_tree.  The node *current is not full  
       and entry belongs in *current at index position.  
 Post: entry has been inserted along with its right-hand branch  
       right_branch into *current at index position.  
 */   
 {   
    for (int i = current->count; i > position; i--) {  //  Shift all later data to the right.   
       current->data[i] = current->data[i - 1];   
       current->branch[i + 1] = current->branch[i];   
    }   
    current->data[position] = entry;   
    current->branch[position + 1] = right_branch;   
    current->count++;   
 }   
    
    
 template <class Record, int order>   
 void B_tree<Record, order>::split_node(   
    B_node<Record, order> *current,    //  node to be split   
    const Record &extra_entry,          //  new entry to insert   
    B_node<Record, order> *extra_branch,//  subtree on right of extra_entry   
    int position,                  //  index in node where extra_entry goes   
    B_node<Record, order> *&right_half, //  new node for right half of entries   
    Record &median)                     //  median entry (in neither half)   
 /*  
 Pre:  current points to a node of a B_tree.  
       The node *current is full, but if there were room, the record  
       extra_entry with its right-hand pointer extra_branch would belong  
       in *current at position position, 0 <= position < order.  
 Post: The node *current with extra_entry and pointer extra_branch at  
       position position are divided into nodes *current and *right_half  
       separated by a Record median.  
 Uses: Methods of struct B_node, function push_in.  
 */   
 {   
    right_half = new B_node<Record, order>;   
    int mid = order/2;  //  The entries from mid on will go to right_half.   
    if (position <= mid) {   //  First case:  extra_entry belongs in left half.   
       for (int i = mid; i < order - 1; i++) {  //  Move entries to right_half.   
          right_half->data[i - mid] = current->data[i];   
          right_half->branch[i + 1 - mid] = current->branch[i + 1];   
       }   
       current->count = mid;   
       right_half->count = order - 1 - mid;   
       push_in(current, extra_entry, extra_branch, position);   
    }   
    else {  //  Second case:  extra_entry belongs in right half.   
       mid++;      //  Temporarily leave the median in left half.   
       for (int i = mid; i < order - 1; i++) {  //  Move entries to right_half.   
          right_half->data[i - mid] = current->data[i];   
          right_half->branch[i + 1 - mid] = current->branch[i + 1];   
       }   
       current->count = mid;   
       right_half->count = order - 1 - mid;   
       push_in(right_half, extra_entry, extra_branch, position - mid);   
    }   
       median = current->data[current->count - 1]; //  Remove median from left half.   
       right_half->branch[0] = current->branch[current->count];   
       current->count--;   
 }   
    
    
 template <class Record, int order>   
 Error_code B_tree<Record, order>::remove(const Record &target)   
 /*  
 Post: If a Record with Key matching that of target belongs to the  
       B_tree, a code of success is returned and the corresponding node  
       is removed from the B-tree.  Otherwise, a code of not_present  
       is returned.  
 Uses: Function recursive_remove  
 */   
 {   
    Error_code result;   
    result = recursive_remove(root, target);   
    if (root != NULL && root->count == 0) {  //  root is now empty.   
       B_node<Record, order> *old_root = root;   
       root = root->branch[0];   
       delete old_root;   
    }   
    return result;   
 }   
    
    
 template <class Record, int order>   
 Error_code B_tree<Record, order>::recursive_remove(   
    B_node<Record, order> *current, const Record &target)   
 /*  
 Pre:  current is either NULL or  
       points to the root node of a subtree of a B_tree.  
 Post: If a Record with Key matching that of target belongs to the subtree,  
       a code of success is returned and the corresponding node is removed  
       from the subtree so that the properties of a B-tree are maintained.  
       Otherwise, a code of not_present is returned.  
 Uses: Functions search_node, copy_in_predecessor,  
       recursive_remove (recursively), remove_data, and restore.  
 */   
 {   
    Error_code result;   
    int position;   
    if (current == NULL) result = not_present;   
    else {   
       if (search_node(current, target, position) == success) {  //  The target is in the current node.   
          result = success;   
          if (current->branch[position] != NULL) {     //  not at a leaf node   
             copy_in_predecessor(current, position);   
    
             recursive_remove(current->branch[position],   
                              current->data[position]);   
          }   
          else remove_data(current, position);     //  Remove from a leaf node.   
       }   
       else result = recursive_remove(current->branch[position], target);   
       if (current->branch[position] != NULL)   
          if (current->branch[position]->count < (order - 1) / 2)   
             restore(current, position);   
    }   
    return result;   
 }   
    
    
 template <class Record, int order>   
 void B_tree<Record, order>::remove_data(B_node<Record, order> *current,   
                                         int position)   
 /*  
 Pre:  current points to a leaf node in a B-tree with an entry at position.  
 Post: This entry is removed from *current.  
 */   
 {   
    for (int i = position; i < current->count - 1; i++)   
       current->data[i] = current->data[i + 1];   
    current->count--;   
 }   
    
    
 template <class Record, int order>   
 void B_tree<Record, order>::copy_in_predecessor(   
                     B_node<Record, order> *current, int position)   
 /*  
 Pre:  current points to a non-leaf node in a B-tree with an entry at position.  
 Post: This entry is replaced by its immediate predecessor under order of keys.  
 */   
 {   
    B_node<Record, order> *leaf = current->branch[position];  //   First go left from the current entry.   
    while (leaf->branch[leaf->count] != NULL)   
       leaf = leaf->branch[leaf->count]; //   Move as far rightward as possible.   
    current->data[position] = leaf->data[leaf->count - 1];   
 }   
    
    
 template <class Record, int order>   
 void B_tree<Record, order>::restore(B_node<Record, order> *current,   
                                     int position)   
 /*  
 Pre:  current points to a non-leaf node in a B-tree; the node to which  
       current->branch[position] points has one too few entries.  
 Post: An entry is taken from elsewhere to restore the minimum number of  
       entries in the node to which current->branch[position] points.  
 Uses: move_left, move_right, combine.  
 */   
 {   
    if (position == current->count)   //  case:  rightmost branch   
       if (current->branch[position - 1]->count > (order - 1) / 2)   
          move_right(current, position - 1);   
       else   
          combine(current, position);   
    else if (position == 0)       //  case: leftmost branch   
       if (current->branch[1]->count > (order - 1) / 2)   
          move_left(current, 1);   
       else   
          combine(current, 1);   
    else                          //  remaining cases: intermediate branches   
       if (current->branch[position - 1]->count > (order - 1) / 2)   
          move_right(current, position - 1);   
       else if (current->branch[position + 1]->count > (order - 1) / 2)   
          move_left(current, position + 1);   
       else   
          combine(current, position);   
 }   
    
    
 template <class Record, int order>   
 void B_tree<Record, order>::move_left(B_node<Record, order> *current,   
                                       int position)   
 /*  
 Pre:  current points to a node in a B-tree with more than the minimum  
       number of entries in branch position and one too few entries in branch  
       position - 1.  
 Post: The leftmost entry from branch position has moved into  
       current, which has sent an entry into the branch position - 1.  
 */   
 {   
    B_node<Record, order> *left_branch = current->branch[position - 1],   
                          *right_branch = current->branch[position];   
    left_branch->data[left_branch->count] = current->data[position - 1];  //  Take entry from the parent.   
    left_branch->branch[++left_branch->count] = right_branch->branch[0];   
    current->data[position - 1] = right_branch->data[0];  //   Add the right-hand entry to the parent.   
    right_branch->count--;   
    for (int i = 0; i < right_branch->count; i++) {   //  Move right-hand entries to fill the hole.   
       right_branch->data[i] = right_branch->data[i + 1];   
       right_branch->branch[i] = right_branch->branch[i + 1];   
    }   
    right_branch->branch[right_branch->count] =   
       right_branch->branch[right_branch->count + 1];   
 }   
    
    
 template <class Record, int order>   
 void B_tree<Record, order>::move_right(B_node<Record, order> *current,   
                                        int position)   
 /*  
 Pre:  current points to a node in a B-tree with more than the minimum  
       number of entries in branch position and one too few entries  
       in branch position + 1.  
 Post: The rightmost entry from branch position has moved into  
       current, which has sent an entry into the branch position + 1.  
 */   
 {   
    B_node<Record, order> *right_branch = current->branch[position + 1],   
                          *left_branch = current->branch[position];   
    right_branch->branch[right_branch->count + 1] =   
       right_branch->branch[right_branch->count];   
    for (int i = right_branch->count ; i > 0; i--) {  //  Make room for new entry.   
       right_branch->data[i] = right_branch->data[i - 1];   
       right_branch->branch[i] = right_branch->branch[i - 1];   
    }   
    right_branch->count++;   
    right_branch->data[0] = current->data[position]; //  Take entry from parent.   
    right_branch->branch[0] = left_branch->branch[left_branch->count--];   
    current->data[position] = left_branch->data[left_branch->count];   
 }   
    
    
 template <class Record, int order>   
 void B_tree<Record, order>::combine(B_node<Record, order> *current,   
                                     int position)   
 /*  
 Pre:  current points to a node in a B-tree with entries in the branches  
       position and position - 1, with too few to move entries.  
 Post: The nodes at branches position - 1 and position have been combined  
       into one node, which also includes the entry formerly in current at  
       index  position - 1.  
 */   
 {   
    int i;   
    B_node<Record, order> *left_branch = current->branch[position - 1],   
                          *right_branch = current->branch[position];   
    left_branch->data[left_branch->count] = current->data[position - 1];   
    left_branch->branch[++left_branch->count] = right_branch->branch[0];   
    for (i = 0; i < right_branch->count; i++) {   
       left_branch->data[left_branch->count] = right_branch->data[i];   
       left_branch->branch[++left_branch->count] =   
                                         right_branch->branch[i + 1];   
    }   
    current->count--;   
    for (i = position - 1; i < current->count; i++) {   
       current->data[i] = current->data[i + 1];   
       current->branch[i + 1] = current->branch[i + 2];   
    }   
    delete right_branch;   
 }   

测试文件：（待写)

//原文地址

B-tree的代码实现 - c / c++ 版本

热门文章

最新文章

相关课程

相关电子书