B-Tree Implementation in C

A B-tree is a self-balancing tree data structure that maintains sorted data and allows for efficient insertion, deletion, and search operations. It is particularly useful in databases and file systems for indexing because it keeps data balanced and minimizes the number of disk accesses required for operations.

Program Structure

This implementation of a B-tree in C will include the following components:

1. Struct definitions for the B-tree node and the B-tree itself.
2. Functions to create and initialize B-tree nodes and the B-tree.
3. Functions to search for a key, insert a key, and split child nodes.
4. A main function to demonstrate the usage of the B-tree for insertion and search operations.

Code Implementation

#include <stdio.h>
#include <stdlib.h>

#define MAX 3  // Maximum degree of the B-tree (T)
#define MIN (MAX + 1)/2

// B-tree node structure
typedef struct BTreeNode {
    int keys[MAX];             // Array of keys
    struct BTreeNode *children[MAX + 1];  // Array of child pointers
    int n;                     // Number of keys currently in the node
    int leaf;                  // 1 if leaf node, 0 otherwise
} BTreeNode;

// B-tree structure
typedef struct BTree {
    BTreeNode *root;  // Pointer to the root node
} BTree;

// Function to create a new B-tree node
BTreeNode* createNode(int leaf) {
    BTreeNode *newNode = (BTreeNode*)malloc(sizeof(BTreeNode));
    newNode->leaf = leaf;
    newNode->n = 0;
    for (int i = 0; i <= MAX; i++) { newNode->children[i] = NULL;
    }
    return newNode;
}

// Function to create a new B-tree
BTree* createBTree() {
    BTree *newTree = (BTree*)malloc(sizeof(BTree));
    newTree->root = createNode(1);  // Start with an empty leaf node
    return newTree;
}

// Function to search for a key in the B-tree
BTreeNode* search(BTreeNode *node, int key) {
    int i = 0;
    while (i < node->n && key > node->keys[i]) {
        i++;
    }

    if (i < node->n && key == node->keys[i]) {
        return node;
    }

    if (node->leaf) {
        return NULL;
    } else {
        return search(node->children[i], key);
    }
}

// Function to split the child node when it is full
void splitChild(BTreeNode *parent, int i, BTreeNode *fullChild) {
    BTreeNode *newChild = createNode(fullChild->leaf);
    newChild->n = MIN - 1;

    for (int j = 0; j < MIN - 1; j++) { newChild->keys[j] = fullChild->keys[j + MIN];
    }

    if (!fullChild->leaf) {
        for (int j = 0; j < MIN; j++) { newChild->children[j] = fullChild->children[j + MIN];
        }
    }

    fullChild->n = MIN - 1;

    for (int j = parent->n; j >= i + 1; j--) {
        parent->children[j + 1] = parent->children[j];
    }

    parent->children[i + 1] = newChild;

    for (int j = parent->n - 1; j >= i; j--) {
        parent->keys[j + 1] = parent->keys[j];
    }

    parent->keys[i] = fullChild->keys[MIN - 1];
    parent->n++;
}

// Function to insert a key in the B-tree
void insertNonFull(BTreeNode *node, int key) {
    int i = node->n - 1;

    if (node->leaf) {
        while (i >= 0 && key < node->keys[i]) {
            node->keys[i + 1] = node->keys[i];
            i--;
        }

        node->keys[i + 1] = key;
        node->n++;
    } else {
        while (i >= 0 && key < node->keys[i]) {
            i--;
        }
        i++;

        if (node->children[i]->n == MAX) {
            splitChild(node, i, node->children[i]);
            if (key > node->keys[i]) {
                i++;
            }
        }
        insertNonFull(node->children[i], key);
    }
}

// Function to insert a key in the B-tree
void insert(BTree *tree, int key) {
    BTreeNode *root = tree->root;
    if (root->n == MAX) {
        BTreeNode *newRoot = createNode(0);
        newRoot->children[0] = root;
        splitChild(newRoot, 0, root);
        tree->root = newRoot;
        insertNonFull(newRoot, key);
    } else {
        insertNonFull(root, key);
    }
}

// Main function to demonstrate the usage of the B-tree
int main() {
    BTree *tree = createBTree();

    // Insert keys into the B-tree
    insert(tree, 10);
    insert(tree, 20);
    insert(tree, 5);
    insert(tree, 6);
    insert(tree, 12);
    insert(tree, 30);
    insert(tree, 7);
    insert(tree, 17);

    // Search for a key in the B-tree
    int key = 6;
    BTreeNode *result = search(tree->root, key);
    if (result != NULL) {
        printf("Key %d found in B-tree.\n", key);
    } else {
        printf("Key %d not found in B-tree.\n", key);
    }

    return 0;
}

Explanation

The program implements a B-tree in C, which is used for database indexing due to its efficient insertion, deletion, and search capabilities. The B-tree is structured such that each node contains multiple keys and child pointers, and the tree is balanced by design.

The B-tree node structure, BTreeNode, includes an array of keys, an array of child pointers, a count of the current number of keys in the node, and a boolean to indicate if the node is a leaf.

The createNode() function initializes a new B-tree node, and createBTree() initializes an empty B-tree with a root node. The search() function searches for a given key in the B-tree and returns the node where the key is found, or NULL if the key is not present.

Inserting a key into the B-tree involves several steps:

• The insert() function handles cases where the root node is full by creating a new root and splitting the existing root node.
• The insertNonFull() function inserts a key into a node that is not full, placing the key in the appropriate position and maintaining the order of keys.
• If a child node is full when a new key needs to be inserted, the splitChild() function splits the child node, promoting a key to the parent node and creating a new sibling node.

In the main() function, we demonstrate the B-tree’s functionality by inserting several keys and searching for a specific key to show how the B-tree handles data.