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基本的操作接口)

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

/*************************************************************************** @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基本的操作接口)

/*************************************************************************** @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基本的操作接口)

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

/*************************************************************************** @coder: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; }

测试文件：（待写)

原文链接: https://www.cnblogs.com/weege/archive/2011/08/29/2199476.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍

原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/31370

非原创文章文中已经注明原地址，如有侵权，联系删除

关注公众号【高性能架构探索】，第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处！

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

相关推荐