用Java编写的B + Tree磁盘实现

import java.io.*;

public class BPlusTreeDiskImplementation {
    private static final int ORDER = 3; // B+树的阶数
    private static final int BLOCK_SIZE = 4096; // 磁盘块的大小

    private static class Node implements Serializable {
        private int[] keys;
        private long[] pointers;
        private int numKeys;
        private boolean isLeaf;

        public Node() {
            keys = new int[ORDER - 1];
            pointers = new long[ORDER];
            numKeys = 0;
            isLeaf = false;
        }
    }

    private RandomAccessFile file;
    private long rootOffset;

    public BPlusTreeDiskImplementation(String filename) throws IOException {
        file = new RandomAccessFile(filename, "rw");
        rootOffset = file.length(); // 根节点的偏移量为文件的末尾
        Node root = new Node();
        root.isLeaf = true;
        writeNode(root, rootOffset);
    }

    public void insert(int key, long value) throws IOException {
        Node root = readNode(rootOffset);
        if (root.numKeys == ORDER - 1) {
            Node newRoot = new Node();
            newRoot.pointers[0] = rootOffset;
            splitChild(newRoot, 0, root);
            root = newRoot;
            rootOffset = file.length();
            writeNode(root, rootOffset);
        }
        insertNonFull(root, key, value);
    }

    private void insertNonFull(Node node, int key, long value) throws IOException {
        int i = node.numKeys - 1;
        if (node.isLeaf) {
            while (i >= 0 && key < node.keys[i]) {
                node.keys[i + 1] = node.keys[i];
                node.pointers[i + 1] = node.pointers[i];
                i--;
            }
            node.keys[i + 1] = key;
            node.pointers[i + 1] = value;
            node.numKeys++;
            writeNode(node, getNodeOffset(node));
        } else {
            while (i >= 0 && key < node.keys[i]) {
                i--;
            }
            i++;
            Node child = readNode(node.pointers[i]);
            if (child.numKeys == ORDER - 1) {
                splitChild(node, i, child);
                if (key > node.keys[i]) {
                    i++;
                }
            }
            insertNonFull(readNode(node.pointers[i]), key, value);
        }
    }

    private void splitChild(Node parent, int index, Node child) throws IOException {
        Node newChild = new Node();
        newChild.isLeaf = child.isLeaf;
        newChild.numKeys = ORDER / 2;
        for (int i = 0; i < ORDER / 2; i++) {
            newChild.keys[i] = child.keys[i + ORDER / 2];
            newChild.pointers[i] = child.pointers[i + ORDER / 2];
        }
        if (!child.isLeaf) {
            newChild.pointers[ORDER / 2] = child.pointers[ORDER - 1];
        }
        child.numKeys = ORDER / 2;
        for (int i = parent.numKeys; i > index; i--) {
            parent.keys[i] = parent.keys[i - 1];
            parent.pointers[i + 1] = parent.pointers[i];
        }
        parent.numKeys++;
        parent.keys[index] = newChild.keys[0];
        parent.pointers[index + 1] = getNodeOffset(newChild);
        writeNode(child, getNodeOffset(child));
        writeNode(newChild, getNodeOffset(newChild));
        writeNode(parent, getNodeOffset(parent));
    }

    public long search(int key) throws IOException {
        Node node = readNode(rootOffset);
        while (true) {
            int i = 0;
            while (i < node.numKeys && key > node.keys[i]) {
                i++;
            }
            if (i < node.numKeys && key == node.keys[i]) {
                return node.pointers[i];
            } else if (node.isLeaf) {
                return -1; // 未找到
            } else {
                node = readNode(node.pointers[i]);
            }
        }
    }

    private void writeNode(Node node, long offset) throws IOException {
        file.seek(offset);
        ByteArrayOutputStream baos = new ByteArrayOutputStream();
        ObjectOutputStream oos = new ObjectOutputStream(baos);
        oos.writeObject(node);
        byte[] data = baos.toByteArray();
        file.write(data);
        int padding = BLOCK_SIZE - data.length;
        if (padding > 0) {
            file.write(new byte[padding]);
        }
    }

    private Node readNode(long offset) throws IOException {
        file.seek(offset);
        byte[] data = new byte[BLOCK_SIZE];
        file.readFully(data);
        ByteArrayInputStream bais = new ByteArrayInputStream(data);
        ObjectInputStream ois = new ObjectInputStream(bais);
        try {
            return (Node) ois.readObject();
        } catch (ClassNotFoundException e) {
            e.printStackTrace();
        }
        return null;
    }

    private long getNodeOffset(Node node) {
        return (long) (BLOCK_SIZE * Math.ceil((double) nodeOffset