B-tree-DevsEnv

Algorithm

A B-tree, short for "balanced tree," is a self-balancing tree data structure that maintains sorted data and allows for efficient search, insertion, deletion, and sequential access. B-trees are commonly used in databases and file systems where large amounts of data need to be stored and accessed quickly.

Here are some key characteristics and features of B-trees:

Balanced Structure: B-trees are balanced, meaning that all leaf nodes of the tree are at the same level. This balance is maintained during insertions and deletions, ensuring that the height of the tree remains relatively small, leading to efficient operations.
Node Structure: Each node in a B-tree contains a certain number of keys and pointers to child nodes. The number of keys in a node is within a specified range, and it is designed to optimize disk I/O by accommodating a large number of keys in each node.
Sorted Order: The keys within each node are stored in sorted order, allowing for efficient search operations using a binary search. This sorting property extends to all the nodes of the tree.
Search Operation: Searching in a B-tree is similar to searching in a binary search tree. Starting from the root, comparisons are made to determine the path to follow down the tree until the desired key is found or a leaf node is reached.
Insertion and Deletion: Inserting or deleting a key in a B-tree involves maintaining the balance of the tree. The tree is modified to ensure that it remains balanced, and nodes are split or merged as needed.
Use Cases: B-trees are commonly used in scenarios where large amounts of data need to be stored and efficiently accessed, such as in databases and file systems. They are well-suited for applications that involve frequent insertions and deletions.
Variants: There are variations of B-trees, including B+ trees and B* trees, each with specific characteristics. B+ trees, for example, store keys only in the leaf nodes, which simplifies range queries.

Code Examples

#1 B-tree implement in Python

Code - Python Programming

class BTreeNode:
    def __init__(self, leaf=True):
        self.leaf = leaf
        self.keys = []
        self.children = []

class BTree:
    def __init__(self, t):
        self.root = BTreeNode()
        self.t = t  # Minimum degree

    def insert(self, key):
        root = self.root
        if len(root.keys) == (2 * self.t) - 1:
            new_root = BTreeNode(leaf=False)
            new_root.children.append(self.root)
            self.split(new_root, 0)
            self.root = new_root
        self.insert_non_full(self.root, key)

    def insert_non_full(self, x, key):
        i = len(x.keys) - 1
        if x.leaf:
            x.keys.append(None)
            while i >= 0 and key < x.keys[i]:
                x.keys[i + 1] = x.keys[i]
                i -= 1
            x.keys[i + 1] = key
        else:
            while i >= 0 and key < x.keys[i]:
                i -= 1
            i += 1
            if len(x.children[i].keys) == (2 * self.t) - 1:
                self.split(x, i)
                if key > x.keys[i]:
                    i += 1
            self.insert_non_full(x.children[i], key)

    def split(self, x, i):
        t = self.t
        y = x.children[i]
        z = BTreeNode(leaf=y.leaf)
        x.children.insert(i + 1, z)
        x.keys.insert(i, y.keys[t - 1])
        z.keys = y.keys[t:(2 * t) - 1]
        y.keys = y.keys[0:t - 1]
        if not y.leaf:
            z.children = y.children[t:2 * t]
            y.children = y.children[0:t - 1]

    def print_tree(self, x, l=0):
        print("Level ", l, ":", len(x.keys), end=" ")
        for key in x.keys:
            print(key, end=" ")
        print()
        l += 1
        if len(x.children) > 0:
            for child in x.children:
                self.print_tree(child, l)

# Example usage:
if __name__ == "__main__":
    b_tree = BTree(t=3)
    keys = [3, 7, 1, 8, 2, 6, 4, 10, 9, 5]
    
    for key in keys:
        b_tree.insert(key)

    print("B-tree after insertion:")
    b_tree.print_tree(b_tree.root)

Copy The Code & Try With Live Editor

#2 B-tree implement in Java

Code - Java Programming

class BTreeNode {
    int[] keys;
    int t; // Minimum degree
    BTreeNode[] children;
    int n; // Current number of keys
    boolean leaf;

    public BTreeNode(int t, boolean leaf) {
        this.t = t;
        this.leaf = leaf;
        this.keys = new int[2 * t - 1];
        this.children = new BTreeNode[2 * t];
        this.n = 0;
    }
}

public class BTree {
    private BTreeNode root;
    private int t; // Minimum degree

    public BTree(int t) {
        this.root = null;
        this.t = t;
    }

    public void insert(int key) {
        if (root == null) {
            root = new BTreeNode(t, true);
            root.keys[0] = key;
            root.n = 1;
        } else {
            if (root.n == 2 * t - 1) {
                BTreeNode newRoot = new BTreeNode(t, false);
                newRoot.children[0] = root;
                splitChild(newRoot, 0);
                root = newRoot;
            }
            insertNonFull(root, key);
        }
    }

    private void insertNonFull(BTreeNode x, int key) {
        int i = x.n - 1;
        if (x.leaf) {
            while (i >= 0 && key  <  x.keys[i]) {
                x.keys[i + 1] = x.keys[i];
                i--;
            }
            x.keys[i + 1] = key;
            x.n++;
        } else {
            while (i >= 0 && key  <  x.keys[i]) {
                i--;
            }
            i++;
            if (x.children[i].n == 2 * t - 1) {
                splitChild(x, i);
                if (key > x.keys[i]) {
                    i++;
                }
            }
            insertNonFull(x.children[i], key);
        }
    }

    private void splitChild(BTreeNode x, int i) {
        BTreeNode y = x.children[i];
        BTreeNode z = new BTreeNode(t, y.leaf);
        x.children[x.n + 1] = null;
        x.n++;
        for (int j = t - 1; j  <  2 * t - 2; j++) {
            z.keys[j - t + 1] = y.keys[j];
        }
        y.n = t - 1;
        z.n = t - 1;
        for (int j = t - 2; j >= 0; j--) {
            y.keys[j] = 0;
        }
        for (int j = x.n - 1; j > i; j--) {
            x.keys[j] = x.keys[j - 1];
            x.children[j + 1] = x.children[j];
        }
        x.keys[i] = y.keys[t - 1];
        x.children[i + 1] = z;
        y.keys[t - 1] = 0;
    }

    public boolean search(int key) {
        return search(root, key);
    }

    private boolean search(BTreeNode x, int key) {
        int i = 0;
        while (i  <  x.n && key > x.keys[i]) {
            i++;
        }
        if (i < x.n && key == x.keys[i]) {
            return true;
        } else if (x.leaf) {
            return false;
        } else {
            return search(x.children[i], key);
        }
    }

    public static void main(String[] args) {
        BTree bTree = new BTree(3);

        // Insert keys
        int[] keys = {3, 7, 1, 5, 11, 8, 14, 2, 6, 9, 13, 15};
        for (int key : keys) {
            bTree.insert(key);
        }

        // Search for keys
        System.out.println(bTree.search(6)); // true
        System.out.println(bTree.search(10)); // false
    }
}

Copy The Code & Try With Live Editor

#3 B-tree implement in C

Code - C Programming

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

// B-tree node structure
typedef struct BTreeNode {
    int *keys;    // Array of keys
    struct BTreeNode **children;  // Array of child pointers
    int n;        // Current number of keys
    int leaf;     // 1 if the node is a leaf, 0 otherwise
} BTreeNode;

// Function to create a new B-tree node
BTreeNode *createNode(int leaf) {
    BTreeNode *newNode = (BTreeNode *)malloc(sizeof(BTreeNode));
    newNode->keys = (int *)malloc(sizeof(int) * 2);  // Assuming a B-tree of order 2
    newNode->children = (BTreeNode **)malloc(sizeof(BTreeNode *) * 3);  // Assuming a B-tree of order 2
    newNode->n = 0;
    newNode->leaf = leaf;
    return newNode;
}

// Function to split a full child of a node
void splitChild(BTreeNode *parent, int index, BTreeNode *child) {
    BTreeNode *newChild = createNode(child->leaf);
    newChild->n = 1;

    // Move the middle key to the parent node
    parent->keys[index] = child->keys[1];

    // Move the second half of the keys to the new child
    newChild->keys[0] = child->keys[2];
    newChild->children[0] = child->children[2];
    newChild->children[1] = child->children[3];

    child->n = 1;

    // Update the parent's children array
    for (int i = parent->n; i > index + 1; i--) {
        parent->children[i] = parent->children[i - 1];
    }

    // Insert the new child in the parent's children array
    parent->children[index + 1] = newChild;
    parent->n++;
}

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

    insertNonFull(root, key);
}

// Function to insert a key into a non-full node
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 == 2) {
            splitChild(node, i, node->children[i]);
            if (key > node->keys[i]) {
                i++;
            }
        }

        insertNonFull(node->children[i], key);
    }
}

// Function to search for a key in the B-tree
BTreeNode *search(BTreeNode *root, int key) {
    int i = 0;

    while (i  <  root->n && key > root->keys[i]) {
        i++;
    }

    if (i < root->n && key == root->keys[i]) {
        return root;
    } else if (root->leaf) {
        return NULL;
    } else {
        return search(root->children[i], key);
    }
}

// Function to print the B-tree in-order
void inOrderTraversal(BTreeNode *root) {
    if (root != NULL) {
        for (int i = 0; i  <  root->n; i++) {
            inOrderTraversal(root->children[i]);
            printf("%d ", root->keys[i]);
        }
        inOrderTraversal(root->children[root->n]);
    }
}

// Function to free the memory allocated for the B-tree
void freeBTree(BTreeNode *root) {
    if (root != NULL) {
        for (int i = 0; i  < = root->n; i++) {
            freeBTree(root->children[i]);
        }
        free(root->keys);
        free(root->children);
        free(root);
    }
}

int main() {
    BTreeNode *root = createNode(1);  // Creating a B-tree with a leaf node

    int keys[] = {3, 8, 2, 7, 6, 1, 5, 4};
    int numKeys = sizeof(keys) / sizeof(keys[0]);

    for (int i = 0; i  <  numKeys; i++) {
        insert(root, keys[i]);
    }

    printf("In-order traversal of the B-tree: ");
    inOrderTraversal(root);
    printf("\n");

    int searchKey = 5;
    BTreeNode *result = search(root, searchKey);
    if (result != NULL) {
        printf("Key %d found in the B-tree.\n", searchKey);
    } else {
        printf("Key %d not found in the B-tree.\n", searchKey);
    }

    // Free the allocated memory for the B-tree
    freeBTree(root);

    return 0;
}

Copy The Code & Try With Live Editor

#4 B-tree implement in C++

Code - C++ Programming

#include <iostream>
#include <vector>

const int T = 2; // Degree of the B-tree

// Node structure for the B-tree
template  < typename KeyType, typename ValueType>
struct BTreeNode {
    bool isLeaf;
    std::vector<KeyType> keys;
    std::vector < ValueType> values;
    std::vector<BTreeNode*> children;

    BTreeNode(bool leaf = true) : isLeaf(leaf) {}

    ~BTreeNode() {
        for (auto child : children) {
            delete child;
        }
    }
};

// B-tree class
template  < typename KeyType, typename ValueType>
class BTree {
private:
    BTreeNode* root;

public:
    BTree() : root(nullptr) {}

    ~BTree() {
        delete root;
    }

    // Function to search for a key in the B-tree
    ValueType search(const KeyType& key) {
        return searchKey(root, key);
    }

    // Function to insert a key-value pair into the B-tree
    void insert(const KeyType& key, const ValueType& value) {
        if (root == nullptr) {
            root = new BTreeNode < KeyType, ValueType>(true);
            root->keys.push_back(key);
            root->values.push_back(value);
        } else {
            if (root->keys.size() == 2 * T - 1) {
                BTreeNode < KeyType, ValueType>* newRoot = new BTreeNode(false);
                newRoot->children.push_back(root);
                splitChild(newRoot, 0);
                root = newRoot;
            }
            insertNonFull(root, key, value);
        }
    }

private:
    // Function to search for a key in a B-tree node
    ValueType searchKey(BTreeNode < KeyType, ValueType>* node, const KeyType& key) {
        if (node != nullptr) {
            size_t i = 0;
            while (i < node->keys.size() && key > node->keys[i]) {
                i++;
            }
            if (i  <  node->keys.size() && key == node->keys[i]) {
                return node->values[i];
            } else if (node->isLeaf) {
                return ValueType(); // Key not found
            } else {
                return searchKey(node->children[i], key);
            }
        }
        return ValueType(); // Key not found
    }

    // Function to insert a key-value pair into a non-full B-tree node
    void insertNonFull(BTreeNode < KeyType, ValueType>* node, const KeyType& key, const ValueType& value) {
        int i = node->keys.size() - 1;
        if (node->isLeaf) {
            node->keys.push_back(KeyType());
            node->values.push_back(ValueType());
            while (i >= 0 && key  <  node->keys[i]) {
                node->keys[i + 1] = node->keys[i];
                node->values[i + 1] = node->values[i];
                i--;
            }
            node->keys[i + 1] = key;
            node->values[i + 1] = value;
        } else {
            while (i >= 0 && key  <  node->keys[i]) {
                i--;
            }
            i++;
            if (node->children[i]->keys.size() == 2 * T - 1) {
                splitChild(node, i);
                if (key > node->keys[i]) {
                    i++;
                }
            }
            insertNonFull(node->children[i], key, value);
        }
    }

    // Function to split a full child of a B-tree node
    void splitChild(BTreeNode < KeyType, ValueType>* parent, int index) {
        BTreeNode* child = parent->children[index];
        BTreeNode* newChild = new BTreeNode(child->isLeaf);

        parent->keys.insert(parent->keys.begin() + index, child->keys[T - 1]);
        parent->values.insert(parent->values.begin() + index, child->values[T - 1]);

        newChild->keys.assign(child->keys.begin() + T, child->keys.end());
        newChild->values.assign(child->values.begin() + T, child->values.end());
        child->keys.resize(T - 1);
        child->values.resize(T - 1);

        if (!child->isLeaf) {
            newChild->children.assign(child->children.begin() + T, child->children.end());
            child->children.resize(T);
        }

        parent->children.insert(parent->children.begin() + index + 1, newChild);
    }
};

int main() {
    BTree < int, std::string> btree;

    // Inserting key-value pairs into the B-tree
    btree.insert(3, "Apple");
    btree.insert(7, "Banana");
    btree.insert(12, "Cherry");
    btree.insert(5, "Date");
    btree.insert(20, "Fig");
    btree.insert(15, "Grapes");

    // Searching for keys in the B-tree
    std::cout << "Value for key 7: " << btree.search(7) << std::endl;
    std::cout << "Value for key 15: " << btree.search(15) << std::endl;
    std::cout << "Value for key 10: " << btree.search(10) << std::endl;

    return 0;
}

Copy The Code & Try With Live Editor

Demonstration

B-tree-DevsEnv

Try With Live Editor

Category - Data Structure and Algorithm Maniruzzaman Akash 11 months ago 442 0