用Java实现B树的建立查找和删除

B树是一种广泛应用于数据库和文件系统中的数据结构，它的主要特点是能够高效地支持插入、查找和删除操作。下面是使用Java实现B树的简单示例代码。

B树节点类：

public class BTreeNode {
    private int t; // B树的度
    private int keyNum; // 节点中关键字数量
    private int[] keys; // 关键字数组
    private boolean isLeaf; // 是否为叶子节点
    private BTreeNode[] children; // 子节点数组

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

    public int getKeyNum() {
        return keyNum;
    }

    public int getKey(int index) {
        return keys[index];
    }

    public void setKey(int index, int key) {
        keys[index] = key;
    }

    public boolean isLeaf() {
        return isLeaf;
    }

    public BTreeNode getChild(int index) {
        return children[index];
    }

    public void setChild(int index, BTreeNode child) {
        children[index] = child;
    }

    public void setLeaf(boolean isLeaf) {
        this.isLeaf = isLeaf;
    }

    public void setKeyNum(int keyNum) {
        this.keyNum = keyNum;
    }
}

B树类：

public class BTree {
    private BTreeNode root; // B树的根节点
    private int t; // B树的度

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

    // 查找操作
    public BTreeNode search(int key) {
        return search(root, key);
    }

    private BTreeNode search(BTreeNode node, int key) {
        if (node == null) {
            return null;
        }

        int i = 0;
        while (i < node.getKeyNum() && key > node.getKey(i)) {
            i++;
        }

        if (i < node.getKeyNum() && key == node.getKey(i)) {
            return node;
        }

        if (node.isLeaf()) {
            return null;
        } else {
            return search(node.getChild(i), key);
        }
    }

    // 插入操作
    public void insert(int key) {
        if (root == null) {
            root = new BTreeNode(t, true);
            root.setKey(0, key);
            root.setKeyNum(1);
        } else {
            if (root.getKeyNum() == 2 * t - 1) {
                BTreeNode newRoot = new BTreeNode(t, false);
                newRoot.setChild(0, root);
                root = newRoot;
                splitChild(root, 0);
            }
            insertNonFull(root, key);
        }
    }

    private void insertNonFull(BTreeNode node, int key) {
        int i = node.getKeyNum() - 1;
        if (node.isLeaf()) {
            while (i >= 0 && key < node.getKey(i)) {
                node.setKey(i + 1, node.getKey(i));
                i--;
            }
            node.setKey(i + 1, key);
            node.setKeyNum(node.getKeyNum() + 1);
        } else {
            while (i >= 0 && key < node.getKey(i)) {
                i--;
            }
            i++;
            if (node.getChild(i).getKeyNum() == 2 * t - 1) {
                splitChild(node, i);
                if (key > node.getKey(i)) {
                    i++;
                }
            }
            insertNonFull(node.getChild(i), key);
        }
    }

    private void splitChild(BTreeNode node, int i) {
        BTreeNode y = node.getChild(i);
        BTreeNode z = new BTreeNode(t, y.isLeaf());
        z.setKeyNum(t - 1);

        for (int j = 0; j < t - 1; j++) {
            z.setKey(j, y.getKey(j + t));
        }

        if (!y.isLeaf()) {
            for (int j = 0; j < t; j++) {
                z.setChild(j, y.getChild(j + t));
            }
        }

        y.setKeyNum(t - 1);

        for (int j = node.getKeyNum(); j >= i + 1; j--) {
            node.setChild(j + 1, node.getChild(j));
        }

        node.setChild(i + 1, z);

        for (int j = node.getKeyNum() - 1; j >= i; j--) {
            node.setKey(j + 1, node.getKey(j));
        }

        node.setKey(i, y.getKey(t - 1));
        node.setKeyNum(node.getKeyNum() + 1);
    }

    // 删除操作
    public void delete(int key) {
        if (root == null) {
            return;
        }

        delete(root, key);

        if (root.getKeyNum() == 0) {
            root = root.getChild(0);
        }
    }

    private void delete(BTreeNode node, int key) {
        int i = 0;
        while (i < node.getKeyNum() && key > node.getKey(i)) {
            i++;
        }

        if (i < node.getKeyNum() && key == node.getKey(i)) {
            if (node.isLeaf()) {
                for (int j = i + 1; j < node.getKeyNum(); j++) {
                    node.setKey(j - 1, node.getKey(j));
                }
                node.setKeyNum(node.getKeyNum() - 1);
            } else {
                BTreeNode leftChild = node.getChild(i);
                BTreeNode rightChild = node.getChild(i + 1);
                if (leftChild.getKeyNum() >= t) {
                    int pred = getPredecessor(node, i);
                    node.setKey(i, pred);
                    delete(leftChild, pred);
                } else if (rightChild.getKeyNum() >= t) {
                    int succ = getSuccessor(node, i);
                    node.setKey(i, succ);
                    delete(rightChild, succ);
                } else {
                    merge(node, i);
                    delete(leftChild, key);
                }
            }
        } else {
            if (node.isLeaf()) {
                return;
            }

            boolean flag = (i == node.getKeyNum());

            BTreeNode child = node.getChild(i);

            if (child.getKeyNum() < t) {
                fill(node, i);
            }

            if (flag && i > node.getKeyNum()) {
                delete(node.getChild(i - 1), key);
            } else {
                delete(node.getChild(i), key);
            }
        }
    }

    private int getPredecessor(BTreeNode node, int index) {
        BTreeNode cur = node.getChild(index);
        while (!cur.isLeaf()) {
            cur = cur.getChild(cur.getKeyNum());
        }
        return cur.getKey(cur.getKeyNum() - 1);
    }

    private int getSuccessor(BTreeNode node, int index) {
        BTreeNode cur = node.getChild(index + 1);
        while (!cur.isLeaf()) {
            cur = cur.getChild(0);
        }
        return cur.getKey(0);
    }

    private void fill(BTreeNode node, int index) {
        if (index != 0 && node.getChild(index - 1).getKeyNum() >= t) {
            borrowFromPrev(node, index);
        } else if (index != node.getKeyNum() && node.getChild(index + 1).getKeyNum() >= t) {
            borrowFromNext(node, index);
        } else {
            if (index != node.getKeyNum()) {
                merge(node, index);
            } else {
                merge(node, index - 1);
            }
        }
    }

    private void borrowFromPrev(BTreeNode node, int index) {
        BTreeNode child = node.getChild(index);
        BTreeNode sibling = node.getChild(index - 1);

        for (int i = child.getKeyNum() - 1; i >= 0; i--) {
            child.setKey(i + 1, child.getKey(i));
        }

        if (!child.isLeaf()) {
            for (int i = child.getKeyNum(); i >= 0; i--) {
                child.setChild(i + 1, child.getChild(i));
            }
        }

        child.setKey(0, node.getKey(index - 1));

        if (!sibling.isLeaf()) {
            child.setChild(0, sibling.getChild(sibling.getKeyNum()));
        }

        node.setKey(index - 1, sibling.getKey(sibling.getKeyNum() - 1));

        child.setKeyNum(child.getKeyNum() + 1);
        sibling.setKeyNum(sibling.getKeyNum() - 1);
    }

    private void borrowFromNext(BTreeNode node, int index) {
        BTreeNode child = node.getChild(index);
        BTreeNode sibling = node.getChild(index + 1);

        child.setKey(child.getKeyNum(), node.getKey(index));

        if (!child.isLeaf()) {
            child.setChild(child.getKeyNum() + 1, sibling.getChild(0));
        }

        node.setKey(index, sibling.getKey(0));

        for (int i = 1; i < sibling.getKeyNum(); i++) {
            sibling.setKey(i - 1, sibling.getKey(i));
        }

        if (!sibling.isLeaf()) {
            for (int i = 1; i <= sibling.getKeyNum(); i++) {
                sibling.setChild(i - 1, sibling.getChild(i));
            }
        }

        child.setKeyNum(child.getKeyNum() + 1);
        sibling.setKeyNum(sibling.getKeyNum() - 1);
    }

    private void merge(BTreeNode node, int index) {
        BTreeNode child = node.getChild(index);
        BTreeNode sibling = node.getChild(index + 1);

        child.setKey(t - 1, node.getKey(index));

        for (int i = 0; i < sibling.getKeyNum(); i++) {
            child.setKey(i + t, sibling.getKey(i));
        }

        if (!child.isLeaf()) {
            for (int i = 0; i <= sibling.getKeyNum(); i++) {
                child.setChild(i + t, sibling.getChild(i));
            }
        }

        for (int i = index + 1; i < node.getKeyNum(); i++) {
            node.setKey(i - 1, node.getKey(i));
        }

        for (int i = index + 2; i <= node.getKeyNum(); i++) {
            node.setChild(i - 1, node.getChild(i));
        }

        child.setKeyNum(2 * t - 1);
        node.setKeyNum(node.getKeyNum() - 1);
    }
}

这是一个简单的B树实现，仅供参考。在实际应用中，可能需要根据具体情况进行优化和改进。