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

2021-07-17 03:11:32

//高大上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?
  1. /*************************************************************************** 
  2.     @coder:weedge E-mail:weege@126.com 
  3.     @date:2011/08/27 
  4.     @comment: 
  5.         参考：http://www.cppblog.com/converse/archive/2009/10/13/98521.html 
  6.         实现对order序(阶)的B-TREE结构基本操作的封装。 
  7.         查找：search，插入：insert，删除：remove。 
  8.         创建：create，销毁：destory，打印：print。 
  9. **********************************************************/  
  10. #ifndef BTREE_H  
  11. #define BTREE_H  
  12.   
  13. #ifdef __cplusplus  
  14. extern "C" {  
  15. #endif  
  16.   
  17. ////* 定义m序(阶)B 树的最小度数BTree_D=ceil(m/2)*/  
  18. /// 在这里定义每个节点中关键字的最大数目为:2 * BTree_D - 1，即序(阶)：2 * BTree_D.  
  19. #define BTree_D        2  
  20. #define ORDER        (BTree_D * 2) //定义为4阶B-tree,2-3-4树。(偶序)  
  21. //#define ORDER        (BTree_D * 2-1)//最简单为3阶B-tree,2-3树。(奇序)  
  22.   
  23.     typedef int KeyType;  
  24.     typedef struct BTNode{  
  25.         int keynum;                        /// 结点中关键字的个数，ceil(ORDER/2)-1<= keynum <= ORDER-1  
  26.         KeyType key[ORDER-1];                /// 关键字向量为key[0..keynum - 1]  
  27.         struct BTNode* child[ORDER];        /// 孩子指针向量为child[0..keynum]  
  28.         char isLeaf;                    /// 是否是叶子节点的标志  
  29.     }BTNode;  
  30.       
  31.     typedef BTNode* BTree;  ///定义BTree  
  32.       
  33.     ///给定数据集data,创建BTree。  
  34.     void BTree_create(BTree* tree, const KeyType* data, int length);  
  35.   
  36.     ///销毁BTree，释放内存空间。  
  37.     void BTree_destroy(BTree* tree);  
  38.       
  39.     ///在BTree中插入关键字key。  
  40.     void BTree_insert(BTree* tree, KeyType key);  
  41.   
  42.     ///在BTree中移除关键字key。  
  43.     void BTree_remove(BTree* tree, KeyType key);  
  44.   
  45.     ///深度遍历BTree打印各层结点信息。  
  46.     void BTree_print(const BTree tree, int layer);  
  47.       
  48.     /// 在BTree中查找关键字 key，  
  49.     /// 成功时返回找到的节点的地址及 key 在其中的位置 *pos  
  50.     /// 失败时返回 NULL 及查找失败时扫描到的节点位置 *pos  
  51.     BTNode* BTree_search(const BTree tree, int key, int* pos);  
  52.       
  53. #ifdef __cplusplus  
  54. }  
  55. #endif  
  56.   
  57. #endif  

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

[cpp] view plaincopyprint?
  1. /*************************************************************************** 
  2.     @coder:weedge E-mail:weege@126.com 
  3.     @date:2011/08/27 
  4.     @comment: 
  5.         参考：http://www.cppblog.com/converse/archive/2009/10/13/98521.html 
  6.         实现对order序(阶)的B-TREE结构基本操作的封装。 
  7.         查找：search，插入：insert，删除：remove。 
  8.         创建：create，销毁：destory，打印：print。 
  9. **********************************************************/  
  10. #include <stdlib.h>  
  11. #include <stdio.h>  
  12. #include <assert.h>  
  13. #include "btree.h"  
  14.   
  15. //#define max(a, b) (((a) > (b)) ? (a) : (b))  
  16. #define cmp(a, b) ( ( ((a)-(b)) >= (0) ) ? (1) : (0) ) //比较a，b大小  
  17. #define DEBUG_BTREE  
  18.   
  19.   
  20. // 模拟向磁盘写入节点  
  21. void disk_write(BTNode* node)  
  22. {  
  23.     int i;  
  24. //打印出结点中的全部元素，方便调试查看keynum之后的元素是否为0(即是否存在垃圾数据)；而不是keynum个元素。  
  25.     printf("向磁盘写入节点");  
  26.     for(i=0;i<ORDER-1;i++){  
  27.         printf("%c",node->key[i]);  
  28.     }  
  29.     printf("\n");  
  30. }  
  31.   
  32. // 模拟从磁盘读取节点  
  33. void disk_read(BTNode** node)  
  34. {  
  35.     int i;  
  36. //打印出结点中的全部元素，方便调试查看keynum之后的元素是否为0(即是否存在垃圾数据)；而不是keynum个元素。  
  37.     printf("向磁盘读取节点");  
  38.     for(i=0;i<ORDER-1;i++){  
  39.         printf("%c",(*node)->key[i]);  
  40.     }  
  41.     printf("\n");  
  42. }  
  43.   
  44. // 按层次打印 B 树  
  45. void BTree_print(const BTree tree, int layer)  
  46. {  
  47.     int i;  
  48.     BTNode* node = tree;  
  49.   
  50.     if (node) {  
  51.         printf("第 %d 层， %d node : ", layer, node->keynum);  
  52.   
  53.         //打印出结点中的全部元素，方便调试查看keynum之后的元素是否为0(即是否存在垃圾数据)；而不是keynum个元素。  
  54.         for (i = 0; i < ORDER-1; ++i) {  
  55.         //for (i = 0; i < node->keynum; ++i) {  
  56.             printf("%c ", node->key[i]);  
  57.         }  
  58.   
  59.         printf("\n");  
  60.   
  61.         ++layer;  
  62.         for (i = 0 ; i <= node->keynum; i++) {  
  63.             if (node->child[i]) {  
  64.                 BTree_print(node->child[i], layer);  
  65.             }  
  66.         }  
  67.     }  
  68.     else {  
  69.         printf("树为空。\n");  
  70.     }  
  71. }  
  72.   
  73. // 结点node内对关键字进行二分查找。  
  74. int binarySearch(BTNode* node, int low, int high, KeyType Fkey)  
  75. {  
  76.     int mid;  
  77.     while (low<=high)  
  78.     {  
  79.         mid = low + (high-low)/2;  
  80.         if (Fkey<node->key[mid])  
  81.         {  
  82.             high = mid-1;  
  83.         }  
  84.         if (Fkey>node->key[mid])  
  85.         {  
  86.             low = mid+1;  
  87.         }  
  88.         if (Fkey==node->key[mid])  
  89.         {  
  90.             return mid;//返回下标。  
  91.         }  
  92.     }  
  93.     return -1;//未找到返回-1.  
  94. }  
  95.   
  96. //=======================================================insert=====================================  
  97.   
  98. /*************************************************************************************** 
  99.    将分裂的结点中的一半元素给新建的结点，并且将分裂结点中的中间关键字元素上移至父节点中。 
  100.    parent 是一个非满的父节点 
  101.    node 是 tree 孩子表中下标为 index 的孩子节点，且是满的，需分裂。 
  102. *******************************************************************/  
  103. void BTree_split_child(BTNode* parent, int index, BTNode* node)  
  104. {  
  105.     int i;  
  106.     BTNode* newNode;  
  107. #ifdef DEBUG_BTREE  
  108.     printf("BTree_split_child!\n");  
  109. #endif  
  110.     assert(parent && node);  
  111.   
  112.   
  113.     // 创建新节点，存储 node 中后半部分的数据  
  114.     newNode = (BTNode*)calloc(sizeof(BTNode), 1);  
  115.     if (!newNode) {  
  116.         printf("Error! out of memory!\n");  
  117.         return;  
  118.     }  
  119.   
  120.     newNode->isLeaf = node->isLeaf;  
  121.     newNode->keynum = BTree_D - 1;  
  122.   
  123.     // 拷贝 node 后半部分关键字,然后将node后半部分置为0。  
  124.     for (i = 0; i < newNode->keynum; ++i){  
  125.         newNode->key[i] = node->key[BTree_D + i];  
  126.         node->key[BTree_D + i] = 0;  
  127.     }  
  128.   
  129.     // 如果 node 不是叶子节点，拷贝 node 后半部分的指向孩子节点的指针，然后将node后半部分指向孩子节点的指针置为NULL。  
  130.     if (!node->isLeaf) {  
  131.         for (i = 0; i < BTree_D; i++) {  
  132.             newNode->child[i] = node->child[BTree_D + i];  
  133.             node->child[BTree_D + i] = NULL;  
  134.         }  
  135.     }  
  136.   
  137.     // 将 node 分裂出 newNode 之后，里面的数据减半  
  138.     node->keynum = BTree_D - 1;  
  139.   
  140.     // 调整父节点中的指向孩子的指针和关键字元素。分裂时父节点增加指向孩子的指针和关键元素。  
  141.     for (i = parent->keynum; i > index; --i) {  
  142.         parent->child[i + 1] = parent->child[i];  
  143.     }  
  144.   
  145.     parent->child[index + 1] = newNode;  
  146.   
  147.     for (i = parent->keynum - 1; i >= index; --i) {  
  148.         parent->key[i + 1] = parent->key[i];  
  149.     }  
  150.   
  151.     parent->key[index] = node->key[BTree_D - 1];  
  152.     ++parent->keynum;  
  153.   
  154.     node->key[BTree_D - 1] = 0;  
  155.   
  156.     // 写入磁盘  
  157.      disk_write(parent);  
  158.      disk_write(newNode);  
  159.      disk_write(node);  
  160. }  
  161.   
  162. void BTree_insert_nonfull(BTNode* node, KeyType key)  
  163. {  
  164.     int i;  
  165.     assert(node);  
  166.   
  167.     // 节点是叶子节点，直接插入  
  168.     if (node->isLeaf) {  
  169.         i = node->keynum - 1;  
  170.         while (i >= 0 && key < node->key[i]) {  
  171.             node->key[i + 1] = node->key[i];  
  172.             --i;  
  173.         }  
  174.   
  175.         node->key[i + 1] = key;  
  176.         ++node->keynum;  
  177.   
  178.         // 写入磁盘  
  179.         disk_write(node);  
  180.     }  
  181.   
  182.     // 节点是内部节点  
  183.     else {  
  184.         /* 查找插入的位置*/  
  185.         i = node->keynum - 1;  
  186.         while (i >= 0 && key < node->key[i]) {  
  187.             --i;  
  188.         }  
  189.   
  190.         ++i;  
  191.   
  192.         // 从磁盘读取孩子节点  
  193.         disk_read(&node->child[i]);  
  194.   
  195.         // 如果该孩子节点已满，分裂调整值  
  196.         if (node->child[i]->keynum == (ORDER-1)) {  
  197.             BTree_split_child(node, i, node->child[i]);  
  198.             // 如果待插入的关键字大于该分裂结点中上移到父节点的关键字，在该关键字的右孩子结点中进行插入操作。  
  199.             if (key > node->key[i]) {  
  200.                 ++i;  
  201.             }  
  202.         }  
  203.         BTree_insert_nonfull(node->child[i], key);  
  204.     }  
  205. }  
  206.   
  207. void BTree_insert(BTree* tree, KeyType key)  
  208. {  
  209.     BTNode* node;  
  210.     BTNode* root = *tree;  
  211.   
  212. #ifdef DEBUG_BTREE  
  213.     printf("BTree_insert:\n");  
  214. #endif  
  215.     // 树为空  
  216.     if (NULL == root) {  
  217.         root = (BTNode*)calloc(sizeof(BTNode), 1);  
  218.         if (!root) {  
  219.             printf("Error! out of memory!\n");  
  220.             return;  
  221.         }  
  222.         root->isLeaf = 1;  
  223.         root->keynum = 1;  
  224.         root->key[0] = key;  
  225.   
  226.         *tree = root;  
  227.   
  228.         // 写入磁盘  
  229.         disk_write(root);  
  230.   
  231.         return;  
  232.     }  
  233.   
  234.     // 根节点已满，插入前需要进行分裂调整  
  235.     if (root->keynum == (ORDER-1)) {  
  236.         // 产生新节点当作根  
  237.         node = (BTNode*)calloc(sizeof(BTNode), 1);  
  238.         if (!node) {  
  239.             printf("Error! out of memory!\n");  
  240.             return;  
  241.         }  
  242.   
  243.         *tree = node;  
  244.         node->isLeaf = 0;  
  245.         node->keynum = 0;  
  246.         node->child[0] = root;  
  247.   
  248.         BTree_split_child(node, 0, root);  
  249.   
  250.         BTree_insert_nonfull(node, key);  
  251.     }  
  252.   
  253.     // 根节点未满，在当前节点中插入 key  
  254.     else {  
  255.         BTree_insert_nonfull(root, key);  
  256.     }  
  257. }  
  258.   
  259. //=================================================remove========================================  
  260. /*********************************************************************************** 
  261. // 对 tree 中的节点 node 进行合并孩子节点处理. 
  262. // 注意：孩子节点的 keynum 必须均已达到下限，即均等于 BTree_D - 1 
  263. // 将 tree 中索引为 index  的 key 下移至左孩子结点中， 
  264. // 将 node 中索引为 index + 1 的孩子节点合并到索引为 index 的孩子节点中，右孩子合并到左孩子结点中。 
  265. // 并调相关的 key 和指针。 
  266. ***************************************************/  
  267. void BTree_merge_child(BTree* tree, BTNode* node, int index)  
  268. {  
  269.     int i;  
  270.     KeyType key;  
  271.     BTNode *leftChild, *rightChild;  
  272. #ifdef DEBUG_BTREE  
  273.     printf("BTree_merge_child!\n");  
  274. #endif  
  275.     assert(tree && node && index >= 0 && index < node->keynum);  
  276.   
  277.   
  278.     key = node->key[index];  
  279.     leftChild = node->child[index];  
  280.     rightChild = node->child[index + 1];  
  281.   
  282.     assert(leftChild && leftChild->keynum == BTree_D - 1  
  283.         && rightChild && rightChild->keynum == BTree_D - 1);  
  284.   
  285.     // 将 node中关键字下标为index 的 key 下移至左孩子结点中，该key所对应的右孩子结点指向node的右孩子结点中的第一个孩子。  
  286.     leftChild->key[leftChild->keynum] = key;  
  287.     leftChild->child[leftChild->keynum + 1] = rightChild->child[0];  
  288.     ++leftChild->keynum;  
  289.   
  290.     // 右孩子的元素合并到左孩子结点中。  
  291.     for (i = 0; i < rightChild->keynum; ++i) {  
  292.         leftChild->key[leftChild->keynum] = rightChild->key[i];  
  293.         leftChild->child[leftChild->keynum + 1] = rightChild->child[i + 1];  
  294.         ++leftChild->keynum;  
  295.     }  
  296.   
  297.     // 在 node 中下移的 key后面的元素前移  
  298.     for (i = index; i < node->keynum - 1; ++i) {  
  299.         node->key[i] = node->key[i + 1];  
  300.         node->child[i + 1] = node->child[i + 2];  
  301.     }  
  302.     node->key[node->keynum - 1] = 0;  
  303.     node->child[node->keynum] = NULL;  
  304.     --node->keynum;  
  305.   
  306.     // 如果根节点没有 key 了，并将根节点调整为合并后的左孩子节点；然后删除释放空间。  
  307.     if (node->keynum == 0) {  
  308.         if (*tree == node) {  
  309.             *tree = leftChild;  
  310.         }  
  311.   
  312.         free(node);  
  313.         node = NULL;  
  314.     }  
  315.   
  316.     free(rightChild);  
  317.     rightChild = NULL;  
  318. }  
  319.   
  320. void BTree_recursive_remove(BTree* tree, KeyType key)  
  321. {  
  322.     // B-数的保持条件之一：  
  323.     // 非根节点的内部节点的关键字数目不能少于 BTree_D - 1  
  324.   
  325.     int i, j, index;  
  326.     BTNode *root = *tree;  
  327.     BTNode *node = root;  
  328.   
  329.     if (!root) {  
  330.         printf("Failed to remove %c, it is not in the tree!\n", key);  
  331.         return;  
  332.     }  
  333.   
  334.     // 结点中找key。  
  335.     index = 0;  
  336.     while (index < node->keynum && key > node->key[index]) {  
  337.         ++index;  
  338.     }  
  339.   
  340. /*======================含有key的当前结点时的情况==================== 
  341. node: 
  342. index of Key:            i-1  i  i+1 
  343.                         +---+---+---+---+ 
  344.                           *  key   * 
  345.                     +---+---+---+---+---+ 
  346.                            /     \ 
  347. index of Child:           i      i+1 
  348.                          /         \ 
  349.                     +---+---+      +---+---+ 
  350.                       *   *           *   *    
  351.                 +---+---+---+  +---+---+---+ 
  352.                     leftChild     rightChild 
  353. ============================================================*/  
  354.     /*一、结点中找到了关键字key的情况.*/  
  355.     if (index < node->keynum && node->key[index] == key) {  
  356.         BTNode *leftChild, *rightChild;  
  357.         KeyType leftKey, rightKey;  
  358.         /* 1，所在节点是叶子节点，直接删除*/  
  359.         if (node->isLeaf) {  
  360.             for (i = index; i < node->keynum-1; ++i) {  
  361.                 node->key[i] = node->key[i + 1];  
  362.                 //node->child[i + 1] = node->child[i + 2];叶子节点的孩子结点为空，无需移动处理。  
  363.             }  
  364.             node->key[node->keynum-1] = 0;  
  365.             //node->child[node->keynum] = NULL;  
  366.             --node->keynum;  
  367.   
  368.             if (node->keynum == 0) {  
  369.                 assert(node == *tree);  
  370.                 free(node);  
  371.                 *tree = NULL;  
  372.             }  
  373.   
  374.             return;  
  375.         }  
  376.         /*2.选择脱贫致富的孩子结点。*/  
  377.         // 2a，选择相对富有的左孩子结点。  
  378.         // 如果位于 key 前的左孩子结点的 key 数目 >= BTree_D，  
  379.         // 在其中找 key 的左孩子结点的最后一个元素上移至父节点key的位置。  
  380.         // 然后在左孩子节点中递归删除元素leftKey。  
  381.         else if (node->child[index]->keynum >= BTree_D) {  
  382.             leftChild = node->child[index];  
  383.             leftKey = leftChild->key[leftChild->keynum - 1];  
  384.             node->key[index] = leftKey;  
  385.   
  386.             BTree_recursive_remove(&leftChild, leftKey);  
  387.         }  
  388.         // 2b，选择相对富有的右孩子结点。  
  389.         // 如果位于 key 后的右孩子结点的 key 数目 >= BTree_D，  
  390.         // 在其中找 key 的右孩子结点的第一个元素上移至父节点key的位置  
  391.         // 然后在右孩子节点中递归删除元素rightKey。  
  392.         else if (node->child[index + 1]->keynum >= BTree_D) {  
  393.             rightChild = node->child[index + 1];  
  394.             rightKey = rightChild->key[0];  
  395.             node->key[index] = rightKey;  
  396.   
  397.             BTree_recursive_remove(&rightChild, rightKey);  
  398.         }  
  399.         /*左右孩子结点都刚脱贫。删除前需要孩子结点的合并操作*/  
  400.         // 2c，左右孩子结点只包含 BTree_D - 1 个节点，  
  401.         // 合并是将 key 下移至左孩子节点，并将右孩子节点合并到左孩子节点中，  
  402.         // 删除右孩子节点，在父节点node中移除 key 和指向右孩子节点的指针，  
  403.         // 然后在合并了的左孩子节点中递归删除元素key。  
  404.         else if (node->child[index]->keynum == BTree_D - 1  
  405.             && node->child[index + 1]->keynum == BTree_D - 1){  
  406.             leftChild = node->child[index];  
  407.   
  408.             BTree_merge_child(tree, node, index);  
  409.   
  410.             // 在合并了的左孩子节点中递归删除 key  
  411.             BTree_recursive_remove(&leftChild, key);  
  412.         }  
  413.     }  
  414.   
  415. /*======================未含有key的当前结点时的情况==================== 
  416. node: 
  417. index of Key:            i-1  i  i+1 
  418.                         +---+---+---+---+ 
  419.                           *  keyi * 
  420.                     +---+---+---+---+---+ 
  421.                        /    |    \ 
  422. index of Child:      i-1    i     i+1 
  423.                      /      |       \ 
  424.             +---+---+   +---+---+      +---+---+ 
  425.              *   *        *   *          *   *    
  426.         +---+---+---+   +---+---+---+  +---+---+---+ 
  427.         leftSibling       Child        rightSibling  
  428. ============================================================*/  
  429.     /*二、结点中未找到了关键字key的情况.*/  
  430.     else {  
  431.         BTNode *leftSibling, *rightSibling, *child;  
  432.         // 3. key 不在内节点 node 中，则应当在某个包含 key 的子节点中。  
  433.         //  key < node->key[index], 所以 key 应当在孩子节点 node->child[index] 中  
  434.         child = node->child[index];  
  435.         if (!child) {  
  436.             printf("Failed to remove %c, it is not in the tree!\n", key);  
  437.             return;  
  438.         }  
  439.         /*所需查找的该孩子结点刚脱贫的情况*/  
  440.         if (child->keynum == BTree_D - 1) {  
  441.             leftSibling = NULL;  
  442.             rightSibling = NULL;  
  443.   
  444.             if (index - 1 >= 0) {  
  445.                 leftSibling = node->child[index - 1];  
  446.             }  
  447.   
  448.             if (index + 1 <= node->keynum) {  
  449.                 rightSibling = node->child[index + 1];  
  450.             }  
  451.             /*选择致富的相邻兄弟结点。*/  
  452.             // 3a，如果所在孩子节点相邻的兄弟节点中有节点至少包含 BTree_D 个关键字  
  453.             // 将 node 的一个关键字key[index]下移到 child 中，将相对富有的相邻兄弟节点中一个关键字上移到  
  454.             // node 中，然后在 child 孩子节点中递归删除 key。  
  455.             if ((leftSibling && leftSibling->keynum >= BTree_D)  
  456.                 || (rightSibling && rightSibling->keynum >= BTree_D)) {  
  457.                 int richR = 0;  
  458.                 if(rightSibling) richR = 1;  
  459.                 if(leftSibling && rightSibling) {  
  460.                     richR = cmp(rightSibling->keynum,leftSibling->keynum);  
  461.                 }  
  462.                 if (rightSibling && rightSibling->keynum >= BTree_D && richR) {  
  463.                     //相邻右兄弟相对富有，则该孩子先向父节点借一个元素，右兄弟中的第一个元素上移至父节点所借位置，并进行相应调整。  
  464.                     child->key[child->keynum] = node->key[index];  
  465.                     child->child[child->keynum + 1] = rightSibling->child[0];  
  466.                     ++child->keynum;  
  467.   
  468.                     node->key[index] = rightSibling->key[0];  
  469.   
  470.                     for (j = 0; j < rightSibling->keynum - 1; ++j) {//元素前移  
  471.                         rightSibling->key[j] = rightSibling->key[j + 1];  
  472.                         rightSibling->child[j] = rightSibling->child[j + 1];  
  473.                     }  
  474.                     rightSibling->key[rightSibling->keynum-1] = 0;  
  475.                     rightSibling->child[rightSibling->keynum-1] = rightSibling->child[rightSibling->keynum];  
  476.                     rightSibling->child[rightSibling->keynum] = NULL;  
  477.                     --rightSibling->keynum;  
  478.                 }  
  479.                 else {//相邻左兄弟相对富有，则该孩子向父节点借一个元素，左兄弟中的最后元素上移至父节点所借位置，并进行相应调整。  
  480.                     for (j = child->keynum; j > 0; --j) {//元素后移  
  481.                         child->key[j] = child->key[j - 1];  
  482.                         child->child[j + 1] = child->child[j];  
  483.                     }  
  484.                     child->child[1] = child->child[0];  
  485.                     child->child[0] = leftSibling->child[leftSibling->keynum];  
  486.                     child->key[0] = node->key[index - 1];  
  487.                     ++child->keynum;  
  488.   
  489.                     node->key[index - 1] = leftSibling->key[leftSibling->keynum - 1];  
  490.   
  491.                     leftSibling->key[leftSibling->keynum - 1] = 0;  
  492.                     leftSibling->child[leftSibling->keynum] = NULL;  
  493.   
  494.                     --leftSibling->keynum;  
  495.                 }  
  496.             }  
  497.             /*相邻兄弟结点都刚脱贫。删除前需要兄弟结点的合并操作,*/  
  498.             // 3b, 如果所在孩子节点相邻的兄弟节点都只包含 BTree_D - 1 个关键字，  
  499.             // 将 child 与其一相邻节点合并，并将 node 中的一个关键字下降到合并节点中，  
  500.             // 再在 node 中删除那个关键字和相关指针，若 node 的 key 为空，删之，并调整根为合并结点。  
  501.             // 最后，在相关孩子节点child中递归删除 key。  
  502.             else if ((!leftSibling || (leftSibling && leftSibling->keynum == BTree_D - 1))  
  503.                 && (!rightSibling || (rightSibling && rightSibling->keynum == BTree_D - 1))) {  
  504.                 if (leftSibling && leftSibling->keynum == BTree_D - 1) {  
  505.   
  506.                     BTree_merge_child(tree, node, index - 1);//node中的右孩子元素合并到左孩子中。  
  507.   
  508.                     child = leftSibling;  
  509.                 }  
  510.   
  511.                 else if (rightSibling && rightSibling->keynum == BTree_D - 1) {  
  512.   
  513.                     BTree_merge_child(tree, node, index);//node中的右孩子元素合并到左孩子中。  
  514.                 }  
  515.             }  
  516.         }  
  517.   
  518.         BTree_recursive_remove(&child, key);//调整后，在key所在孩子结点中继续递归删除key。  
  519.     }  
  520. }  
  521.   
  522. void BTree_remove(BTree* tree, KeyType key)  
  523. {  
  524. #ifdef DEBUG_BTREE  
  525.     printf("BTree_remove:\n");  
  526. #endif  
  527.     if (*tree==NULL)  
  528.     {     
  529.         printf("BTree is NULL!\n");  
  530.         return;  
  531.     }  
  532.   
  533.     BTree_recursive_remove(tree, key);  
  534. }  
  535.   
  536. //=====================================search====================================  
  537.   
  538. BTNode* BTree_recursive_search(const BTree tree, KeyType key, int* pos)  
  539. {  
  540.     int i = 0;  
  541.   
  542.     while (i < tree->keynum && key > tree->key[i]) {  
  543.         ++i;  
  544.     }  
  545.   
  546.     // Find the key.  
  547.     if (i < tree->keynum && tree->key[i] == key) {  
  548.         *pos = i;  
  549.         return tree;  
  550.     }  
  551.   
  552.     // tree 为叶子节点，找不到 key，查找失败返回  
  553.     if (tree->isLeaf) {  
  554.         return NULL;  
  555.     }  
  556.   
  557.     // 节点内查找失败，但 tree->key[i - 1]< key < tree->key[i]，  
  558.     // 下一个查找的结点应为 child[i]  
  559.   
  560.     // 从磁盘读取第 i 个孩子的数据  
  561.     disk_read(&tree->child[i]);  
  562.   
  563.     // 递归地继续查找于树 tree->child[i]  
  564.     return BTree_recursive_search(tree->child[i], key, pos);  
  565. }  
  566.   
  567. BTNode* BTree_search(const BTree tree, KeyType key, int* pos)  
  568. {  
  569. #ifdef DEBUG_BTREE  
  570.     printf("BTree_search:\n");  
  571. #endif  
  572.     if (!tree) {  
  573.         printf("BTree is NULL!\n");  
  574.         return NULL;  
  575.     }  
  576.     *pos = -1;  
  577.     return BTree_recursive_search(tree,key,pos);  
  578. }  
  579.   
  580. //===============================create===============================  
  581. void BTree_create(BTree* tree, const KeyType* data, int length)  
  582. {  
  583.     int i, pos = -1;  
  584.     assert(tree);  
  585.   
  586. #ifdef DEBUG_BTREE  
  587.     printf("\n 开始创建 B-树，关键字为:\n");  
  588.     for (i = 0; i < length; i++) {  
  589.         printf(" %c ", data[i]);  
  590.     }  
  591.     printf("\n");  
  592. #endif  
  593.   
  594.     for (i = 0; i < length; i++) {  
  595. #ifdef DEBUG_BTREE  
  596.         printf("\n插入关键字 %c:\n", data[i]);  
  597. #endif  
  598.   
  599.         BTree_search(*tree,data[i],&pos);//树的递归搜索。  
  600.         if (pos!=-1)  
  601.         {  
  602.             printf("this key %c is in the B-tree,not to insert.\n",data[i]);  
  603.         }else{  
  604.             BTree_insert(tree, data[i]);//插入元素到BTree中。  
  605.         }  
  606.   
  607. #ifdef DEBUG_BTREE  
  608.         BTree_print(*tree,1);//树的深度遍历,从第一层开始。  
  609. #endif  
  610.     }  
  611.   
  612.     printf("\n");  
  613. }  
  614. //===============================destroy===============================  
  615. void BTree_destroy(BTree* tree)  
  616. {  
  617.     int i;  
  618.     BTNode* node = *tree;  
  619.   
  620.     if (node) {  
  621.         for (i = 0; i <= node->keynum; i++) {  
  622.             BTree_destroy(&node->child[i]);  
  623.         }  
  624.   
  625.         free(node);  
  626.     }  
  627.   
  628.     *tree = NULL;  
  629. }  



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

[cpp] view plaincopyprint?
  1. /*************************************************************************** 
  2.     @coder:weedge E-mail:weege@126.com 
  3.     @date:2011/08/28 
  4.     @comment: 
  5.         测试order序(阶)的B-TREE结构基本操作。 
  6.         查找：search，插入：insert，删除：remove。 
  7.         创建：create，销毁：destory，打印：print。 
  8. **********************************************************/  
  9.   
  10. #include <stdio.h>  
  11. #include "btree.h"  
  12.   
  13. void test_BTree_search(BTree tree, KeyType key)  
  14. {  
  15.     int pos = -1;  
  16.     BTNode*    node = BTree_search(tree, key, &pos);  
  17.     if (node) {  
  18.         printf("在%s节点（包含 %d 个关键字）中找到关键字 %c，其索引为 %d\n",  
  19.             node->isLeaf ? "叶子" : "非叶子",  
  20.             node->keynum, key, pos);  
  21.     }  
  22.     else {  
  23.         printf("在树中找不到关键字 %c\n", key);  
  24.     }  
  25. }  
  26.   
  27. void test_BTree_remove(BTree* tree, KeyType key)  
  28. {  
  29.     printf("\n移除关键字 %c \n", key);  
  30.     BTree_remove(tree, key);  
  31.     BTree_print(*tree);  
  32.     printf("\n");  
  33. }  
  34.   
  35. void test_btree()  
  36. {  
  37.   
  38.     KeyType array[] = {  
  39.         'G','G', 'M', 'P', 'X', 'A', 'C', 'D', 'E', 'J', 'K',  
  40.         'N', 'O', 'R', 'S', 'T', 'U', 'V', 'Y', 'Z', 'F', 'X'  
  41.     };  
  42.     const int length = sizeof(array)/sizeof(KeyType);  
  43.     BTree tree = NULL;  
  44.     BTNode* node = NULL;  
  45.     int pos = -1;  
  46.     KeyType key1 = 'R';        // in the tree.  
  47.     KeyType key2 = 'B';        // not in the tree.  
  48.   
  49.     // 创建  
  50.     BTree_create(&tree, array, length);  
  51.   
  52.     printf("\n=== 创建 B- 树 ===\n");  
  53.     BTree_print(tree);  
  54.     printf("\n");  
  55.   
  56.     // 查找  
  57.     test_BTree_search(tree, key1);  
  58.     printf("\n");  
  59.     test_BTree_search(tree, key2);  
  60.   
  61.     // 移除不在B树中的元素  
  62.     test_BTree_remove(&tree, key2);  
  63.     printf("\n");  
  64.   
  65.     // 插入关键字  
  66.     printf("\n插入关键字 %c \n", key2);  
  67.     BTree_insert(&tree, key2);  
  68.     BTree_print(tree);  
  69.     printf("\n");  
  70.   
  71.     test_BTree_search(tree, key2);  
  72.   
  73.     // 移除关键字  
  74.     test_BTree_remove(&tree, key2);  
  75.     test_BTree_search(tree, key2);  
  76.   
  77.     key2 = 'M';  
  78.     test_BTree_remove(&tree, key2);  
  79.     test_BTree_search(tree, key2);  
  80.   
  81.     key2 = 'E';  
  82.     test_BTree_remove(&tree, key2);  
  83.     test_BTree_search(tree, key2);  
  84.   
  85.     key2 = 'G';  
  86.     test_BTree_remove(&tree, key2);  
  87.     test_BTree_search(tree, key2);  
  88.   
  89.     key2 = 'A';  
  90.     test_BTree_remove(&tree, key2);  
  91.     test_BTree_search(tree, key2);  
  92.   
  93.     key2 = 'D';  
  94.     test_BTree_remove(&tree, key2);  
  95.     test_BTree_search(tree, key2);  
  96.   
  97.     key2 = 'K';  
  98.     test_BTree_remove(&tree, key2);  
  99.     test_BTree_search(tree, key2);  
  100.   
  101.     key2 = 'P';  
  102.     test_BTree_remove(&tree, key2);  
  103.     test_BTree_search(tree, key2);  
  104.   
  105.     key2 = 'J';  
  106.     test_BTree_remove(&tree, key2);  
  107.     test_BTree_search(tree, key2);  
  108.   
  109.     key2 = 'C';  
  110.     test_BTree_remove(&tree, key2);  
  111.     test_BTree_search(tree, key2);  
  112.   
  113.     key2 = 'X';  
  114.     test_BTree_remove(&tree, key2);  
  115.     test_BTree_search(tree, key2);  
  116.   
  117.     key2 = 'O';  
  118.     test_BTree_remove(&tree, key2);  
  119.     test_BTree_search(tree, key2);  
  120.   
  121.     key2 = 'V';  
  122.     test_BTree_remove(&tree, key2);  
  123.     test_BTree_search(tree, key2);  
  124.   
  125.     key2 = 'R';  
  126.     test_BTree_remove(&tree, key2);  
  127.     test_BTree_search(tree, key2);  
  128.   
  129.     key2 = 'U';  
  130.     test_BTree_remove(&tree, key2);  
  131.     test_BTree_search(tree, key2);  
  132.   
  133.     key2 = 'T';  
  134.     test_BTree_remove(&tree, key2);  
  135.     test_BTree_search(tree, key2);  
  136.   
  137.     key2 = 'N';  
  138.     test_BTree_remove(&tree, key2);  
  139.     test_BTree_search(tree, key2);  
  140.     key2 = 'S';  
  141.     test_BTree_remove(&tree, key2);  
  142.     test_BTree_search(tree, key2);  
  143.     key2 = 'Y';  
  144.     test_BTree_remove(&tree, key2);  
  145.     test_BTree_search(tree, key2);  
  146.     key2 = 'F';  
  147.     test_BTree_remove(&tree, key2);  
  148.     test_BTree_search(tree, key2);  
  149.     key2 = 'Z';  
  150.     test_BTree_remove(&tree, key2);  
  151.     test_BTree_search(tree, key2);  
  152.   
  153.     // 销毁  
  154.     BTree_destroy(&tree);  
  155. }  
  156.   
  157. int main()  
  158. {  
  159.     test_btree();  
  160.   
  161.     return 0;  
  162. }  


另外参考《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?
  1. /*************************************************************************** 
  2.     @editer:weedge E-mail:weege@126.com 
  3.     @date:2011/08/27 
  4.     @comment: 
  5.         Data.structures.and.Program.Design.in.Cpp 
  6.         Section 11.3:EXTERNALSEARCHING:B-TREES 
  7.         采用泛型编程（模板template），Record为关键字类型，order为序(阶)， 
  8.         实现对order序(阶)的B-TREE结构基本操作的封装。 
  9.         查找：search，插入：insert，删除：remove。 
  10. **********************************************************/  
  11.   
  12. #ifndef B_Tree_H_  
  13. #define B_Tree_H_  
  14.   
  15. enum Error_code{overflow=-2,duplicate_error=-1,not_present=0,success=1};  
  16.   
  17. template <class Record, int order>  
  18. struct B_node {  
  19. ///  data members:  
  20.    int count;  
  21.    Record data[order - 1];  
  22.    B_node<Record, order> *branch[order];///在大多数应用中，这些指针被不同的磁盘中块(block)的地址代替。  
  23. ///  constructor:  
  24.    B_node();  
  25. };  
  26.   
  27. template <class Record, int order>  
  28. class B_tree {  
  29. public:    
  30.     ////*  Add public methods. */  
  31.   
  32.     Error_code search_tree(Record &target);  
  33.   
  34.     Error_code insert(const Record &new_entry);  
  35.   
  36.     Error_code remove(const Record &target);  
  37.   
  38. protected:  
  39.     ////*  data members */  
  40.       
  41.     ////*  Add protected auxiliary functions here in order to inherit for subclass. */  
  42.     ///=============================search=========================================  
  43.   
  44.     Error_code recursive_search_tree(B_node<Record, order> *current, Record &target);  
  45.       
  46.     Error_code search_node(B_node<Record, order> *current, const Record &target, int &position);  
  47.   
  48.     ///=============================insert=========================================  
  49.   
  50.     Error_code push_down(B_node<Record, order> *current,const Record &new_entry,  
  51.         Record &median,B_node<Record, order> *&right_branch);  
  52.       
  53.     void push_in(B_node<Record, order> *current, const Record &entry,   
  54.         B_node<Record, order> *right_branch, int position);  
  55.       
  56.     void split_node(B_node<Record, order> *current,   const Record &extra_entry, B_node<Record, order> *extra_branch,  
  57.         int position, B_node<Record, order> *&right_half, Record &median);  
  58.   
  59.     ///==============================remove========================================  
  60.   
  61.     Error_code recursive_remove(B_node<Record, order> *current, const Record &target);  
  62.       
  63.     void remove_data(B_node<Record, order> *current, int position);  
  64.   
  65.     void copy_in_predecessor(B_node<Record, order> *current, int position);  
  66.       
  67.     void restore(B_node<Record, order> *current,int position);  
  68.       
  69.     void move_left(B_node<Record, order> *current, int position);  
  70.       
  71.     void move_right(B_node<Record, order> *current,int position);  
  72.       
  73.     void combine(B_node<Record, order> *current, int position);  
  74.   
  75. private:   
  76.     ////*  data members */  
  77.     B_node<Record, order> *root;  
  78.   
  79.     ////*  Add private auxiliary functions here. */  
  80. };  
  81.   
  82. #endif //end B_Tree_H_  

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

[cpp] view plaincopyprint?
  1. /*************************************************************************** 
  2.     @editor:weedge E-mail:weege@126.com 
  3.     @date:2011/08/27 
  4.     @comment: 
  5.         Data.structures.and.Program.Design.in.Cpp 
  6.         Section 11.3:EXTERNALSEARCHING:B-TREES 
  7.         采用泛型编程（模板template）， 
  8.         实现对B-TREE结构基本操作的封装。 
  9.         查找：search，插入：insert，删除：remove。 
  10. **********************************************************/  
  11. #include "B_Tree.h"  
  12.   
  13. template <class Record, int order>  
  14. Error_code B_tree<Record, order>::search_tree(Record &target)  
  15. /* 
  16. Post: If there is an entry in the B-tree whose key matches that in target, 
  17.       the parameter target is replaced by the corresponding Record from 
  18.       the B-tree and a code of success is returned.  Otherwise 
  19.       a code of not_present is returned. 
  20. Uses: recursive_search_tree 
  21. */  
  22. {  
  23.    return recursive_search_tree(root, target);  
  24. }  
  25.   
  26.   
  27. template <class Record, int order>  
  28. Error_code B_tree<Record, order>::recursive_search_tree(  
  29.            B_node<Record, order> *current, Record &target)  
  30. /* 
  31. Pre:  current is either NULL or points to a subtree of the B_tree. 
  32. Post: If the Key of target is not in the subtree, a code of not_present 
  33.       is returned. Otherwise, a code of success is returned and 
  34.       target is set to the corresponding Record of the subtree. 
  35. Uses: recursive_search_tree recursively and search_node 
  36. */  
  37. {  
  38.    Error_code result = not_present;  
  39.    int position;  
  40.    if (current != NULL) {  
  41.       result = search_node(current, target, position);  
  42.       if (result == not_present)  
  43.          result = recursive_search_tree(current->branch[position], target);  
  44.       else  
  45.          target = current->data[position];  
  46.    }  
  47.    return result;  
  48. }  
  49.   
  50.   
  51. template <class Record, int order>  
  52. Error_code B_tree<Record, order>::search_node(  
  53.    B_node<Record, order> *current, const Record &target, int &position)  
  54. /* 
  55. Pre:  current points to a node of a B_tree. 
  56. Post: If the Key of target is found in *current, then a code of 
  57.       success is returned, the parameter position is set to the index 
  58.       of target, and the corresponding Record is copied to 
  59.       target.  Otherwise, a code of not_present is returned, and 
  60.       position is set to the branch index on which to continue the search. 
  61. Uses: Methods of class Record. 
  62. */  
  63. {  
  64.    position = 0;  
  65.    while (position < current->count && target > current->data[position])  
  66.       position++;         //  Perform a sequential search through the keys.  
  67.    if (position < current->count && target == current->data[position])  
  68.       return success;  
  69.    else  
  70.       return not_present;  
  71. }  
  72.   
  73.   
  74. template <class Record, int order>  
  75. Error_code B_tree<Record, order>::insert(const Record &new_entry)  
  76. /* 
  77. Post: If the Key of new_entry is already in the B_tree, 
  78.       a code of duplicate_error is returned. 
  79.       Otherwise, a code of success is returned and the Record new_entry 
  80.       is inserted into the B-tree in such a way that the properties of a B-tree 
  81.       are preserved. 
  82. Uses: Methods of struct B_node and the auxiliary function push_down. 
  83. */  
  84. {  
  85.    Record median;  
  86.    B_node<Record, order> *right_branch, *new_root;  
  87.    Error_code result = push_down(root, new_entry, median, right_branch);  
  88.   
  89.    if (result == overflow) {  //  The whole tree grows in height.  
  90.                               //  Make a brand new root for the whole B-tree.  
  91.       new_root = new B_node<Record, order>;  
  92.       new_root->count = 1;  
  93.       new_root->data[0] = median;  
  94.       new_root->branch[0] = root;  
  95.       new_root->branch[1] = right_branch;  
  96.       root = new_root;  
  97.       result = success;  
  98.    }  
  99.    return result;  
  100. }  
  101.   
  102.   
  103. template <class Record, int order>  
  104. Error_code B_tree<Record, order>::push_down(  
  105.                  B_node<Record, order> *current,  
  106.                  const Record &new_entry,  
  107.                  Record &median,  
  108.                  B_node<Record, order> *&right_branch)  
  109. /* 
  110. Pre:  current is either NULL or points to a node of a B_tree. 
  111. Post: If an entry with a Key matching that of new_entry is in the subtree 
  112.       to which current points, a code of duplicate_error is returned. 
  113.       Otherwise, new_entry is inserted into the subtree: If this causes the 
  114.       height of the subtree to grow, a code of overflow is returned, and the 
  115.       Record median is extracted to be reinserted higher in the B-tree, 
  116.       together with the subtree right_branch on its right. 
  117.       If the height does not grow, a code of success is returned. 
  118. Uses: Functions push_down (called recursively), search_node, 
  119.       split_node, and push_in. 
  120. */  
  121. {  
  122.    Error_code result;  
  123.    int position;  
  124.    if (current == NULL) { //  Since we cannot insert in an empty tree, the recursion terminates.  
  125.       median = new_entry;  
  126.       right_branch = NULL;  
  127.       result = overflow;  
  128.    }  
  129.    else {   //   Search the current node.  
  130.       if (search_node(current, new_entry, position) == success)  
  131.          result = duplicate_error;  
  132.       else {  
  133.          Record extra_entry;  
  134.          B_node<Record, order> *extra_branch;  
  135.          result = push_down(current->branch[position], new_entry,  
  136.                             extra_entry, extra_branch);  
  137.          if (result == overflow) {  //  Record extra_entry now must be added to current  
  138.             if (current->count < order - 1) {  
  139.                result = success;  
  140.                push_in(current, extra_entry, extra_branch, position);  
  141.             }  
  142.   
  143.             else split_node(current, extra_entry, extra_branch, position,  
  144.                             right_branch, median);  
  145.             //  Record median and its right_branch will go up to a higher node.  
  146.          }  
  147.       }  
  148.    }  
  149.    return result;  
  150. }  
  151.   
  152.   
  153. template <class Record, int order>  
  154. void B_tree<Record, order>::push_in(B_node<Record, order> *current,  
  155.    const Record &entry, B_node<Record, order> *right_branch, int position)  
  156. /* 
  157. Pre:  current points to a node of a B_tree.  The node *current is not full 
  158.       and entry belongs in *current at index position. 
  159. Post: entry has been inserted along with its right-hand branch 
  160.       right_branch into *current at index position. 
  161. */  
  162. {  
  163.    for (int i = current->count; i > position; i--) {  //  Shift all later data to the right.  
  164.       current->data[i] = current->data[i - 1];  
  165.       current->branch[i + 1] = current->branch[i];  
  166.    }  
  167.    current->data[position] = entry;  
  168.    current->branch[position + 1] = right_branch;  
  169.    current->count++;  
  170. }  
  171.   
  172.   
  173. template <class Record, int order>  
  174. void B_tree<Record, order>::split_node(  
  175.    B_node<Record, order> *current,    //  node to be split  
  176.    const Record &extra_entry,          //  new entry to insert  
  177.    B_node<Record, order> *extra_branch,//  subtree on right of extra_entry  
  178.    int position,                  //  index in node where extra_entry goes  
  179.    B_node<Record, order> *&right_half, //  new node for right half of entries  
  180.    Record &median)                     //  median entry (in neither half)  
  181. /* 
  182. Pre:  current points to a node of a B_tree. 
  183.       The node *current is full, but if there were room, the record 
  184.       extra_entry with its right-hand pointer extra_branch would belong 
  185.       in *current at position position, 0 <= position < order. 
  186. Post: The node *current with extra_entry and pointer extra_branch at 
  187.       position position are divided into nodes *current and *right_half 
  188.       separated by a Record median. 
  189. Uses: Methods of struct B_node, function push_in. 
  190. */  
  191. {  
  192.    right_half = new B_node<Record, order>;  
  193.    int mid = order/2;  //  The entries from mid on will go to right_half.  
  194.    if (position <= mid) {   //  First case:  extra_entry belongs in left half.  
  195.       for (int i = mid; i < order - 1; i++) {  //  Move entries to right_half.  
  196.          right_half->data[i - mid] = current->data[i];  
  197.          right_half->branch[i + 1 - mid] = current->branch[i + 1];  
  198.       }  
  199.       current->count = mid;  
  200.       right_half->count = order - 1 - mid;  
  201.       push_in(current, extra_entry, extra_branch, position);  
  202.    }  
  203.    else {  //  Second case:  extra_entry belongs in right half.  
  204.       mid++;      //  Temporarily leave the median in left half.  
  205.       for (int i = mid; i < order - 1; i++) {  //  Move entries to right_half.  
  206.          right_half->data[i - mid] = current->data[i];  
  207.          right_half->branch[i + 1 - mid] = current->branch[i + 1];  
  208.       }  
  209.       current->count = mid;  
  210.       right_half->count = order - 1 - mid;  
  211.       push_in(right_half, extra_entry, extra_branch, position - mid);  
  212.    }  
  213.       median = current->data[current->count - 1]; //  Remove median from left half.  
  214.       right_half->branch[0] = current->branch[current->count];  
  215.       current->count--;  
  216. }  
  217.   
  218.   
  219. template <class Record, int order>  
  220. Error_code B_tree<Record, order>::remove(const Record &target)  
  221. /* 
  222. Post: If a Record with Key matching that of target belongs to the 
  223.       B_tree, a code of success is returned and the corresponding node 
  224.       is removed from the B-tree.  Otherwise, a code of not_present 
  225.       is returned. 
  226. Uses: Function recursive_remove 
  227. */  
  228. {  
  229.    Error_code result;  
  230.    result = recursive_remove(root, target);  
  231.    if (root != NULL && root->count == 0) {  //  root is now empty.  
  232.       B_node<Record, order> *old_root = root;  
  233.       root = root->branch[0];  
  234.       delete old_root;  
  235.    }  
  236.    return result;  
  237. }  
  238.   
  239.   
  240. template <class Record, int order>  
  241. Error_code B_tree<Record, order>::recursive_remove(  
  242.    B_node<Record, order> *current, const Record &target)  
  243. /* 
  244. Pre:  current is either NULL or 
  245.       points to the root node of a subtree of a B_tree. 
  246. Post: If a Record with Key matching that of target belongs to the subtree, 
  247.       a code of success is returned and the corresponding node is removed 
  248.       from the subtree so that the properties of a B-tree are maintained. 
  249.       Otherwise, a code of not_present is returned. 
  250. Uses: Functions search_node, copy_in_predecessor, 
  251.       recursive_remove (recursively), remove_data, and restore. 
  252. */  
  253. {  
  254.    Error_code result;  
  255.    int position;  
  256.    if (current == NULL) result = not_present;  
  257.    else {  
  258.       if (search_node(current, target, position) == success) {  //  The target is in the current node.  
  259.          result = success;  
  260.          if (current->branch[position] != NULL) {     //  not at a leaf node  
  261.             copy_in_predecessor(current, position);  
  262.   
  263.             recursive_remove(current->branch[position],  
  264.                              current->data[position]);  
  265.          }  
  266.          else remove_data(current, position);     //  Remove from a leaf node.  
  267.       }  
  268.       else result = recursive_remove(current->branch[position], target);  
  269.       if (current->branch[position] != NULL)  
  270.          if (current->branch[position]->count < (order - 1) / 2)  
  271.             restore(current, position);  
  272.    }  
  273.    return result;  
  274. }  
  275.   
  276.   
  277. template <class Record, int order>  
  278. void B_tree<Record, order>::remove_data(B_node<Record, order> *current,  
  279.                                         int position)  
  280. /* 
  281. Pre:  current points to a leaf node in a B-tree with an entry at position. 
  282. Post: This entry is removed from *current. 
  283. */  
  284. {  
  285.    for (int i = position; i < current->count - 1; i++)  
  286.       current->data[i] = current->data[i + 1];  
  287.    current->count--;  
  288. }  
  289.   
  290.   
  291. template <class Record, int order>  
  292. void B_tree<Record, order>::copy_in_predecessor(  
  293.                     B_node<Record, order> *current, int position)  
  294. /* 
  295. Pre:  current points to a non-leaf node in a B-tree with an entry at position. 
  296. Post: This entry is replaced by its immediate predecessor under order of keys. 
  297. */  
  298. {  
  299.    B_node<Record, order> *leaf = current->branch[position];  //   First go left from the current entry.  
  300.    while (leaf->branch[leaf->count] != NULL)  
  301.       leaf = leaf->branch[leaf->count]; //   Move as far rightward as possible.  
  302.    current->data[position] = leaf->data[leaf->count - 1];  
  303. }  
  304.   
  305.   
  306. template <class Record, int order>  
  307. void B_tree<Record, order>::restore(B_node<Record, order> *current,  
  308.                                     int position)  
  309. /* 
  310. Pre:  current points to a non-leaf node in a B-tree; the node to which 
  311.       current->branch[position] points has one too few entries. 
  312. Post: An entry is taken from elsewhere to restore the minimum number of 
  313.       entries in the node to which current->branch[position] points. 
  314. Uses: move_left, move_right, combine. 
  315. */  
  316. {  
  317.    if (position == current->count)   //  case:  rightmost branch  
  318.       if (current->branch[position - 1]->count > (order - 1) / 2)  
  319.          move_right(current, position - 1);  
  320.       else  
  321.          combine(current, position);  
  322.    else if (position == 0)       //  case: leftmost branch  
  323.       if (current->branch[1]->count > (order - 1) / 2)  
  324.          move_left(current, 1);  
  325.       else  
  326.          combine(current, 1);  
  327.    else                          //  remaining cases: intermediate branches  
  328.       if (current->branch[position - 1]->count > (order - 1) / 2)  
  329.          move_right(current, position - 1);  
  330.       else if (current->branch[position + 1]->count > (order - 1) / 2)  
  331.          move_left(current, position + 1);  
  332.       else  
  333.          combine(current, position);  
  334. }  
  335.   
  336.   
  337. template <class Record, int order>  
  338. void B_tree<Record, order>::move_left(B_node<Record, order> *current,  
  339.                                       int position)  
  340. /* 
  341. Pre:  current points to a node in a B-tree with more than the minimum 
  342.       number of entries in branch position and one too few entries in branch 
  343.       position - 1. 
  344. Post: The leftmost entry from branch position has moved into 
  345.       current, which has sent an entry into the branch position - 1. 
  346. */  
  347. {  
  348.    B_node<Record, order> *left_branch = current->branch[position - 1],  
  349.                          *right_branch = current->branch[position];  
  350.    left_branch->data[left_branch->count] = current->data[position - 1];  //  Take entry from the parent.  
  351.    left_branch->branch[++left_branch->count] = right_branch->branch[0];  
  352.    current->data[position - 1] = right_branch->data[0];  //   Add the right-hand entry to the parent.  
  353.    right_branch->count--;  
  354.    for (int i = 0; i < right_branch->count; i++) {   //  Move right-hand entries to fill the hole.  
  355.       right_branch->data[i] = right_branch->data[i + 1];  
  356.       right_branch->branch[i] = right_branch->branch[i + 1];  
  357.    }  
  358.    right_branch->branch[right_branch->count] =  
  359.       right_branch->branch[right_branch->count + 1];  
  360. }  
  361.   
  362.   
  363. template <class Record, int order>  
  364. void B_tree<Record, order>::move_right(B_node<Record, order> *current,  
  365.                                        int position)  
  366. /* 
  367. Pre:  current points to a node in a B-tree with more than the minimum 
  368.       number of entries in branch position and one too few entries 
  369.       in branch position + 1. 
  370. Post: The rightmost entry from branch position has moved into 
  371.       current, which has sent an entry into the branch position + 1. 
  372. */  
  373. {  
  374.    B_node<Record, order> *right_branch = current->branch[position + 1],  
  375.                          *left_branch = current->branch[position];  
  376.    right_branch->branch[right_branch->count + 1] =  
  377.       right_branch->branch[right_branch->count];  
  378.    for (int i = right_branch->count ; i > 0; i--) {  //  Make room for new entry.  
  379.       right_branch->data[i] = right_branch->data[i - 1];  
  380.       right_branch->branch[i] = right_branch->branch[i - 1];  
  381.    }  
  382.    right_branch->count++;  
  383.    right_branch->data[0] = current->data[position]; //  Take entry from parent.  
  384.    right_branch->branch[0] = left_branch->branch[left_branch->count--];  
  385.    current->data[position] = left_branch->data[left_branch->count];  
  386. }  
  387.   
  388.   
  389. template <class Record, int order>  
  390. void B_tree<Record, order>::combine(B_node<Record, order> *current,  
  391.                                     int position)  
  392. /* 
  393. Pre:  current points to a node in a B-tree with entries in the branches 
  394.       position and position - 1, with too few to move entries. 
  395. Post: The nodes at branches position - 1 and position have been combined 
  396.       into one node, which also includes the entry formerly in current at 
  397.       index  position - 1. 
  398. */  
  399. {  
  400.    int i;  
  401.    B_node<Record, order> *left_branch = current->branch[position - 1],  
  402.                          *right_branch = current->branch[position];  
  403.    left_branch->data[left_branch->count] = current->data[position - 1];  
  404.    left_branch->branch[++left_branch->count] = right_branch->branch[0];  
  405.    for (i = 0; i < right_branch->count; i++) {  
  406.       left_branch->data[left_branch->count] = right_branch->data[i];  
  407.       left_branch->branch[++left_branch->count] =  
  408.                                         right_branch->branch[i + 1];  
  409.    }  
  410.    current->count--;  
  411.    for (i = position - 1; i < current->count; i++) {  
  412.       current->data[i] = current->data[i + 1];  
  413.       current->branch[i + 1] = current->branch[i + 2];  
  414.    }  
  415.    delete right_branch;  
  416. }  

测试文件：（待写)

//原文地址


上一篇：Spring3.0+Struts2.2+Hibernate3.6整合与常见问题


下一篇：smarty教程系列2--section1