使用Java写一个B树

B树是一种自平衡的数据结构，常用于数据库和文件系统中。以下是一个基于Java语言实现的B树的示例代码：

public class BTree {

    private int order; // B树的阶数
    private Node root;

    public BTree(int order) {
        this.order = order;
        root = new Node(order, true);
    }

    // 节点类
    private class Node {

        private int count; // 节点中元素的数量
        private int[] keys; // 节点中的元素
        private Node[] children; // 子节点
        private boolean isLeaf; // 是否为叶子节点

        public Node(int order, boolean isLeaf) {
            this.count = 0;
            this.keys = new int[2 * order - 1];
            this.children = new Node[2 * order];
            this.isLeaf = isLeaf;
        }

        // 查找元素在节点中的索引
        public int find(int key) {
            for (int i = 0; i < count; i++) {
                if (keys[i] == key) {
                    return i;
                }
            }
            return -1;
        }

        // 插入元素到节点
        public void insert(int key) {
            int i = count - 1;
            while (i >= 0 && keys[i] > key) {
                keys[i + 1] = keys[i];
                i--;
            }
            keys[i + 1] = key;
            count++;
        }

        // 删除节点中的元素
        public void remove(int key) {
            int i = find(key);
            if (i >= 0) {
                for (int j = i; j < count - 1; j++) {
                    keys[j] = keys[j + 1];
                }
                count--;
            }
        }
    }

    // 插入元素到B树
    public void insert(int key) {
        Node node = root;
        if (node.count == 2 * order - 1) {
            Node newRoot = new Node(order, false);
            newRoot.children[0] = root;
            splitChild(newRoot, 0, root);
            insertNonFull(newRoot, key);
            root = newRoot;
        } else {
            insertNonFull(node, key);
        }
    }

    // 插入元素到非满节点
    private void insertNonFull(Node node, int key) {
        int i = node.count - 1;
        if (node.isLeaf) {
            while (i >= 0 && node.keys[i] > key) {
                node.keys[i + 1] = node.keys[i];
                i--;
            }
            node.keys[i + 1] = key;
            node.count++;
        } else {
            while (i >= 0 && node.keys[i] > key) {
                i--;
            }
            i++;
            if (node.children[i].count == 2 * order - 1) {
                splitChild(node, i, node.children[i]);
                if (node.keys[i] < key) {
                    i++;
                }
            }
            insertNonFull(node.children[i], key);
        }
    }

    // 分裂子节点
    private void splitChild(Node parent, int index, Node child) {
        Node newNode = new Node(order, child.isLeaf);
        newNode.count = order - 1;

        for (int i = 0; i < order - 1; i++) {
            newNode.keys[i] = child.keys[i + order];
        }
        if (!child.isLeaf) {
            for (int i = 0; i < order; i++) {
                newNode.children[i] = child.children[i + order];
            }
        }
        child.count = order - 1;
        for (int i = parent.count; i > index; i--) {
            parent.children[i + 1] = parent.children[i];
        }
        parent.children[index + 1] = newNode;
        for (int i = parent.count - 1; i >= index; i--) {
            parent.keys[i + 1] = parent.keys[i];
        }
        parent.keys[index] = child.keys[order - 1];
        parent.count++;
    }

    // 删除元素从B树中
    public void remove(int key) {
        remove(root, key);
        if (root.count == 0) {
            root = root.children[0];
        }
    }

    // 删除元素从节点中
    private void remove(Node node, int key) {
        int i = node.find(key);
        if (i >= 0) {
            if (node.isLeaf) {
                node.remove(key);
            } else {
                Node leftChild = node.children[i];
                Node rightChild = node.children[i + 1];
                if (leftChild.count >= order) {
                    int predecessor = getPredecessor(leftChild);
                    node.keys[i] = predecessor;
                    remove(leftChild, predecessor);
                } else if (rightChild.count >= order) {
                    int successor = getSuccessor(rightChild);
                    node.keys[i] = successor;
                    remove(rightChild, successor);
                } else {
                    merge(node, i, leftChild, rightChild);
                    remove(leftChild, key);
                }
            }
        } else {
            if (node.isLeaf) {
                return;
            }
            boolean flag = (i == -1) ? true : false;
            Node child = node.children[flag ? 0 : i + 1];
            if (child.count < order) {
                fill(node, i, child, flag);
            }
            remove(child, key);
        }
    }

    // 获取节点的前继元素
    private int getPredecessor(Node node) {
        while (!node.isLeaf) {
            node = node.children[node.count];
        }
        return node.keys[node.count - 1];
    }

    // 获取节点的后继元素
    private int getSuccessor(Node node) {
        while (!node.isLeaf) {
            node = node.children[0];
        }
        return node.keys[0];
    }

    // 合并节点
    private void merge(Node parent, int index, Node leftChild, Node rightChild) {
        leftChild.keys[leftChild.count] = parent.keys[index];
        for (int i = 0; i < rightChild.count; i++) {
            leftChild.keys[leftChild.count + 1 + i] = rightChild.keys[i];
        }
        if (!leftChild.isLeaf) {
            for (int i = 0; i <= rightChild.count; i++) {
                leftChild.children[leftChild.count + 1 + i] = rightChild.children[i];
            }
        }
        leftChild.count += rightChild.count + 1;
        for (int i = index; i < parent.count - 1; i++) {
            parent.keys[i] = parent.keys[i + 1];
            parent.children[i + 1] = parent.children[i + 2];
        }
        parent.children[parent.count] = null;
        parent.count--;
    }

    // 填充节点
    private void fill(Node parent, int index, Node child, boolean flag) {
        if (index != 0 && parent.children[index - 1].count >= order) {
            borrowFromLeft(parent, index, child, flag);
        } else if (index != parent.count && parent.children[index + 1].count >= order) {
            borrowFromRight(parent, index, child, flag);
        } else {
            if (index == parent.count) {
                index--;
            }
            merge(parent, index, child, parent.children[index + 1]);
        }
    }

    // 从左侧节点借元素
    private void borrowFromLeft(Node parent, int index, Node child, boolean flag) {
        Node leftChild = parent.children[index - 1];
        for (int i = child.count; i > 0; i--) {
            child.keys[i] = child.keys[i - 1];
        }
        if (!child.isLeaf) {
            for (int i = child.count + 1; i > 0; i--) {
                child.children[i] = child.children[i - 1];
            }
            child.children[0] = leftChild.children[leftChild.count];
        }
        child.keys[0] = parent.keys[index - 1];
        parent.keys[index - 1] = leftChild.keys[leftChild.count - 1];
        child.count++;
        leftChild.count--;
    }

    // 从右侧节点借元素
    private void borrowFromRight(Node parent, int index, Node child, boolean flag) {
        Node rightChild = parent.children[index + 1];
        child.keys[child.count] = parent.keys[index];
        if (!child.isLeaf) {
            child.children[child.count + 1] = rightChild.children[0];
        }
        parent.keys[index] = rightChild.keys[0];
        for (int i = 0; i < rightChild.count - 1; i++) {
            rightChild.keys[i] = rightChild.keys[i + 1];
        }
        if (!rightChild.isLeaf) {
            for (int i = 0; i < rightChild.count; i++) {
                rightChild.children[i] = rightChild.children[i + 1];
            }
            rightChild.children[rightChild.count] = null;
        }
        rightChild.count--;
        child.count++;
    }

    // 查找元素是否存在于B树中
    public boolean contains(int key) {
        return search(root, key) != null;
    }

    // 在B树中查找元素
    private Node search(Node node, int key) {
        int i = 0;
        while (i < node.count && key > node.keys[i]) {
            i++;
        }
        if (i < node.count && key == node.keys[i]) {
            return node;
        }
        if (node.isLeaf) {
            return null;
        } else {
            return search(node.children[i], key);
        }
    }

    // 打印B树
    public void print() {
        print(root, "");
    }

    // 打印节点
    private void print(Node node, String indent) {
        if (node == null) {
            return;
        }
        System.out.print(indent);
        for (int i = 0; i < node.count; i++) {
            System.out.print(node.keys[i] + " ");
        }
        System.out.println();
        if (!node.isLeaf) {
            for (int i = 0; i <= node.count; i++) {
                print(node.children[i], indent + "    ");
            }
        }
    }
}

这个B树实现支持插入、删除和查询操作，并提供了打印B树的功能。在实际使用时，可以根据需求进行修改和扩展。