Overview

The B-Tree is a self-balancing search tree data structure designed for efficient storage and retrieval of sorted data. Unlike binary search trees, B-Trees can have multiple keys per node and multiple children, making them particularly well-suited for disk-based storage systems where reading large blocks of data is costly.

Historical Background

B-Trees were introduced in 1972 by Rudolf Bayer and Edward M. McCreight in their seminal paper "Organization and Maintenance of Large Ordered Indexes," published in ACM Transactions on Database Systems. The structure was designed to optimize operations on large ordered indexes stored on disk, where minimizing the number of disk accesses is crucial for performance.

The "B" in B-Tree has never been officially explained by its creators. Various interpretations have been proposed over the years, including "balanced," "broad," "bushy," and even "Boeing" (since Bayer worked at Boeing at the time). McCreight himself once noted that the more you think about what the "B" stands for, the better you understand B-Trees—suggesting the meaning may be deliberately ambiguous or simply lost to history.

Key Properties

A B-Tree maintains the following characteristics:

Property 1 - Node Structure: Each node contains:

• A keyCount field representing the number of keys currently stored
• An array of keys stored in sorted ascending order
• A array of child pointers (for non-leaf nodes)
• A isLeaf boolean flag indicating whether the node is a leaf

Property 2 - Child Count: Non-leaf nodes have one more child than they have keys. If a node has n keys, it has n + 1 children.

Property 3 - Degree Constraints: The minimum degree t (where t >= 2) defines the key count bounds for each node:

When a node reaches its maximum key capacity, it must be split.

Property 4 - Balanced Height: All leaf nodes reside at the same depth, ensuring uniform search performance across the tree.

Relationship with 2-3 Trees

B-Trees generalize several earlier balanced tree structures:

• 2-3 Tree: A B-Tree with minimum degree t=2, where each node contains 1-2 keys and has 2-3 children
• 2-3-4 Tree: A B-Tree with minimum degree t=2, supporting 1-3 keys per node and 2-4 children
• B-Tree: The generalized form where the degree can be any value >= 2

This hierarchical relationship shows that 2-3 trees are a specific instance of B-Trees with constrained parameters.

Implementation

Node Definition

class BTreeNode {
    boolean isLeaf;
    int currentSize;
    int minimumDegree;
    int[] keys;
    BTreeNode[] childNodes;
    
    BTreeNode(int degree) {
        this.minimumDegree = degree;
        this.keys = new int[2 * degree - 1];
        this.childNodes = new BTreeNode[2 * degree];
    }
    
    int findKeyPosition(int target) {
        int pos = 0;
        while (pos < currentSize && keys[pos] < target) {
            pos++;
        }
        return pos;
    }
}

Search Operation

BTreeNode search(BTreeNode node, int target) {
    int i = findKeyPosition(target);
    
    if (i < node.currentSize && node.keys[i] == target) {
        return node;
    }
    
    if (node.isLeaf) {
        return null;
    }
    
    return search(node.childNodes[i], target);
}

Key and Child Insertion Helpers

void addKeyToNode(int key, int position) {
    for (int j = currentSize - 1; j >= position; j--) {
        keys[j + 1] = keys[j];
    }
    keys[position] = key;
    currentSize++;
}

void addChildToNode(BTreeNode child, int position) {
    for (int j = currentSize - 1; j >= position; j--) {
        childNodes[j + 1] = childNodes[j];
    }
    childNodes[position] = child;
}

Tree Structure

public class BTree {
    private BTreeNode rootNode;
    private final int degree;
    private final int minKeys;
    private final int maxKeys;
    
    public BTree(int degree) {
        this.degree = degree;
        this.minKeys = degree - 1;
        this.maxKeys = 2 * degree - 1;
        this.rootNode = new BTreeNode(degree);
    }
}

Insertion with Splitting

public void insert(int key) {
    insertInternal(rootNode, key);
}

private void insertInternal(BTreeNode node, int key) {
    int i = node.findKeyPosition(key);
    
    if (node.keys[i] == key) {
        return;
    }
    
    if (node.isLeaf) {
        node.addKeyToNode(key, i);
    } else {
        insertInternal(node.childNodes[i], key);
    }
    
    if (node.currentSize == maxKeys) {
        splitNode(node, i);
    }
}

void splitNode(BTreeNode parentNode, int childIndex) {
    if (parentNode == rootNode && parentNode.currentSize == 0) {
        BTreeNode newRoot = new BTreeNode(degree);
        newRoot.isLeaf = false;
        newRoot.childNodes[0] = rootNode;
        rootNode = newRoot;
        parentNode = newRoot;
    }
    
    BTreeNode leftChild = parentNode.childNodes[childIndex];
    BTreeNode rightChild = new BTreeNode(degree);
    rightChild.isLeaf = leftChild.isLeaf;
    rightChild.currentSize = degree - 1;
    
    System.arraycopy(leftChild.keys, degree, rightChild.keys, 0, degree - 1);
    
    if (!leftChild.isLeaf) {
        System.arraycopy(leftChild.childNodes, degree, rightChild.childNodes, 0, degree);
    }
    
    leftChild.currentSize = degree - 1;
    
    int promotionKey = leftChild.keys[degree - 1];
    parentNode.addKeyToNode(promotionKey, childIndex);
    parentNode.addChildToNode(rightChild, childIndex + 1);
}

The split operation handles two scenarios: when splitting the root, a new root is created; otherwise, the middle key is promoted to the parent, and the remaining keys are distributed between the two split nodes.

Deletion Algorithm

B-Tree deletion involves several cases based on key location and node balance:

1. Key in leaf node: Direct removal if key exists
2. Key in internal node: Replace with predecessor or successor, then delete from appropriate child
3. Underflow prevention: Before descending to a child, ensure it has sufficient keys by borrowing from siblings or merging
4. Root special case: Reduce tree height when root has no keys and has only one child

public void delete(int key) {
    deleteInternal(rootNode, key);
}

private void deleteInternal(BTreeNode node, int key) {
    int i = node.findKeyPosition(key);
    
    if (node.isLeaf) {
        if (foundKey(node, key, i)) {
            removeKeyFromNode(node, i);
        }
        return;
    }
    
    if (foundKey(node, key, i)) {
        BTreeNode successor = node.childNodes[i + 1];
        while (!successor.isLeaf) {
            successor = successor.childNodes[0];
        }
        int replacement = successor.keys[0];
        node.keys[i] = replacement;
        deleteInternal(node.childNodes[i + 1], replacement);
    } else {
        deleteInternal(node.childNodes[i], key);
    }
    
    if (node.currentSize < minKeys) {
        rebalance(node, i);
    }
}

Rebalancing Operations

private void rebalance(BTreeNode node, int index) {
    if (node == rootNode) {
        if (rootNode.currentSize == 0 && rootNode.childNodes[0] != null) {
            rootNode = rootNode.childNodes[0];
        }
        return;
    }
    
    BTreeNode leftSib = node.childNodes[index - 1];
    BTreeNode rightSib = node.childNodes[index + 1];
    
    if (leftSib != null && leftSib.currentSize > minKeys) {
        rotateRight(node, leftSib, index);
        return;
    }
    
    if (rightSib != null && rightSib.currentSize > minKeys) {
        rotateLeft(node, rightSib, index);
        return;
    }
    
    if (leftSib != null) {
        mergeWithLeft(leftSib, node, index - 1);
    } else {
        mergeWithLeft(node, node, index);
    }
}

private void rotateRight(BTreeNode parent, BTreeNode leftSibling, int index) {
    int parentKey = leftSibling.keys[leftSibling.currentSize - 1];
    int pushedKey = parent.keys[index - 1];
    
    shiftNodeKeys(parent, index - 1, parentKey);
    
    if (!leftSibling.isLeaf) {
        shiftNodeChildren(parent, 0, leftSibling.childNodes[leftSibling.currentSize]);
    }
}

private void rotateLeft(BTreeNode parent, BTreeNode rightSibling, int index) {
    int parentKey = parent.keys[index];
    int pushedKey = rightSibling.keys[0];
    
    shiftNodeKeys(parent, index, pushedKey);
    
    if (!rightSibling.isLeaf) {
        shiftNodeChildren(parent, parent.currentSize + 1, rightSibling.childNodes[0]);
    }
}

Performance Characteristics

For a B-Tree with minimum degree t and n total keys:

• Height: O(log_t n) - significantly shallower than equivalent binary trees
• Search: O(log_t n) comparisons
• Insert/Delete: O(log_t n) with node splitting or merging as needed
• Space: Nearly optimal, with at least 50% utilization guaranteed under normal operations

For comparison, storing one million keys in a B-Tree with t=500 results in a height of approximately 3, compared to around 20 for an equivalent AVL tree, dramatically reducing disk access requirements.

Complete Implementation

public class BTree {
    
    static class Node {
        int[] keys;
        Node[] children;
        int keyCount;
        boolean isLeaf;
        int degree;

        Node(int degree) {
            this.degree = degree;
            this.keys = new int[2 * degree - 1];
            this.children = new Node[2 * degree];
        }

        int locateKey(int target) {
            int pos = 0;
            while (pos < keyCount && keys[pos] < target) {
                pos++;
            }
            return pos;
        }

        void insertKeyAt(int key, int position) {
            for (int j = keyCount - 1; j >= position; j--) {
                keys[j + 1] = keys[j];
            }
            keys[position] = key;
            keyCount++;
        }

        void insertChildAt(Node child, int position) {
            for (int j = keyCount - 1; j >= position; j--) {
                children[j + 1] = children[j];
            }
            children[position] = child;
        }

        int extractKey(int index) {
            int value = keys[index];
            for (int j = index; j < keyCount - 1; j++) {
                keys[j] = keys[j + 1];
            }
            keyCount--;
            return value;
        }

        Node extractChild(int index) {
            Node removed = children[index];
            for (int j = index; j < keyCount; j++) {
                children[j] = children[j + 1];
            }
            children[keyCount] = null;
            return removed;
        }

        Node getLeftNeighbor(int index) {
            return index > 0 ? children[index - 1] : null;
        }

        Node getRightNeighbor(int index) {
            return index == keyCount ? null : children[index + 1];
        }

        void transferTo(Node target) {
            if (!isLeaf) {
                for (int i = 0; i <= keyCount; i++) {
                    target.children[target.keyCount + i] = children[i];
                }
            }
            for (int i = 0; i < keyCount; i++) {
                target.keys[target.keyCount++] = keys[i];
            }
        }
    }

    private Node root;
    private final int degree;
    private final int minKeys;
    private final int maxKeys;

    public BTree(int degree) {
        this.degree = degree;
        this.minKeys = degree - 1;
        this.maxKeys = 2 * degree - 1;
        this.root = new Node(degree);
    }

    public boolean contains(int key) {
        return search(root, key) != null;
    }

    private Node search(Node node, int key) {
        int i = node.locateKey(key);
        
        if (i < node.keyCount && node.keys[i] == key) {
            return node;
        }
        
        if (node.isLeaf) {
            return null;
        }
        
        return search(node.children[i], key);
    }

    public void insert(int key) {
        insertRecursive(root, key, null, 0);
    }

    private void insertRecursive(Node node, int key, Node parent, int childIndex) {
        int i = node.locateKey(key);
        
        if (node.keys[i] == key) {
            return;
        }
        
        if (node.isLeaf) {
            node.insertKeyAt(key, i);
        } else {
            insertRecursive(node.children[i], key, node, i);
        }
        
        if (node.keyCount == maxKeys) {
            performSplit(node, parent, childIndex);
        }
    }

    private void performSplit(Node node, Node parent, int childIndex) {
        if (parent == null) {
            Node newRoot = new Node(degree);
            newRoot.isLeaf = false;
            newRoot.children[0] = node;
            this.root = newRoot;
            parent = newRoot;
        }
        
        Node rightNode = new Node(degree);
        rightNode.isLeaf = node.isLeaf;
        rightNode.keyCount = degree - 1;
        
        System.arraycopy(node.keys, degree, rightNode.keys, 0, degree - 1);
        
        if (!node.isLeaf) {
            System.arraycopy(node.children, degree, rightNode.children, 0, degree);
            for (int i = degree; i <= node.keyCount; i++) {
                node.children[i] = null;
            }
        }
        
        node.keyCount = degree - 1;
        
        int promotedKey = node.keys[degree - 1];
        parent.insertKeyAt(promotedKey, childIndex);
        parent.insertChildAt(rightNode, childIndex + 1);
    }

    public void remove(int key) {
        removeRecursive(root, key, null, 0);
    }

    private void removeRecursive(Node node, int key, Node parent, int index) {
        int i = node.locateKey(key);
        
        if (node.isLeaf) {
            if (!keyExists(node, key, i)) {
                return;
            }
            node.extractKey(i);
        } else {
            if (!keyExists(node, key, i)) {
                removeRecursive(node.children[i], key, node, i);
            } else {
                Node successor = node.children[i + 1];
                while (!successor.isLeaf) {
                    successor = successor.children[0];
                }
                int replacement = successor.keys[0];
                node.keys[i] = replacement;
                removeRecursive(node.children[i + 1], replacement, node, i + 1);
            }
        }
        
        if (node.keyCount < minKeys) {
            fixUnderflow(node, parent, index);
        }
    }

    private boolean keyExists(Node node, int key, int i) {
        return i < node.keyCount && node.keys[i] == key;
    }

    private void fixUnderflow(Node node, Node parent, int index) {
        if (node == root) {
            if (root.keyCount == 0 && root.children[0] != null) {
                root = root.children[0];
            }
            return;
        }
        
        Node leftSib = node.getLeftNeighbor(index);
        Node rightSib = node.getRightNeighbor(index);
        
        if (leftSib != null && leftSib.keyCount > minKeys) {
            rotateFromRight(node, leftSib, parent, index);
            return;
        }
        
        if (rightSib != null && rightSib.keyCount > minKeys) {
            rotateFromLeft(node, rightSib, parent, index);
            return;
        }
        
        if (leftSib != null) {
            mergeNodes(leftSib, parent, index - 1);
        } else {
            mergeNodes(node, parent, index);
        }
    }

    private void rotateFromRight(Node target, Node source, Node parent, int index) {
        target.insertKeyAt(parent.keys[index - 1], 0);
        if (!source.isLeaf) {
            target.insertChildAt(source.extractChild(source.keyCount), 0);
        }
        parent.keys[index - 1] = source.keys[source.keyCount - 1];
    }

    private void rotateFromLeft(Node target, Node source, Node parent, int index) {
        target.insertKeyAt(parent.keys[index], target.keyCount);
        if (!source.isLeaf) {
            target.insertChildAt(source.extractChild(0), target.keyCount + 1);
        }
        parent.keys[index] = source.keys[0];
    }

    private void mergeNodes(Node left, Node parent, int index) {
        Node right = parent.extractChild(index + 1);
        left.insertKeyAt(parent.extractKey(index), left.keyCount);
        right.transferTo(left);
    }
}

Practical Applications

B-Trees form the foundation of modern database indexing systems. Their balanced nature and optimized disk access patterns make them ideal for:

• Database index structures (B+Tree variants)
• Filesystem metadata storage
• Key-value stores with ordered iteration requirements
• Any system requiring efficient range queries on sorted data