Java 实现 B+ 树：节点分裂合并与范围查询优化

二、节点分裂策略

1. 叶子节点分裂

public class BPlusTree<K extends Comparable<K>, V> {
    private BPlusTreeNode<K, V> root;
    private int degree;
    private LeafNode<K, V> head; // 叶子节点链表头

    /**
     * 叶子节点分裂
     */
    private void splitLeafNode(LeafNode<K, V> leafNode) {
        // 1. 创建新叶子节点
        LeafNode<K, V> newLeaf = new LeafNode<>(degree);
        // 2. 计算分裂点（通常是中间位置）
        int splitIndex = leafNode.size() / 2;
        // 3. 移动后半部分数据到新节点
        for (int i = splitIndex; i < leafNode.size(); i++) {
            newLeaf.keys.add(leafNode.keys.get(i));
            newLeaf.values.add(leafNode.values.get(i));
        }
        // 移除原节点中已移动的数据
        for (int i = leafNode.size() - 1; i >= splitIndex; i--) {
            leafNode.keys.remove(i);
            leafNode.values.remove(i);
        }
        // 4. 更新叶子节点链表
        newLeaf.next = leafNode.next;
        if (leafNode.next != null) {
            leafNode.next.prev = newLeaf;
        }
        leafNode.next = newLeaf;
        newLeaf.prev = leafNode;
        // 5. 获取新节点的第一个 key（用于向上传递）
        K newKey = newLeaf.keys.get(0);
        // 6. 插入新 key 到父节点
        insertIntoParent(leafNode, newKey, newLeaf);
    }

    /**
     * 插入到父节点
     */
    private void insertIntoParent(BPlusTreeNode<K, V> leftChild, K key, BPlusTreeNode<K, V> rightChild) {
        if (leftChild.parent == null) {
            // 需要创建新的根节点
            createNewRoot(leftChild, key, rightChild);
            return;
        }
        InternalNode<K, V> parent = (InternalNode<K, V>) leftChild.parent;
        // 1. 找到插入位置
        int insertIndex = findInsertIndex(parent.keys, key);
        // 2. 插入 key 和右孩子
        parent.keys.add(insertIndex, key);
        parent.children.add(insertIndex + 1, rightChild);
        rightChild.parent = parent;
        // 3. 如果父节点满了，继续分裂
        if (parent.isFull()) {
            splitInternalNode(parent);
        }
    }

    /**
     * 创建新根节点
     */
    private void createNewRoot(BPlusTreeNode<K, V> leftChild, K key, BPlusTreeNode<K, V> rightChild) {
        InternalNode<K, V> newRoot = new InternalNode<>(degree);
        newRoot.keys.add(key);
        newRoot.children.add(leftChild);
        newRoot.children.add(rightChild);
        leftChild.parent = newRoot;
        rightChild.parent = newRoot;
        this.root = newRoot;
    }
}

2. 内部节点分裂

public class BPlusTree<K extends Comparable<K>, V> {
    /**
     * 内部节点分裂
     */
    private void splitInternalNode(InternalNode<K, V> node) {
        // 1. 创建新的内部节点
        InternalNode<K, V> newNode = new InternalNode<>(degree);
        // 2. 计算分裂点（中间 key 的索引）
        int splitIndex = node.size() / 2;
        K promoteKey = node.keys.get(splitIndex); // 中间 key 要提升到父节点
        // 3. 移动后半部分 key 和 children 到新节点
        for (int i = splitIndex + 1; i < node.size(); i++) {
            newNode.keys.add(node.keys.get(i));
        }
        for (int i = splitIndex + 1; i < node.children.size(); i++) {
            BPlusTreeNode<K, V> child = node.children.get(i);
            newNode.children.add(child);
            child.parent = newNode;
        }
        // 4. 移除原节点中已移动的数据
        for (int i = node.size() - 1; i >= splitIndex; i--) {
            node.keys.remove(i);
        }
        for (int i = node.children.size() - 1; i >= splitIndex + 1; i--) {
            node.children.remove(i);
        }
        // 5. 提升中间 key 到父节点
        if (node.parent == null) {
            // 需要创建新的根节点
            createNewRoot(node, promoteKey, newNode);
        } else {
            InternalNode<K, V> parent = (InternalNode<K, V>) node.parent;
            int insertIndex = findInsertIndex(parent.keys, promoteKey);
            parent.keys.add(insertIndex, promoteKey);
            parent.children.add(insertIndex + 1, newNode);
            newNode.parent = parent;
            // 递归检查父节点
            if (parent.isFull()) {
                splitInternalNode(parent);
            }
        }
    }

    /**
     * 找到插入位置的辅助方法（二分查找）
     */
    private int findInsertIndex(List<K> keys, K key) {
        int left = 0;
        int right = keys.size() - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int cmp = keys.get(mid).compareTo(key);
            if (cmp < 0) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }
}

三、节点合并策略

1. 叶子节点合并

public class BPlusTree<K extends Comparable<K>, V> {
    /**
     * 叶子节点合并
     * @param node 需要合并的节点（关键字不足）
     */
    private void mergeLeafNodes(LeafNode<K, V> node) {
        // 尝试从左兄弟借一个元素
        if (node.prev != null && node.prev.parent == node.parent) {
            LeafNode<K, V> leftSibling = node.prev;
            if (leftSibling.size() > leftSibling.getMinKeys()) {
                // 可以从左兄弟借
                borrowFromLeftSibling(node, leftSibling);
                return;
            }
        }
        // 尝试从右兄弟借一个元素
        if (node.next != null && node.next.parent == node.parent) {
            LeafNode<K, V> rightSibling = node.next;
            if (rightSibling.size() > rightSibling.getMinKeys()) {
                // 可以从右兄弟借
                borrowFromRightSibling(node, rightSibling);
                return;
            }
        }
        // 无法借用，需要合并
        if (node.prev != null && node.prev.parent == node.parent) {
            // 与左兄弟合并
            mergeWithLeftSibling(node);
        } else if (node.next != null && node.next.parent == node.parent) {
            // 与右兄弟合并
            mergeWithRightSibling(node);
        }
    }

    /**
     * 从左兄弟借用元素
     */
    private void borrowFromLeftSibling(LeafNode<K, V> node, LeafNode<K, V> leftSibling) {
        // 1. 获取左兄弟的最后一个元素
        int lastIndex = leftSibling.size() - 1;
        K borrowedKey = leftSibling.keys.get(lastIndex);
        V borrowedValue = leftSibling.values.get(lastIndex);
        // 2. 从左兄弟移除
        leftSibling.keys.remove(lastIndex);
        leftSibling.values.remove(lastIndex);
        // 3. 插入到当前节点开头
        node.keys.add(0, borrowedKey);
        node.values.add(0, borrowedValue);
        // 4. 更新父节点的分隔 key
        updateParentSeparator(node, borrowedKey);
    }

    /**
     * 从右兄弟借用元素
     */
    private void borrowFromRightSibling(LeafNode<K, V> node, LeafNode<K, V> rightSibling) {
        // 1. 获取右兄弟的第一个元素
        K borrowedKey = rightSibling.keys.get(0);
        V borrowedValue = rightSibling.values.get(0);
        // 2. 从右兄弟移除
        rightSibling.keys.remove(0);
        rightSibling.values.remove(0);
        // 3. 插入到当前节点末尾
        node.keys.add(borrowedKey);
        node.values.add(borrowedValue);
        // 4. 更新父节点的分隔 key
        updateParentSeparator(rightSibling, rightSibling.keys.get(0));
    }

    /**
     * 与左兄弟合并
     */
    private void mergeWithLeftSibling(LeafNode<K, V> node) {
        LeafNode<K, V> leftSibling = node.prev;
        // 1. 将所有元素移动到左兄弟
        for (int i = 0; i < node.size(); i++) {
            leftSibling.keys.add(node.keys.get(i));
            leftSibling.values.add(node.values.get(i));
        }
        // 2. 更新叶子节点链表
        leftSibling.next = node.next;
        if (node.next != null) {
            node.next.prev = leftSibling;
        }
        // 3. 从父节点中删除对应的 key 和指针
        InternalNode<K, V> parent = (InternalNode<K, V>) node.parent;
        int indexInParent = findChildIndex(parent, node);
        // 删除指向当前节点的指针和对应的 key
        parent.keys.remove(indexInParent - 1);
        parent.children.remove(indexInParent);
        // 4. 检查父节点是否下溢
        if (parent.isUnderflow()) {
            if (parent == root && parent.size() == 0) {
                // 根节点为空，降低树的高度
                root = leftSibling;
                leftSibling.parent = null;
            } else {
                mergeInternalNodes(parent);
            }
        }
    }
}

2. 内部节点合并

public class BPlusTree<K extends Comparable<K>, V> {
    /**
     * 内部节点合并
     */
    private void mergeInternalNodes(InternalNode<K, V> node) {
        // 查找兄弟节点
        InternalNode<K, V> parent = (InternalNode<K, V>) node.parent;
        int nodeIndex = findChildIndex(parent, node);
        // 尝试从左兄弟借用
        if (nodeIndex > 0) {
            InternalNode<K, V> leftSibling = (InternalNode<K, V>) parent.children.get(nodeIndex - 1);
            if (leftSibling.size() > leftSibling.getMinKeys()) {
                borrowFromLeftInternalSibling(node, leftSibling, parent, nodeIndex);
                return;
            }
        }
        // 尝试从右兄弟借用
        if (nodeIndex < parent.children.size() - 1) {
            InternalNode<K, V> rightSibling = (InternalNode<K, V>) parent.children.get(nodeIndex + 1);
            if (rightSibling.size() > rightSibling.getMinKeys()) {
                borrowFromRightInternalSibling(node, rightSibling, parent, nodeIndex);
                return;
            }
        }
        // 需要合并
        if (nodeIndex > 0) {
            // 与左兄弟合并
            mergeWithLeftInternalSibling(node, parent, nodeIndex);
        } else {
            // 与右兄弟合并
            mergeWithRightInternalSibling(node, parent, nodeIndex);
        }
    }

    /**
     * 从左兄弟内部节点借用
     */
    private void borrowFromLeftInternalSibling(InternalNode<K, V> node, InternalNode<K, V> leftSibling, InternalNode<K, V> parent, int nodeIndex) {
        // 1. 从父节点借一个 key
        K parentKey = parent.keys.get(nodeIndex - 1);
        // 2. 从左兄弟获取最后一个 child
        BPlusTreeNode<K, V> borrowedChild = leftSibling.children.remove(leftSibling.children.size() - 1);
        K borrowedKey = leftSibling.keys.remove(leftSibling.keys.size() - 1);
        // 3. 父节点的 key 下移到当前节点开头
        node.keys.add(0, parentKey);
        node.children.add(0, borrowedChild);
        borrowedChild.parent = node;
        // 4. 借来的 key 上移到父节点
        parent.keys.set(nodeIndex - 1, borrowedKey);
    }

    /**
     * 合并内部节点
     */
    private void mergeWithLeftInternalSibling(InternalNode<K, V> node, InternalNode<K, V> parent, int nodeIndex) {
        InternalNode<K, V> leftSibling = (InternalNode<K, V>) parent.children.get(nodeIndex - 1);
        // 1. 将父节点的分隔 key 下移
        K parentKey = parent.keys.get(nodeIndex - 1);
        leftSibling.keys.add(parentKey);
        // 2. 将当前节点的所有 key 和 children 移到左兄弟
        for (K key : node.keys) {
            leftSibling.keys.add(key);
        }
        for (BPlusTreeNode<K, V> child : node.children) {
            leftSibling.children.add(child);
            child.parent = leftSibling;
        }
        // 3. 从父节点中删除
        parent.keys.remove(nodeIndex - 1);
        parent.children.remove(nodeIndex);
        // 4. 递归检查父节点
        if (parent.isUnderflow()) {
            if (parent == root && parent.size() == 0) {
                root = leftSibling;
                leftSibling.parent = null;
            } else {
                mergeInternalNodes(parent);
            }
        }
    }
}

四、范围查询优化

1. 叶子节点链表遍历

public class BPlusTree<K extends Comparable<K>, V> {
    /**
     * 范围查询
     * @param startKey 起始 key（包含）
     * @param endKey 结束 key（包含）
     * @return 范围内的所有值
     */
    public List<V> rangeQuery(K startKey, K endKey) {
        List<V> results = new ArrayList<>();
        // 1. 找到起始 key 所在的叶子节点
        LeafNode<K, V> startNode = findLeafNode(startKey);
        if (startNode == null) {
            return results;
        }
        // 2. 在起始节点中找到起始位置
        int startIndex = startNode.findKeyIndex(startKey);
        if (startIndex < 0) {
            startIndex = -startIndex - 1; // 转换为插入位置
        }
        // 3. 遍历叶子节点链表
        LeafNode<K, V> currentNode = startNode;
        int currentIndex = startIndex;
        while (currentNode != null) {
            while (currentIndex < currentNode.size()) {
                K currentKey = currentNode.keys.get(currentIndex);
                // 检查是否超出范围
                if (currentKey.compareTo(endKey) > 0) {
                    return results;
                }
                results.add(currentNode.values.get(currentIndex));
                currentIndex++;
            }
            // 移动到下一个叶子节点
            currentNode = currentNode.next;
            currentIndex = 0;
        }
        return results;
    }

    /**
     * 批量范围查询优化（预取）
     */
    public List<V> rangeQueryWithPrefetch(K startKey, K endKey, int batchSize) {
        List<V> results = new ArrayList<>();
        // 1. 找到起始节点
        LeafNode<K, V> currentNode = findLeafNode(startKey);
        int currentIndex = 0;
        // 预取下一批节点
        List<LeafNode<K, V>> prefetchedNodes = prefetchNodes(currentNode, batchSize);
        while (!prefetchedNodes.isEmpty()) {
            for (LeafNode<K, V> node : prefetchedNodes) {
                // 2. 对每个节点进行二分查找，快速定位范围
                int start = binarySearchInNode(node, startKey);
                int end = binarySearchInNode(node, endKey);
                if (start < 0) start = -start - 1;
                if (end < 0) end = -end - 2; // end 是最后一个<=endKey 的位置
                // 3. 批量添加结果
                for (int i = start; i <= end && i < node.size(); i++) {
                    results.add(node.values.get(i));
                }
                // 如果已经超过 endKey，提前结束
                if (end < node.size() - 1 && node.keys.get(end + 1).compareTo(endKey) > 0) {
                    return results;
                }
            }
            // 4. 预取下一批节点
            currentNode = prefetchedNodes.get(prefetchedNodes.size() - 1).next;
            prefetchedNodes = prefetchNodes(currentNode, batchSize);
        }
        return results;
    }

    /**
     * 预取节点（减少磁盘 IO）
     */
    private List<LeafNode<K, V>> prefetchNodes(LeafNode<K, V> startNode, int count) {
        List<LeafNode<K, V>> nodes = new ArrayList<>();
        LeafNode<K, V> current = startNode;
        for (int i = 0; i < count && current != null; i++) {
            nodes.add(current);
            current = current.next;
        }
        return nodes;
    }
}

2. 并行范围查询

public class ParallelBPlusTree<K extends Comparable<K>, V> extends BPlusTree<K, V> {
    private ExecutorService executor;

    /**
     * 并行范围查询
     */
    public List<V> parallelRangeQuery(K startKey, K endKey, int numThreads) {
        // 1. 估算范围内的大致数据量
        long estimatedSize = estimateRangeSize(startKey, endKey);
        // 2. 根据数据量决定是否并行
        if (estimatedSize < 1000) {
            return super.rangeQuery(startKey, endKey);
        }
        // 3. 分割查询范围
        List<RangeTask> tasks = splitRange(startKey, endKey, numThreads);
        // 4. 提交任务并行执行
        List<Future<List<V>>> futures = new ArrayList<>();
        for (RangeTask task : tasks) {
            futures.add(executor.submit(() -> executeRangeQuery(task.startKey, task.endKey)));
        }
        // 5. 收集结果
        List<V> results = new ArrayList<>();
        for (Future<List<V>> future : futures) {
            try {
                results.addAll(future.get());
            } catch (Exception e) {
                // 处理异常，继续执行其他任务
            }
        }
        return results;
    }

    /**
     * 分割查询范围
     */
    private List<RangeTask> splitRange(K startKey, K endKey, int numSplits) {
        List<RangeTask> tasks = new ArrayList<>();
        // 1. 找到范围内的所有叶子节点
        List<LeafNode<K, V>> leafNodes = getLeafNodesInRange(startKey, endKey);
        // 2. 计算每个任务应该处理的节点数
        int nodesPerTask = Math.max(1, leafNodes.size() / numSplits);
        // 3. 创建任务
        for (int i = 0; i < leafNodes.size(); i += nodesPerTask) {
            int endIndex = Math.min(i + nodesPerTask, leafNodes.size());
            List<LeafNode<K, V>> taskNodes = leafNodes.subList(i, endIndex);
            K taskStartKey = taskNodes.get(0).keys.get(0);
            K taskEndKey = taskNodes.get(taskNodes.size() - 1)
                    .keys.get(taskNodes.get(taskNodes.size() - 1).size() - 1);
            tasks.add(new RangeTask(taskStartKey, taskEndKey, taskNodes));
        }
        return tasks;
    }

    private static class RangeTask {
        K startKey;
        K endKey;
        List<LeafNode<K, V>> nodes;

        RangeTask(K startKey, K endKey, List<LeafNode<K, V>> nodes) {
            this.startKey = startKey;
            this.endKey = endKey;
            this.nodes = nodes;
        }
    }
}

3. 缓存优化策略

public class CachedBPlusTree<K extends Comparable<K>, V> extends BPlusTree<K, V> {
    // LRU 缓存，缓存最近访问的节点
    private LinkedHashMap<K, CacheEntry> cache;
    private final int cacheSize;

    public CachedBPlusTree(int degree, int cacheSize) {
        super(degree);
        this.cacheSize = cacheSize;
        this.cache = new LinkedHashMap<K, CacheEntry>(cacheSize, 0.75f, true) {
            @Override
            protected boolean removeEldestEntry(Map.Entry<K, CacheEntry> eldest) {
                return size() > cacheSize;
            }
        };
    }

    @Override
    public V get(K key) {
        // 1. 检查缓存
        CacheEntry entry = cache.get(key);
        if (entry != null) {
            return entry.value;
        }
        // 2. 从磁盘读取
        V value = super.get(key);
        // 3. 放入缓存
        if (value != null) {
            cache.put(key, new CacheEntry(value, System.currentTimeMillis()));
        }
        return value;
    }

    @Override
    public List<V> rangeQuery(K startKey, K endKey) {
        List<V> results = new ArrayList<>();
        // 1. 预热缓存：预先加载范围内的部分数据
        preloadCache(startKey, endKey);
        // 2. 执行范围查询，优先使用缓存
        LeafNode<K, V> currentNode = findLeafNode(startKey);
        while (currentNode != null) {
            for (int i = 0; i < currentNode.size(); i++) {
                K currentKey = currentNode.keys.get(i);
                if (currentKey.compareTo(endKey) > 0) {
                    return results;
                }
                // 检查缓存
                CacheEntry cached = cache.get(currentKey);
                if (cached != null) {
                    results.add(cached.value);
                } else {
                    V value = currentNode.values.get(i);
                    results.add(value);
                    // 放入缓存
                    cache.put(currentKey, new CacheEntry(value, System.currentTimeMillis()));
                }
            }
            currentNode = currentNode.next;
        }
        return results;
    }

    /**
     * 缓存预热
     */
    private void preloadCache(K startKey, K endKey) {
        // 采样范围内的部分 key 进行预热
        List<K> sampleKeys = sampleKeysInRange(startKey, endKey, 100);
        for (K key : sampleKeys) {
            V value = super.get(key);
            if (value != null) {
                cache.put(key, new CacheEntry(value, System.currentTimeMillis()));
            }
        }
    }

    private static class CacheEntry {
        V value;
        long timestamp;

        CacheEntry(V value, long timestamp) {
            this.value = value;
            this.timestamp = timestamp;
        }
    }
}

五、性能优化策略

1. 批量插入优化

public class OptimizedBPlusTree<K extends Comparable<K>, V> extends BPlusTree<K, V> {
    /**
     * 批量插入优化
     */
    public void bulkInsert(List<Pair<K, V>> data) {
        if (data.isEmpty()) return;
        // 1. 按 key 排序
        data.sort(Comparator.comparing(Pair::getKey));
        // 2. 批量构建叶子节点
        List<LeafNode<K, V>> leafNodes = buildLeafNodesInBatch(data);
        // 3. 批量构建索引
        buildIndexInBatch(leafNodes);
        // 4. 更新根节点
        updateRootFromLeaves(leafNodes);
    }

    /**
     * 批量构建叶子节点
     */
    private List<LeafNode<K, V>> buildLeafNodesInBatch(List<Pair<K, V>> data) {
        List<LeafNode<K, V>> leafNodes = new ArrayList<>();
        LeafNode<K, V> currentLeaf = new LeafNode<>(degree);
        for (Pair<K, V> entry : data) {
            currentLeaf.keys.add(entry.getKey());
            currentLeaf.values.add(entry.getValue());
            if (currentLeaf.isFull()) {
                leafNodes.add(currentLeaf);
                currentLeaf = new LeafNode<>(degree);
            }
        }
        if (!currentLeaf.keys.isEmpty()) {
            leafNodes.add(currentLeaf);
        }
        // 连接叶子节点链表
        for (int i = 0; i < leafNodes.size() - 1; i++) {
            leafNodes.get(i).next = leafNodes.get(i + 1);
            leafNodes.get(i + 1).prev = leafNodes.get(i);
        }
        return leafNodes;
    }

    /**
     * 批量构建索引（自底向上）
     */
    private void buildIndexInBatch(List<LeafNode<K, V>> leafNodes) {
        List<InternalNode<K, V>> currentLevel = new ArrayList<>();
        // 第一层：叶子节点的父节点
        for (int i = 0; i < leafNodes.size(); i += degree) {
            InternalNode<K, V> parent = new InternalNode<>(degree);
            int end = Math.min(i + degree, leafNodes.size());
            for (int j = i; j < end; j++) {
                LeafNode<K, V> leaf = leafNodes.get(j);
                parent.children.add(leaf);
                leaf.parent = parent;
                if (j > i) {
                    parent.keys.add(leaf.keys.get(0));
                }
            }
            currentLevel.add(parent);
        }
        // 递归构建更高层
        while (currentLevel.size() > 1) {
            currentLevel = buildNextLevel(currentLevel);
        }
        // 更新根节点
        if (!currentLevel.isEmpty()) {
            root = currentLevel.get(0);
        }
    }
}

2. 并发控制

public class ConcurrentBPlusTree<K extends Comparable<K>, V> extends BPlusTree<K, V> {
    private final ReadWriteLock globalLock = new ReentrantReadWriteLock();
    private final Map<BPlusTreeNode<K, V>, ReadWriteLock> nodeLocks = new ConcurrentHashMap<>();

    /**
     * 细粒度并发插入
     */
    @Override
    public void insert(K key, V value) {
        // 1. 查找插入位置（读锁）
        globalLock.readLock().lock();
        try {
            LeafNode<K, V> leaf = findLeafNode(key);
            lockNode(leaf, false); // 写锁叶子节点
            // 2. 插入到叶子节点
            if (!leaf.isFull()) {
                insertIntoLeaf(leaf, key, value);
                unlockNode(leaf);
                return;
            }
            // 3. 需要分裂，获取父节点锁
            lockNode(leaf.parent, false);
            // 4. 执行分裂（可能需要递归向上）
            splitAndInsert(leaf, key, value);
            unlockNode(leaf.parent);
            unlockNode(leaf);
        } finally {
            globalLock.readLock().unlock();
        }
    }

    /**
     * 乐观并发范围查询
     */
    public List<V> optimisticRangeQuery(K startKey, K endKey) {
        List<V> results = new ArrayList<>();
        int retries = 3;
        while (retries-- > 0) {
            try {
                // 1. 记录版本号（或修改时间）
                long startVersion = getTreeVersion();
                // 2. 执行范围查询
                results = doRangeQuery(startKey, endKey);
                // 3. 验证版本是否变化
                long endVersion = getTreeVersion();
                if (startVersion == endVersion) {
                    return results; // 没有并发修改，结果有效
                }
                // 4. 版本变化，重试
                results.clear();
            } catch (ConcurrentModificationException e) {
                // 重试
            }
        }
        // 重试失败，使用悲观锁
        return pessimisticRangeQuery(startKey, endKey);
    }

    private void lockNode(BPlusTreeNode<K, V> node, boolean readOnly) {
        ReadWriteLock lock = nodeLocks.computeIfAbsent(node, n -> new ReentrantReadWriteLock());
        if (readOnly) {
            lock.readLock().lock();
        } else {
            lock.writeLock().lock();
        }
    }

    private void unlockNode(BPlusTreeNode<K, V> node) {
        ReadWriteLock lock = nodeLocks.get(node);
        if (lock != null) {
            if (lock.writeLock().isHeldByCurrentThread()) {
                lock.writeLock().unlock();
            } else {
                lock.readLock().unlock();
            }
        }
    }
}

六、应用场景与配置建议

1. 数据库索引配置

-- MySQL InnoDB B+ 树索引配置示例
CREATE TABLE users (
    id INT PRIMARY KEY,
    name VARCHAR(100),
    email VARCHAR(100),
    created_at TIMESTAMP,
    INDEX idx_name (name),
    INDEX idx_email (email)
) ENGINE=InnoDB
-- B+ 树相关参数
ROW_FORMAT=DYNAMIC -- 行格式
KEY_BLOCK_SIZE=16 -- 索引页大小（KB）
-- InnoDB 参数
innodb_page_size=16K -- 页大小
innodb_buffer_pool_size=1G -- 缓冲池大小
innodb_purge_threads=4 -- 清理线程

2. 文件系统实现

// 基于 B+ 树的简单文件系统
public class BPlusTreeFileSystem {
    private BPlusTree<String, FileMetadata> index; // 文件名->文件元数据
    private BlockManager blockManager; // 块管理器

    /**
     * 范围查询文件（按文件名排序）
     */
    public List<FileMetadata> listFiles(String prefix) {
        // 使用 B+ 树的范围查询特性
        return index.rangeQuery(prefix, prefix + Character.MAX_VALUE);
    }

    /**
     * 分页查询优化
     */
    public PageResult<FileMetadata> listFilesPaged(
            String prefix, int page, int pageSize) {
        // 1. 找到起始位置
        LeafNode<String, FileMetadata> startNode = index.findLeafNode(prefix);
        // 2. 使用游标遍历，避免全量读取
        Cursor cursor = new Cursor(startNode, prefix);
        // 3. 读取指定页的数据
        List<FileMetadata> pageData = new ArrayList<>();
        for (int i = 0; i < pageSize && cursor.hasNext(); i++) {
            pageData.add(cursor.next());
        }
        // 4. 记录下一次的起始位置
        String nextStartKey = cursor.hasNext() ? cursor.peek().getKey() : null;
        return new PageResult<>(pageData, page, pageSize, nextStartKey);
    }
}

3. 性能测试与监控

public class BPlusTreeBenchmark {
    public void benchmark() {
        int[] degrees = {16, 32, 64, 128};
        int[] dataSizes = {1000, 10000, 100000, 1000000};
        for (int degree : degrees) {
            for (int size : dataSizes) {
                // 测试插入性能
                testInsertPerformance(degree, size);
                // 测试查询性能
                testQueryPerformance(degree, size);
                // 测试范围查询性能
                testRangeQueryPerformance(degree, size);
                // 测试分裂合并开销
                testSplitMergeOverhead(degree, size);
            }
        }
    }

    private void testRangeQueryPerformance(int degree, int size) {
        BPlusTree<Integer, String> tree = new BPlusTree<>(degree);
        // 插入测试数据
        for (int i = 0; i < size; i++) {
            tree.insert(i, "value" + i);
        }
        // 测试不同范围大小的查询
        int[] rangeSizes = {10, 100, 1000, 10000};
        for (int rangeSize : rangeSizes) {
            long startTime = System.nanoTime();
            for (int i = 0; i < 1000; i++) {
                int start = i % (size - rangeSize);
                int end = start + rangeSize;
                tree.rangeQuery(start, end);
            }
            long duration = System.nanoTime() - startTime;
            System.out.printf("Degree=%d, Size=%d, Range=%d: %.2f ops/ms\n", degree, size, rangeSize, 1000.0 / (duration / 1_000_000.0));
        }
    }
}

七、总结

B+ 树的核心优势：

1. 分裂合并策略：
   • 分裂：当节点满时，将其分成两个节点并提升中间 key
   • 合并：当节点元素过少时，与兄弟节点合并或借用元素
   • 保证树的高度平衡和空间利用率
2. 范围查询优化：
   • 叶子节点链表支持顺序遍历
   • 缓存和预取减少磁盘 IO
   • 并行查询充分利用多核 CPU
   • 游标支持分页查询
3. 性能优化技术：
   • 批量操作减少树的重组
   • 细粒度并发控制
   • 缓存热点数据
   • 自适应分裂阈值

实际应用建议：

1. 选择合适的度（degree）：
   • 内存数据库：较小的度（16-64）
   • 磁盘数据库：较大的度（64-256），匹配页大小
   • SSD：中等度（32-128）
2. 监控与调优：
   • 监控树的高度和节点填充率
   • 定期重组优化空间利用率
   • 根据负载模式调整缓存策略
3. 现代改进：
   • 考虑 B* 树（减少分裂频率）
   • 支持 SSD 的 B+ 树变种
   • 结合 LSM 树处理写入密集型负载

B+ 树作为经典的数据结构，通过精心设计的分裂合并策略和范围查询优化，在数据库索引和文件系统中仍然发挥着重要作用。