用java实现一个B+树

B+树是一种平衡树，广泛应用于数据库索引、文件系统等领域。下面是一个简单的Java实现：

public class BPlusTree<K extends Comparable<K>, V> {
    private int order;  // B+树的阶数
    private Node<K, V> root;  // 根节点

    public BPlusTree(int order) {
        this.order = order;
        root = new LeafNode<K, V>();
    }

    public void insert(K key, V value) {
        root.insert(key, value);
    }

    public V search(K key) {
        return root.search(key);
    }

    // 节点类
    private abstract class Node<K extends Comparable<K>, V> {
        protected List<K> keys;  // 关键字列表

        // 插入关键字和值
        public abstract void insert(K key, V value);

        // 根据关键字查找值
        public abstract V search(K key);
    }

    // 叶子节点类
    private class LeafNode<K extends Comparable<K>, V> extends Node<K, V> {
        private List<V> values;  // 值列表

        public LeafNode() {
            keys = new ArrayList<K>();
            values = new ArrayList<V>();
        }

        public void insert(K key, V value) {
            int i = Collections.binarySearch(keys, key);
            if (i >= 0) {
                values.set(i, value);
            } else {
                i = -i - 1;
                keys.add(i, key);
                values.add(i, value);
            }
        }

        public V search(K key) {
            int i = Collections.binarySearch(keys, key);
            return i >= 0 ? values.get(i) : null;
        }
    }

    // 内部节点类
    private class InternalNode<K extends Comparable<K>, V> extends Node<K, V> {
        private List<Node<K, V>> children;  // 子节点列表

        public InternalNode() {
            keys = new ArrayList<K>();
            children = new ArrayList<Node<K, V>>();
        }

        public void insert(K key, V value) {
            int i = Collections.binarySearch(keys, key);
            i = i >= 0 ? i + 1 : -i - 1;
            Node<K, V> child = children.get(i);
            child.insert(key, value);
            if (child.keys.size() > order) {
                Node<K, V> sibling = child.split();
                keys.add(i, sibling.keys.get(0));
                children.add(i + 1, sibling);
            }
        }

        public V search(K key) {
            int i = Collections.binarySearch(keys, key);
            i = i >= 0 ? i + 1 : -i - 1;
            return children.get(i).search(key);
        }
    }

    // 分裂节点
    private Node<K, V> split() {
        InternalNode<K, V> sibling = new InternalNode<K, V>();
        sibling.keys.addAll(keys.subList(order / 2, keys.size()));
        sibling.children.addAll(children.subList(order / 2, children.size()));
        keys.subList(order / 2, keys.size()).clear();
        children.subList(order / 2, children.size()).clear();
        return sibling;
    }
}

该实现中，B+树被表示为一个根节点，根据key的类型，分为内部节点和叶子节点。内部节点包含key列表和子节点列表，叶子节点包含key列表和value列表。在插入时，如果叶子节点已经存在该key，则更新其value，否则将key和value插入到正确的位置。如果叶子节点的key数量超过了阶数，则进行分裂操作，将其中一半的key和value放到新的叶子节点中，并将新叶子节点的第一个key添加到父节点的key列表中。在搜索时，根据key的大小关系，递归查找到叶子节点并返回对应的value。