B tree code (C language)

btree.h

// Realize to order order ( rank ) Of B-TREE Encapsulation of basic operation of structure . 
// lookup ：search, Insert ：insert, Delete ：remove. 
// establish ：create, The destruction ：destory, Print ：print. 
#ifndef BTREE_H 
#define BTREE_H 
  
#ifdef __cplusplus 
extern "C" {
      
#endif 
  
*  Definition m order ( rank )B  The minimum degree of a tree BTree_D=ceil(m)*/ 
///  Here, the maximum number of keywords in each node is defined as :2 * BTree_D - 1, Immediate sequence ( rank )：2 * BTree_D. 
#define BTree_D 2 
#define ORDER (BTree_D * 2) // Defined as 4 rank B-tree,2-3-4 Trees . The simplest is 3 rank B-tree,2-3 Trees . 
//#define ORDER (BTree_T * 2-1) // The simplest is 3 rank B-tree,2-3 Trees . 
  
    typedef int KeyType;  
    typedef struct BTNode{
      
        int keynum;                        ///  The number of keywords in the node ,keynum <= BTree_N 
        KeyType key[ORDER-1];                ///  The keyword vector is key[0..keynum - 1] 
        struct BTNode* child[ORDER];        ///  The child pointer vector is child[0..keynum] 
        bool isLeaf;                    ///  Whether it is the flag of leaf node  
    }BTNode;  
      
    typedef BTNode* BTree;  /// Definition BTree 
      
    /// Given data set data, establish BTree. 
    void BTree_create(BTree* tree, const KeyType* data, int length);  
  
    /// The destruction BTree, Free up memory . 
    void BTree_destroy(BTree* tree);  
      
    /// stay BTree Insert key words in key. 
    void BTree_insert(BTree* tree, KeyType key);  
  
    /// stay BTree Remove keywords from key. 
    void BTree_remove(BTree* tree, KeyType key);  
  
    /// Depth traversal BTree Print node information of each layer . 
    void BTree_print(const BTree tree, int layer=1);  
      
    ///  stay BTree Search for keywords in  key, 
    ///  When successful, the address of the found node and  key  In which position  *pos 
    ///  Return... On failure  NULL  And the node location scanned when the search fails  *pos 
    BTNode* BTree_search(const BTree tree, int key, int* pos);  
      
#ifdef __cplusplus 
}  
#endif 
  
#endif

btree.c

// Code from （ The article has a detailed explanation ）：http://blog.csdn.net/v_july_v/article/details/6735293
// Realize to order order ( rank ) Of B-TREE Encapsulation of basic operation of structure . 
// lookup ：search, Insert ：insert, Delete ：remove. 
// establish ：create, The destruction ：destory, Print ：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) ) // Compare a,b size  
#define DEBUG_BTREE 
  
  
//  Simulate writing nodes to disk  
void disk_write(BTNode* node)  
{
      
// Print out all the elements in the node , Convenient for debugging and viewing keynum Whether the following element is 0( That is, whether there is garbage data ); instead of keynum Elements . 
    printf(" Write nodes to disk ");  
    for(int i=0;i<ORDER-1;i++){
      
        printf("%c",node->key[i]);  
    }  
    printf("\n");  
}  
  
//  Simulate reading nodes from disk  
void disk_read(BTNode** node)  
{
      
// Print out all the elements in the node , Convenient for debugging and viewing keynum Whether the following element is 0( That is, whether there is garbage data ); instead of keynum Elements . 
    printf(" Read nodes to disk ");  
    for(int i=0;i<ORDER-1;i++){
      
        printf("%c",(*node)->key[i]);  
    }  
    printf("\n");  
}  
  
//  Print hierarchically  B  Trees  
void BTree_print(const BTree tree, int layer)  
{
      
    int i;  
    BTNode* node = tree;  
  
    if (node) {
      
        printf(" The first  %d  layer , %d node : ", layer, node->keynum);  
  
        // Print out all the elements in the node , Convenient for debugging and viewing keynum Whether the following element is 0( That is, whether there is garbage data ); instead of keynum Elements . 
        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(" The tree is empty. .\n");  
    }  
}  
  
//  node node Binary search for keywords in . 
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;// Returns the subscript . 
        }  
    }  
    return 0;// No return found 0. 
}  
  
//insert 
/***************************************************************************************  Give half the elements of the split node to the new node , And move the intermediate key element in the split node up to the parent node . parent  Is a non full parent node  node  yes  tree  The subscript in the child table is  index  The child node of , And it is full , Need to split . *******************************************************************/  
void BTree_split_child(BTNode* parent, int index, BTNode* node)  
{
      
#ifdef DEBUG_BTREE 
    printf("BTree_split_child!\n");  
#endif 
    assert(parent && node);  
    int i;  
  
    //  Create a new node , Storage  node  Data in the second half of the  
    BTNode* newNode = (BTNode*)calloc(sizeof(BTNode), 1);  
    if (!newNode) {
      
        printf("Error! out of memory!\n");  
        return;  
    }  
  
    newNode->isLeaf = node->isLeaf;  
    newNode->keynum = BTree_D - 1;  
  
    //  Copy  node  The second half of the keywords , And then node The second half is set to 0. 
    for (i = 0; i < newNode->keynum; ++i){
      
        newNode->key[i] = node->key[BTree_D + i];  
        node->key[BTree_D + i] = 0;  
    }  
  
    //  If  node  It's not a leaf node , Copy  node  The pointer to the child node in the second half , And then node The second half of the pointer to the child node is set to 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;  
        }  
    }  
  
    //  take  node  Split up  newNode  after , The data inside is halved  
    node->keynum = BTree_D - 1;  
  
    //  Adjust the pointer to the child and keyword elements in the parent node . When splitting, the parent node adds pointers to the child and key elements . 
    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;  
  
    //  Write to disk  
     disk_write(parent);  
     disk_write(newNode);  
     disk_write(node);  
}  
  
void BTree_insert_nonfull(BTNode* node, KeyType key)  
{
      
    assert(node);  
  
    int i;  
  
    //  A node is a leaf node , Directly inserted into the  
    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;  
  
        //  Write to disk  
        disk_write(node);  
    }  
  
    //  Nodes are internal nodes  
    else {
      
        /*  Find where to insert */  
        i = node->keynum - 1;  
        while (i >= 0 && key < node->key[i]) {
      
            --i;  
        }  
  
        ++i;  
  
        //  Read child nodes from disk  
        disk_read(&node->child[i]);  
  
        //  If the child node is full , Split adjustment value  
        if (node->child[i]->keynum == (ORDER-1)) {
      
            BTree_split_child(node, i, node->child[i]);  
            //  If the keyword to be inserted is larger than the keyword moved up to the parent node in the split node , Insert in the right child node of the keyword . 
            if (key > node->key[i]) {
      
                ++i;  
            }  
        }  
        BTree_insert_nonfull(node->child[i], key);  
    }  
}  
  
void BTree_insert(BTree* tree, KeyType key)  
{
      
#ifdef DEBUG_BTREE 
    printf("BTree_insert:\n");  
#endif 
    BTNode* node;  
    BTNode* root = *tree;  
  
    //  The tree is empty.  
    if (NULL == root) {
      
        root = (BTNode*)calloc(sizeof(BTNode), 1);  
        if (!root) {
      
            printf("Error! out of memory!\n");  
            return;  
        }  
        root->isLeaf = true;  
        root->keynum = 1;  
        root->key[0] = key;  
  
        *tree = root;  
  
        //  Write to disk  
        disk_write(root);  
  
        return;  
    }  
  
    //  The root node is full , Split adjustment is required before inserting  
    if (root->keynum == (ORDER-1)) {
      
        //  Generate a new node as the root  
        node = (BTNode*)calloc(sizeof(BTNode), 1);  
        if (!node) {
      
            printf("Error! out of memory!\n");  
            return;  
        }  
  
        *tree = node;  
        node->isLeaf = false;  
        node->keynum = 0;  
        node->child[0] = root;  
  
        BTree_split_child(node, 0, root);  
  
        BTree_insert_nonfull(node, key);  
    }  
  
    //  The root node is not full , Insert... In the current node  key 
    else {
      
        BTree_insert_nonfull(root, key);  
    }  
}  
//remove 
//  Yes  tree  The nodes in the  node  Merge child nodes . 
//  Be careful ： Children's node  keynum  Must have reached the lower limit , That is, they are all equal to  BTree_D - 1 
//  take  tree  The index for  index  Of  key  Move down to the left child node , 
//  take  node  The index for  index + 1  The child nodes of are merged into an index of  index  In the child node of , The right child is merged into the left child node . 
//  And adjust the relevant  key  And a pointer .</p>void BTree_merge_child(BTree* tree, BTNode* node, int index) 
{
      
#ifdef DEBUG_BTREE 
    printf("BTree_merge_child!\n");  
#endif 
    assert(tree && node && index >= 0 && index < node->keynum);  
  
    int i;  
  
    KeyType key = node->key[index];  
    BTNode* leftChild = node->child[index];  
    BTNode* rightChild = node->child[index + 1];  
  
    assert(leftChild && leftChild->keynum == BTree_D - 1  
        && rightChild && rightChild->keynum == BTree_D - 1);  
  
    //  take  node The subscript of the keyword in is index  Of  key  Move down to the left child node , The key The corresponding right child node points to node The first child in the right child node of . 
    leftChild->key[leftChild->keynum] = key;  
    leftChild->child[leftChild->keynum + 1] = rightChild->child[0];  
    ++leftChild->keynum;  
  
    //  The elements of the right child are merged into the left child node . 
    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;  
    }  
  
    //  stay  node  Middle down  key The elements behind move forward  
    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 the root node does not  key  了 , And adjust the root node to the merged left child node ; Then delete to free up space . 
    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- One of the conditions for keeping numbers ： 
    //  The number of keywords for internal nodes that are not root nodes cannot be less than  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;  
    }  
  
    //  Find... In the node key. 
    index = 0;  
    while (index < node->keynum && key > node->key[index]) {
      
        ++index;  
    }  
  
/*====================== contain key The current node of ==================== node: index of Key: i-1 i i+1 +---+---+---+---+ * key * +---+---+---+---+---+ / \ index of Child: i i+1 / \ +---+---+ +---+---+ * * * * +---+---+---+ +---+---+---+ leftChild rightChild ============================================================*/  
    /* One 、 Keyword found in node key The situation of .*/  
    BTNode *leftChild, *rightChild;  
    KeyType leftKey, rightKey;  
    if (index < node->keynum && node->key[index] == key) {
      
        /* 1, The node is a leaf node , Delete directly */  
        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]; The child node of the leaf node is empty , No mobile processing required . 
            }  
            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. Choose the child node to get rid of poverty and become rich .*/  
        // 2a, Select the relatively rich left child node . 
        //  If located  key  Front left child node  key  number  >= BTree_D, 
        //  Find... In it  key  The last element of the left child node of is moved up to the parent node key The location of . 
        //  Then recursively delete the element in the left child node 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, Select the relatively rich right child node . 
        //  If located  key  After the right child node  key  number  >= BTree_D, 
        //  Find... In it  key  The first element of the right child node of is moved up to the parent node key The location of  
        //  Then recursively delete the element in the right child node 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);  
        }  
        /* Both the left and right children have just been lifted out of poverty . Before deleting, you need to merge child nodes */  
        // 2c, The left and right child nodes only contain  BTree_D - 1  Nodes , 
        //  Merge is to merge  key  Move down to the left child node , And merge the right child node into the left child node , 
        //  Delete the right child node , On the parent node node Remove  key  And a pointer to the right child node , 
        //  Then recursively delete the elements in the merged left child node 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);  
  
            //  Recursively delete in the merged left child node  key 
            BTree_recursive_remove(&leftChild, key);  
        }  
    }  
  
/*====================== Does not contain key The current node of ==================== node: index of Key: i-1 i i+1 +---+---+---+---+ * keyi * +---+---+---+---+---+ / | \ index of Child: i-1 i i+1 / | \ +---+---+ +---+---+ +---+---+ * * * * * * +---+---+---+ +---+---+---+ +---+---+---+ leftSibling Child rightSibling ============================================================*/  
    /* Two 、 Keyword not found in node key The situation of .*/  
    else {
      
        BTNode *leftSibling, *rightSibling, *child;  
        // 3. key  Not the inner node  node  in , It should contain  key  Child node of . 
        // key < node->key[index],  therefore  key  It should be on the child node  node->child[index]  in  
        child = node->child[index];  
        if (!child) {
      
            printf("Failed to remove %c, it is not in the tree!\n", key);  
            return;  
        }  
        /* The child node that needs to be searched has just been lifted out of poverty */  
        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];  
            }  
            /* Select the neighboring brother node to get rich .*/  
            // 3a, If any of the sibling nodes adjacent to the child node contains at least  BTree_D  Key words  
            //  take  node  One of the keywords of key[index] Move down to  child  in , Move a keyword in a relatively rich neighboring sibling node up to  
            // node  in , And then in  child  Recursively delete the child node  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) {
      
        // The neighboring right brothers are relatively rich , The child first borrows an element from the parent node , The first element in the right sibling moves up to the borrowed position of the parent node , And adjust accordingly . 
                    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) {
    // The element moves forward  
                        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 {
    // The neighboring left brothers are relatively rich , Then the child borrows an element from the parent node , The last element in the left sibling moves up to the borrowed position of the parent node , And adjust accordingly . 
                    for (j = child->keynum; j > 0; --j) {
    // Elements move back  
                        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;  
                }  
            }  
            /* Neighboring brother nodes have just been lifted out of poverty . Before deleting, you need to merge sibling nodes ,*/  
            // 3b,  If the sibling nodes adjacent to the child node contain only  BTree_D - 1  Key words , 
            //  take  child  Merge with an adjacent node , And will  node  A keyword in is dropped to the merge node , 
            //  And then  node  Delete that keyword and related pointer in , if  node  Of  key  It's empty , Delete it , And adjust the root to the merge node . 
            //  Last , At the relevant child node child Recursive deletion in  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 The right child element in is merged into the left child . 
  
                    child = leftSibling;  
                }  
  
                else if (rightSibling && rightSibling->keynum == BTree_D - 1) {
      
  
                    BTree_merge_child(tree, node, index);//node The right child element in is merged into the left child . 
                }  
            }  
        }  
  
        BTree_recursive_remove(&child, key);// After the adjustment , stay key Continue to delete recursively in the child node 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  Is a leaf node , Can't find  key, Search failed return  
    if (tree->isLeaf) {
      
        return NULL;  
    }  
  
    //  Intra node lookup failed , but  tree->key[i - 1]< key < tree->key[i], 
    //  The next lookup node should be  child[i] 
  
    //  Read the... From the disk  i  Data of children  
    disk_read(&tree->child[i]);  
  
    //  Recursively continue to find in the tree  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)  
{
      
    assert(tree);  
  
    int i;  
  
#ifdef DEBUG_BTREE 
    printf("\n  Start to create  B- Trees , Keyword is :\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 Insert keywords  %c:\n", data[i]);  
#endif 
        int pos = -1;  
        BTree_search(*tree,data[i],&pos);// Recursive search of trees . 
        if (pos!=-1)  
        {
      
            printf("this key %c is in the B-tree,not to insert.\n",data[i]);  
        }else{
      
            BTree_insert(tree, data[i]);// Insert elements into BTree in . 
        }  
  
#ifdef DEBUG_BTREE 
        BTree_print(*tree);// Depth traversal of trees . 
#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;  
}