B-trees are height-balanced search trees dseigned to minimize I/O by packing many ordered keys into a single node sized to a disk block or cache line. Instead of assuming all data lives in main memory (as typical for AVL or Red-Black trees), B-trees optimize for large datasets by reducing the number of node visits (hence disk reads). If the height of the tree is h, search, insert, delete, min/max, and predecessor/successor operations require O(h) node accesses, typically O(log n).

Key properties (minimum degree t):

• Every node except the root stores between t−1 and 2t−1 keys; the root stores between 1 and 2t−1 keys (unless the tree is empty).
• Internal nodes with k keys have k+1 children.
• All leaves reside at the same depth.
• Keys within a node are strictly increasing; subtrees partition the key ranges accordingly.
• The tree grows and shrinks at the root. Node splits and merges maintain the invariants.

This implementation uses the standard top-down (proactive) insertion: on the way down, we split full children before descending, guaranteeing insertion always lands in a non-full leaf. Deletion follows the classic cases (borrow from siblings or merge) while ensuring we never descend into a child with fewer than t keys.

Java implementation (integer keys)

// B-Tree of integers with top-down insertion and full delete support
// Minimum degree t >= 2

class BTNode {
    final int t;                  // minimum degree
    int[] keys;                   // sorted keys
    BTNode[] kids;                // child pointers
    int keyCount;                 // number of valid keys
    boolean leaf;                 // is this a leaf

    BTNode(int t, boolean leaf) {
        this.t = t;
        this.leaf = leaf;
        this.keys = new int[2 * t - 1];
        this.kids = new BTNode[2 * t];
        this.keyCount = 0;
    }

    // Return the first index i such that keys[i] >= k (or keyCount if all < k)
    int findIndex(int k) {
        int i = 0;
        while (i < keyCount && keys[i] < k) i++;
        return i;
    }

    BTNode find(int k) {
        int i = 0;
        while (i < keyCount && k > keys[i]) i++;
        if (i < keyCount && keys[i] == k) return this;
        if (leaf) return null;
        return kids[i].find(k);
    }

    void traverse() {
        int i;
        for (i = 0; i < keyCount; i++) {
            if (!leaf) kids[i].traverse();
            System.out.print(" " + keys[i]);
        }
        if (!leaf) kids[i].traverse();
    }

    // Insert assuming this node is non-full
    void insertIntoNonFull(int k) {
        int i = keyCount - 1;
        if (leaf) {
            while (i >= 0 && keys[i] > k) {
                keys[i + 1] = keys[i];
                i--;
            }
            keys[i + 1] = k;
            keyCount++;
        } else {
            while (i >= 0 && keys[i] > k) i--;
            int childIdx = i + 1;
            if (kids[childIdx].keyCount == 2 * t - 1) {
                splitAt(childIdx, kids[childIdx]);
                if (keys[childIdx] < k) childIdx++;
            }
            kids[childIdx].insertIntoNonFull(k);
        }
    }

    // Split full child y at index i into y and z; promote median into this node
    void splitAt(int i, BTNode y) {
        BTNode z = new BTNode(y.t, y.leaf);
        z.keyCount = t - 1;

        // move top (t-1) keys from y to z
        for (int j = 0; j < t - 1; j++) z.keys[j] = y.keys[j + t];
        if (!y.leaf) {
            for (int j = 0; j < t; j++) z.kids[j] = y.kids[j + t];
        }
        y.keyCount = t - 1;

        // make room for new child
        for (int j = keyCount; j >= i + 1; j--) kids[j + 1] = kids[j];
        kids[i + 1] = z;

        // move median up
        for (int j = keyCount - 1; j >= i; j--) keys[j + 1] = keys[j];
        keys[i] = y.keys[t - 1];
        keyCount++;
    }

    void delete(int k) {
        int idx = findIndex(k);
        if (idx < keyCount && keys[idx] == k) {
            if (leaf) deleteFromLeaf(idx);
            else deleteFromInternal(idx);
        } else {
            if (leaf) {
                // key not present
                return;
            }
            boolean wasLast = (idx == keyCount);
            if (kids[idx].keyCount < t) fixChildSize(idx);
            // After fix, if we originally aimed past the last child and the node shrank,
            // move to the left sibling; otherwise continue with the same index.
            if (wasLast && idx > keyCount) {
                kids[idx - 1].delete(k);
            } else {
                kids[idx].delete(k);
            }
        }
    }

    private void deleteFromLeaf(int idx) {
        for (int i = idx + 1; i < keyCount; i++) keys[i - 1] = keys[i];
        keyCount--;
    }

    private void deleteFromInternal(int idx) {
        int k = keys[idx];
        if (kids[idx].keyCount >= t) {
            int pred = predecessor(idx);
            keys[idx] = pred;
            kids[idx].delete(pred);
        } else if (kids[idx + 1].keyCount >= t) {
            int succ = successor(idx);
            keys[idx] = succ;
            kids[idx + 1].delete(succ);
        } else {
            fuseChildren(idx);
            kids[idx].delete(k);
        }
    }

    private int predecessor(int idx) {
        BTNode cur = kids[idx];
        while (!cur.leaf) cur = cur.kids[cur.keyCount];
        return cur.keys[cur.keyCount - 1];
    }

    private int successor(int idx) {
        BTNode cur = kids[idx + 1];
        while (!cur.leaf) cur = cur.kids[0];
        return cur.keys[0];
    }

    private void fixChildSize(int idx) {
        if (idx > 0 && kids[idx - 1].keyCount >= t) {
            rotateFromLeft(idx);
        } else if (idx < keyCount && kids[idx + 1].keyCount >= t) {
            rotateFromRight(idx);
        } else {
            if (idx < keyCount) {
                fuseChildren(idx);
            } else {
                fuseChildren(idx - 1);
            }
        }
    }

    // Borrow one key from the left sibling
    private void rotateFromLeft(int idx) {
        BTNode child = kids[idx];
        BTNode left = kids[idx - 1];

        // shift child keys/children right by 1
        for (int i = child.keyCount - 1; i >= 0; i--) child.keys[i + 1] = child.keys[i];
        if (!child.leaf) {
            for (int i = child.keyCount; i >= 0; i--) child.kids[i + 1] = child.kids[i];
        }

        // move separator down to child
        child.keys[0] = keys[idx - 1];
        if (!child.leaf) child.kids[0] = left.kids[left.keyCount];

        // move left's last key up as new separator
        keys[idx - 1] = left.keys[left.keyCount - 1];

        child.keyCount++;
        left.keyCount--;
    }

    // Borrow one key from the right sibling
    private void rotateFromRight(int idx) {
        BTNode child = kids[idx];
        BTNode right = kids[idx + 1];

        // bring separator down
        child.keys[child.keyCount] = keys[idx];
        if (!child.leaf) child.kids[child.keyCount + 1] = right.kids[0];

        // new separator is right's first key
        keys[idx] = right.keys[0];

        // shift right sibling left by 1
        for (int i = 1; i < right.keyCount; i++) right.keys[i - 1] = right.keys[i];
        if (!right.leaf) {
            for (int i = 1; i <= right.keyCount; i++) right.kids[i - 1] = right.kids[i];
        }

        child.keyCount++;
        right.keyCount--;
    }

    // Merge kids[idx] and kids[idx+1] into a single node
    private void fuseChildren(int idx) {
        BTNode left = kids[idx];
        BTNode right = kids[idx + 1];

        // pull separator key into left
        left.keys[t - 1] = keys[idx];

        // copy right's keys and children into left
        for (int i = 0; i < right.keyCount; i++) left.keys[i + t] = right.keys[i];
        if (!left.leaf) {
            for (int i = 0; i <= right.keyCount; i++) left.kids[i + t] = right.kids[i];
        }

        // shift keys and children of current node left
        for (int i = idx + 1; i < keyCount; i++) keys[i - 1] = keys[i];
        for (int i = idx + 2; i <= keyCount; i++) kids[i - 1] = kids[i];

        left.keyCount += right.keyCount + 1;
        keyCount--;
    }
}

class BTreeInt {
    private BTNode root;
    private final int t;

    BTreeInt(int t) {
        if (t < 2) throw new IllegalArgumentException("Minimum degree must be >= 2");
        this.t = t;
        this.root = null;
    }

    void insert(int k) {
        if (root == null) {
            root = new BTNode(t, true);
            root.keys[0] = k;
            root.keyCount = 1;
            return;
        }
        if (root.keyCount == 2 * t - 1) {
            BTNode s = new BTNode(t, false);
            s.kids[0] = root;
            s.splitAt(0, root);
            int i = (s.keys[0] < k) ? 1 : 0;
            s.kids[i].insertIntoNonFull(k);
            root = s;
        } else {
            root.insertIntoNonFull(k);
        }
    }

    void delete(int k) {
        if (root == null) return;
        root.delete(k);
        if (root.keyCount == 0) {
            root = root.leaf ? null : root.kids[0];
        }
    }

    boolean contains(int k) {
        return root != null && root.find(k) != null;
    }

    void traverse() {
        if (root != null) root.traverse();
    }
}

public class Demo {
    public static void main(String[] args) {
        BTreeInt tree = new BTreeInt(2); // t=2 (2-3-4 tree)
        int[] inserts = {
            1,3,7,10,11,13,14,15,18,16,19,24,25,26,21,4,5,20,22,2,17,12,6
        };
        for (int v : inserts) tree.insert(v);

        System.out.println("Traversal of constructed tree:");
        tree.traverse();
        System.out.println();

        int[] deletes = {6,13,7,4,2,16};
        for (int d : deletes) {
            tree.delete(d);
            System.out.println("Traversal after removing " + d + ":");
            tree.traverse();
            System.out.println();
        }
    }
}

Notes on operations

• Search: at most O(h) node visits by binary-like scan within a node followed by one child descent.
• Insertion: split full children on the descent (top-down) so the final inesrtion goes into a node with fewer than 2t−1 keys.
• Deletion:
  • If the key is in a leaf, remove it directly.
  • If the key is in an internal node, replace it with its predecessor or successor if the corresponding child has ≥ t keys; otherwise merge the two children and continue.
  • Before descending, ensure the child has at least t keys by rotating from siblings or merging.

Height is O(log_t n), and each operation touches O(h) nodes, which is efficient when nodes are sized to fit a block or cache line.