B-Tree (JS)

BTree.js

class BTreeNode {
    constructor(isLeaf = true) {
        this.isLeaf = isLeaf;
        this.keys = [];      // Array of keys
        this.children = [];   // Array of child pointers (BTreeNode instances)
    }
}

class BTree {
    constructor(order = 3) {
        this.root = new BTreeNode();
        this.order = order; // Maximum children per node
    }

    // Insert a key into the B-Tree
    insert(key) {
        const root = this.root;
        
        if (root.keys.length === this.order - 1) {
            // Root is full, split and create new root
            const newRoot = new BTreeNode(false);
            newRoot.children.push(root);
            this.splitChild(newRoot, 0, root);
            this.root = newRoot;
            this.insertNonFull(newRoot, key);
        } else {
            // Insert in non-full node
            this.insertNonFull(root, key);
        }
    }

    // Insert a key into a node that is not full
    insertNonFull(node, key) {
        let i = node.keys.length - 1;

        if (node.isLeaf) {
            // Insert key in the leaf node
            while (i >= 0 && key < node.keys[i]) {
                i--;
            }
            node.keys.splice(i + 1, 0, key); // Insert key in the sorted position
        } else {
            // Find the child where the key should be inserted
            while (i >= 0 && key < node.keys[i]) {
                i--;
            }
            i++;

            if (node.children[i].keys.length === this.order - 1) {
                // Split the child if it is full
                this.splitChild(node, i, node.children[i]);

                // After splitting, the middle key moves up, so we need to decide which child to insert into
                if (key > node.keys[i]) {
                    i++;
                }
            }
            this.insertNonFull(node.children[i], key);
        }
    }

    // Split a full child node into two nodes and move the middle key up
    splitChild(parent, index, child) {
        const newChild = new BTreeNode(child.isLeaf);
        const mid = Math.floor((this.order - 1) / 2);

        // Move keys and children to newChild
        newChild.keys = child.keys.splice(mid + 1);
        if (!child.isLeaf) {
            newChild.children = child.children.splice(mid + 1);
        }

        // Insert the middle key into the parent
        parent.keys.splice(index, 0, child.keys[mid]);
        parent.children.splice(index + 1, 0, newChild);

        // Remove the middle key from the original child
        child.keys.splice(mid, 1);
    }

    // In-order traversal for debugging
    inOrderTraversal(node = this.root, result = []) {
        if (node) {
            let i;
            for (i = 0; i < node.keys.length; i++) {
                // Traverse left child
                if (!node.isLeaf) {
                    this.inOrderTraversal(node.children[i], result);
                }
                // Add key to result
                result.push(node.keys[i]);
            }
            // Traverse the rightmost child
            if (!node.isLeaf) {
                this.inOrderTraversal(node.children[i], result);
            }
        }
        return result;
    }
}

// Example usage:
const bTree = new BTree(3);
bTree.insert(10);
bTree.insert(20);
bTree.insert(5);
bTree.insert(6);
bTree.insert(12);
bTree.insert(30);
bTree.insert(7);
bTree.insert(17);

console.log("In-order traversal:", bTree.inOrderTraversal()); // Should print keys in sorted order