每日算法 — 使用java实现B+树：多路平衡搜索与范围查询优化

B+树（B-Plus Tree）是数据库管理系统和文件系统中最核心的索引结构之一。与二叉搜索树不同，B+树通过每个节点存储多个键值来大幅降低树高，使得磁盘I/O次数与数据量呈对数关系。其所有数据记录都存储在叶子节点，并通过双向链表串联，从而支持高效的范围查询与顺序遍历。本文用Java从零实现一个完整的B+树，详解节点分裂合并、叶子链表串联、范围查询优化等关键机制。

一、B+树的核心设计思想

1.1 为什么需要B+树

传统二叉搜索树在最坏情况下会退化为链表，时间复杂度退化为O(n)。平衡二叉树（如AVL树、红黑树）虽然保证O(log n)的搜索复杂度，但每个节点仅存储一个键值，导致树高相对较高。在磁盘存储场景下，每次节点访问都可能触发一次磁盘I/O，树高直接决定了查询效率上限。

B+树的核心优势在于：

• 多路分支：每个内部节点可包含数百个子节点，树高通常不超过3~4层
• 数据集中在叶子：所有数据记录存储在叶子节点，内部节点仅作为索引导航
• 叶子链表串联：叶子节点通过指针形成有序链表，支持高效的范围扫描
• 自平衡机制：插入删除时通过分裂与合并保持平衡，无需全局重构

1.2 关键参数与不变式

设B+树的阶数为 M（即每个节点最多容纳 M 个子指针），则必须满足以下不变式：

• 根节点：至少有2个子节点（除非根是叶子）
• 内部节点：至少包含 ⌈M/2⌉ 个子节点，最多 M 个
• 叶子节点：至少包含 ⌈M/2⌉ 个键值，最多 M 个
• 键值有序性：每个节点内的键值按升序排列
• 叶子链表：所有叶子节点通过 next 指针串联成有序链表

二、节点结构定义

B+树中存在两种节点：内部节点（Internal Node）负责索引导航，叶子节点（Leaf Node）负责实际数据存储。为了统一处理，我们先定义抽象基类，再派生出两种具体节点。

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * B+树抽象节点
 * @param <K> 键类型，必须实现Comparable接口
 * @param <V> 值类型
 */
abstract class BPlusNode<K extends Comparable<K>, V> {
    /**
     * 节点中当前存储的键列表，始终保持升序
     */
    protected final List<K> keys;

    /**
     * 父节点引用，根节点的父为null
     */
    protected BPlusNode<K, V> parent;

    BPlusNode() {
        this.keys = new ArrayList<>();
        this.parent = null;
    }

    /**
     * 判断当前节点是否为叶子节点
     */
    abstract boolean isLeaf();

    /**
     * 判断当前节点是否已满
     * @param maxKeys 最大允许的键数量
     */
    boolean isFull(int maxKeys) {
        return keys.size() >= maxKeys;
    }

    /**
     * 判断当前节点键数量是否低于最小阈值
     * @param minKeys 最小允许的键数量
     */
    boolean isUnderflow(int minKeys) {
        return keys.size() < minKeys;
    }

    /**
     * 在节点内查找给定键的位置
     * 返回第一个大于等于key的键的索引，用于确定子树分支
     */
    int findKeyIndex(K key) {
        int idx = Collections.binarySearch(keys, key);
        return idx >= 0 ? idx : -idx - 1;
    }

    /**
     * 获取节点中键的数量
     */
    int keyCount() {
        return keys.size();
    }
}

2.1 内部节点

内部节点存储键值和子节点指针的交替序列。对于 n 个键，内部节点有 n+1 个子指针。键 keys[i] 是子树 children[i+1] 中的最小键，也是分隔 children[i] 和 children[i+1] 的分界值。

/**
 * B+树内部节点
 * 仅存储索引键和子节点引用，不存储实际数据值
 */
class InternalNode<K extends Comparable<K>, V> extends BPlusNode<K, V> {
    /**
     * 子节点列表，长度为 keys.size() + 1
     * children[i] 中所有键均小于 keys[i]（当 i < keys.size() 时）
     * children[i] 中所有键均大于等于 keys[i-1]（当 i > 0 时）
     */
    private final List<BPlusNode<K, V>> children;

    InternalNode() {
        super();
        this.children = new ArrayList<>();
    }

    @Override
    boolean isLeaf() {
        return false;
    }

    /**
     * 根据键值定位应进入哪个子树
     * 返回目标子节点的索引
     */
    int getChildIndex(K key) {
        int idx = findKeyIndex(key);
        // 如果key等于keys[idx]，进入右侧子树
        if (idx < keys.size() && keys.get(idx).compareTo(key) == 0) {
            return idx + 1;
        }
        return idx;
    }

    BPlusNode<K, V> getChild(int index) {
        return children.get(index);
    }

    void addChild(int index, BPlusNode<K, V> child) {
        children.add(index, child);
        child.parent = this;
    }

    void removeChild(int index) {
        children.remove(index);
    }

    int childCount() {
        return children.size();
    }

    K getKey(int index) {
        return keys.get(index);
    }

    void setKey(int index, K key) {
        keys.set(index, key);
    }

    void addKey(int index, K key) {
        keys.add(index, key);
    }

    void removeKey(int index) {
        keys.remove(index);
    }

    /**
     * 将键和子节点插入到指定位置
     */
    void insertEntry(int keyIndex, K key, int childIndex, BPlusNode<K, V> child) {
        keys.add(keyIndex, key);
        children.add(childIndex, child);
        child.parent = this;
    }
}

2.2 叶子节点

叶子节点存储实际的键值对，并通过 next 指针串联成有序链表。叶子节点之间不存在层级跳跃，范围查询只需定位起始叶子，然后沿链表顺序遍历即可。

/**
 * B+树叶子节点
 * 存储实际的键值对，并通过next指针串联成有序链表
 */
class LeafNode<K extends Comparable<K>, V> extends BPlusNode<K, V> {
    /**
     * 与键对应的值列表，keys[i] 对应 values[i]
     */
    private final List<V> values;

    /**
     * 指向下一个叶子节点的指针，构成有序链表
     */
    private LeafNode<K, V> next;

    LeafNode() {
        super();
        this.values = new ArrayList<>();
        this.next = null;
    }

    @Override
    boolean isLeaf() {
        return true;
    }

    V getValue(int index) {
        return values.get(index);
    }

    void addEntry(int index, K key, V value) {
        keys.add(index, key);
        values.add(index, value);
    }

    void removeEntry(int index) {
        keys.remove(index);
        values.remove(index);
    }

    void setValue(int index, V value) {
        values.set(index, value);
    }

    LeafNode<K, V> getNext() {
        return next;
    }

    void setNext(LeafNode<K, V> next) {
        this.next = next;
    }

    /**
     * 查找键在叶子中的精确位置
     * 返回键的索引，若不存在则返回 -1
     */
    int findExactKey(K key) {
        int idx = Collections.binarySearch(keys, key);
        return idx >= 0 ? idx : -1;
    }
}

三、B+树核心操作实现

3.1 树的整体结构

/**
 * B+树实现
 * 支持插入、删除、精确查询、范围查询
 */
public class BPlusTree<K extends Comparable<K>, V> {
    /**
     * B+树的阶数：每个节点最多容纳M个子指针，内部节点最多M-1个键
     */
    private final int M;

    /**
     * 内部节点的最小键数（根节点除外）
     */
    private final int minInternalKeys;

    /**
     * 叶子节点的最小键数
     */
    private final int minLeafKeys;

    /**
     * 根节点
     */
    private BPlusNode<K, V> root;

    /**
     * 指向最左叶子节点的指针，用于范围扫描的起点优化
     */
    private LeafNode<K, V> leftmostLeaf;

    public BPlusTree(int order) {
        if (order < 3) {
            throw new IllegalArgumentException("B+树阶数至少为3");
        }
        this.M = order;
        this.minInternalKeys = (M + 1) / 2 - 1;  // 向上取整(M/2) - 1
        this.minLeafKeys = (M + 1) / 2;          // 向上取整(M/2)
        this.root = new LeafNode<>();
        this.leftmostLeaf = (LeafNode<K, V>) root;
    }

    /**
     * 精确查询：根据键查找对应的值
     * 时间复杂度：O(log_M N)
     */
    public V search(K key) {
        LeafNode<K, V> leaf = findLeafNode(key);
        int idx = leaf.findExactKey(key);
        return idx >= 0 ? leaf.getValue(idx) : null;
    }

    /**
     * 从根节点出发，沿着内部节点的索引导航到达目标叶子
     */
    private LeafNode<K, V> findLeafNode(K key) {
        BPlusNode<K, V> node = root;
        while (!node.isLeaf()) {
            InternalNode<K, V> internal = (InternalNode<K, V>) node;
            int childIdx = internal.getChildIndex(key);
            node = internal.getChild(childIdx);
        }
        return (LeafNode<K, V>) node;
    }
}

3.2 插入操作与节点分裂

插入操作首先定位到目标叶子节点，将键值对按序插入。若插入后叶子节点溢出（键数超过 M-1），则进行叶子分裂：将节点一分为二，将右半部分键值对移入新节点，并把新节点的首键提升到父节点作为分隔键。若父节点因此溢出，则递归向上分裂。

/**
 * 插入键值对
 * 若键已存在则覆盖旧值
 * 时间复杂度：O(log_M N)
 */
public void insert(K key, V value) {
    LeafNode<K, V> leaf = findLeafNode(key);
    int idx = leaf.findExactKey(key);
    if (idx >= 0) {
        // 键已存在，覆盖值
        leaf.setValue(idx, value);
        return;
    }

    // 找到应插入的位置
    idx = leaf.findKeyIndex(key);
    leaf.addEntry(idx, key, value);

    // 若叶子溢出，执行分裂
    if (leaf.keyCount() > M - 1) {
        splitLeaf(leaf);
    }
}

/**
 * 分裂叶子节点
 * 将满叶子节点拆分为左右两个叶子，右半部分移入新节点
 * 新节点的首键提升到父节点作为索引键
 */
private void splitLeaf(LeafNode<K, V> leaf) {
    int mid = leaf.keyCount() / 2;
    LeafNode<K, V> newLeaf = new LeafNode<>();

    // 将后半部分键值对移到新节点
    for (int i = mid; i < leaf.keyCount(); ) {
        newLeaf.addEntry(newLeaf.keyCount(), leaf.keys.get(mid), leaf.getValue(mid));
        leaf.removeEntry(mid);
    }

    // 维护叶子链表
    newLeaf.setNext(leaf.getNext());
    leaf.setNext(newLeaf);

    // 将新节点的首键提升到父节点
    K upKey = newLeaf.keys.get(0);
    if (leaf.parent == null) {
        // 当前叶子是根，需要创建新的根
        InternalNode<K, V> newRoot = new InternalNode<>();
        newRoot.addKey(0, upKey);
        newRoot.addChild(0, leaf);
        newRoot.addChild(1, newLeaf);
        root = newRoot;
    } else {
        InternalNode<K, V> parent = (InternalNode<K, V>) leaf.parent;
        int insertPos = parent.findKeyIndex(upKey);
        parent.insertEntry(insertPos, upKey, insertPos + 1, newLeaf);

        // 若父节点溢出，递归分裂
        if (parent.keyCount() > M - 1) {
            splitInternal(parent);
        }
    }
}

/**
 * 分裂内部节点
 * 将满内部节点拆分为左右两个节点，中间键提升到父节点
 */
private void splitInternal(InternalNode<K, V> node) {
    int mid = node.keyCount() / 2;
    K upKey = node.getKey(mid);
    InternalNode<K, V> newNode = new InternalNode<>();

    // 移动右半部分的键（不含中间键）
    for (int i = mid + 1; i < node.keyCount(); ) {
        newNode.addKey(newNode.keyCount(), node.getKey(mid + 1));
        node.removeKey(mid + 1);
    }
    node.removeKey(mid);

    // 移动对应的子节点
    int childStart = mid + 1;
    for (int i = childStart; i <= node.childCount(); ) {
        newNode.addChild(newNode.childCount(), node.getChild(childStart));
        node.removeChild(childStart);
    }

    if (node.parent == null) {
        InternalNode<K, V> newRoot = new InternalNode<>();
        newRoot.addKey(0, upKey);
        newRoot.addChild(0, node);
        newRoot.addChild(1, newNode);
        root = newRoot;
    } else {
        InternalNode<K, V> parent = (InternalNode<K, V>) node.parent;
        int insertPos = parent.findKeyIndex(upKey);
        parent.insertEntry(insertPos, upKey, insertPos + 1, newNode);

        if (parent.keyCount() > M - 1) {
            splitInternal(parent);
        }
    }
}

3.3 删除操作与节点合并/借用

删除操作首先定位到目标叶子节点并删除键值对。若删除后叶子节点的键数低于最小阈值，则优先尝试从相邻兄弟节点借用键值；若兄弟节点也处于临界状态，则与兄弟节点合并。合并可能导致父节点的键数低于阈值，因此需要递归向上处理。

/**
 * 删除指定键
 * 返回是否删除成功
 * 时间复杂度：O(log_M N)
 */
public boolean delete(K key) {
    LeafNode<K, V> leaf = findLeafNode(key);
    int idx = leaf.findExactKey(key);
    if (idx < 0) {
        return false; // 键不存在
    }

    leaf.removeEntry(idx);

    // 若叶子是根节点，直接返回（根允许少于minLeafKeys）
    if (leaf == root) {
        if (leaf.keyCount() == 0) {
            leftmostLeaf = null;
        }
        return true;
    }

    // 若低于最小键数阈值，执行再平衡
    if (leaf.keyCount() < minLeafKeys) {
        rebalanceLeaf(leaf);
    }
    return true;
}

/**
 * 叶子节点再平衡
 * 优先尝试从左/右兄弟借用键值，若无法借用则合并
 */
private void rebalanceLeaf(LeafNode<K, V> leaf) {
    InternalNode<K, V> parent = (InternalNode<K, V>) leaf.parent;
    int leafIndex = -1;
    for (int i = 0; i < parent.childCount(); i++) {
        if (parent.getChild(i) == leaf) {
            leafIndex = i;
            break;
        }
    }

    // 尝试从左兄弟借用
    if (leafIndex > 0) {
        LeafNode<K, V> leftSibling = (LeafNode<K, V>) parent.getChild(leafIndex - 1);
        if (leftSibling.keyCount() > minLeafKeys) {
            borrowFromLeftLeaf(leaf, leftSibling, parent, leafIndex - 1);
            return;
        }
    }

    // 尝试从右兄弟借用
    if (leafIndex < parent.childCount() - 1) {
        LeafNode<K, V> rightSibling = (LeafNode<K, V>) parent.getChild(leafIndex + 1);
        if (rightSibling.keyCount() > minLeafKeys) {
            borrowFromRightLeaf(leaf, rightSibling, parent, leafIndex);
            return;
        }
    }

    // 无法借用，执行合并
    if (leafIndex > 0) {
        LeafNode<K, V> leftSibling = (LeafNode<K, V>) parent.getChild(leafIndex - 1);
        mergeLeaves(leftSibling, leaf, parent, leafIndex - 1);
    } else {
        LeafNode<K, V> rightSibling = (LeafNode<K, V>) parent.getChild(leafIndex + 1);
        mergeLeaves(leaf, rightSibling, parent, leafIndex);
    }
}

/**
 * 从左侧兄弟叶子借用最后一个键值对
 */
private void borrowFromLeftLeaf(LeafNode<K, V> leaf, LeafNode<K, V> leftSibling,
                                 InternalNode<K, V> parent, int leftKeyIndex) {
    int borrowIdx = leftSibling.keyCount() - 1;
    K borrowKey = leftSibling.keys.get(borrowIdx);
    V borrowValue = leftSibling.getValue(borrowIdx);
    leftSibling.removeEntry(borrowIdx);

    leaf.addEntry(0, borrowKey, borrowValue);

    // 更新父节点中的分隔键
    parent.setKey(leftKeyIndex, leaf.keys.get(0));
}

/**
 * 从右侧兄弟叶子借用第一个键值对
 */
private void borrowFromRightLeaf(LeafNode<K, V> leaf, LeafNode<K, V> rightSibling,
                                  InternalNode<K, V> parent, int keyIndex) {
    K borrowKey = rightSibling.keys.get(0);
    V borrowValue = rightSibling.getValue(0);
    rightSibling.removeEntry(0);

    leaf.addEntry(leaf.keyCount(), borrowKey, borrowValue);

    // 更新父节点中的分隔键
    parent.setKey(keyIndex, rightSibling.keys.get(0));
}

/**
 * 合并两个相邻的叶子节点
 * 将右节点的所有键值对移入左节点，然后从父节点删除对应的分隔键和右节点引用
 */
private void mergeLeaves(LeafNode<K, V> left, LeafNode<K, V> right,
                          InternalNode<K, V> parent, int keyIndex) {
    // 将右节点的键值对全部移入左节点
    for (int i = 0; i < right.keyCount(); i++) {
        left.addEntry(left.keyCount(), right.keys.get(i), right.getValue(i));
    }
    left.setNext(right.getNext());

    // 从父节点删除分隔键和右节点引用
    parent.removeKey(keyIndex);
    parent.removeChild(keyIndex + 1);

    // 若父节点是根且为空，则左节点提升为根
    if (parent == root && parent.keyCount() == 0 && parent.childCount() == 1) {
        root = left;
        left.parent = null;
        return;
    }

    // 递归检查父节点是否需要再平衡
    if (parent != root && parent.keyCount() < minInternalKeys) {
        rebalanceInternal(parent);
    }
}

3.4 内部节点再平衡

内部节点的再平衡逻辑与叶子节点类似：优先借用，无法借用则合并。合并时需要同时处理键和子节点的迁移。

/**
 * 内部节点再平衡
 */
private void rebalanceInternal(InternalNode<K, V> node) {
    InternalNode<K, V> parent = (InternalNode<K, V>) node.parent;
    if (parent == null) return;

    int nodeIndex = -1;
    for (int i = 0; i < parent.childCount(); i++) {
        if (parent.getChild(i) == node) {
            nodeIndex = i;
            break;
        }
    }

    // 尝试从左兄弟借用
    if (nodeIndex > 0) {
        InternalNode<K, V> leftSibling = (InternalNode<K, V>) parent.getChild(nodeIndex - 1);
        if (leftSibling.keyCount() > minInternalKeys) {
            borrowFromLeftInternal(node, leftSibling, parent, nodeIndex - 1);
            return;
        }
    }

    // 尝试从右兄弟借用
    if (nodeIndex < parent.childCount() - 1) {
        InternalNode<K, V> rightSibling = (InternalNode<K, V>) parent.getChild(nodeIndex + 1);
        if (rightSibling.keyCount() > minInternalKeys) {
            borrowFromRightInternal(node, rightSibling, parent, nodeIndex);
            return;
        }
    }

    // 执行合并
    if (nodeIndex > 0) {
        InternalNode<K, V> leftSibling = (InternalNode<K, V>) parent.getChild(nodeIndex - 1);
        mergeInternals(leftSibling, node, parent, nodeIndex - 1);
    } else {
        InternalNode<K, V> rightSibling = (InternalNode<K, V>) parent.getChild(nodeIndex + 1);
        mergeInternals(node, rightSibling, parent, nodeIndex);
    }
}

/**
 * 从左侧兄弟内部节点借用
 * 父节点的分隔键下移到当前节点，左兄弟的最后一个键上移到父节点
 */
private void borrowFromLeftInternal(InternalNode<K, V> node, InternalNode<K, V> leftSibling,
                                     InternalNode<K, V> parent, int leftKeyIndex) {
    K parentKey = parent.getKey(leftKeyIndex);
    K borrowKey = leftSibling.getKey(leftSibling.keyCount() - 1);
    BPlusNode<K, V> borrowChild = leftSibling.getChild(leftSibling.childCount() - 1);

    leftSibling.removeKey(leftSibling.keyCount() - 1);
    leftSibling.removeChild(leftSibling.childCount() - 1);

    node.addKey(0, parentKey);
    node.addChild(0, borrowChild);
    parent.setKey(leftKeyIndex, borrowKey);
}

/**
 * 从右侧兄弟内部节点借用
 * 父节点的分隔键下移到当前节点，右兄弟的第一个键上移到父节点
 */
private void borrowFromRightInternal(InternalNode<K, V> node, InternalNode<K, V> rightSibling,
                                      InternalNode<K, V> parent, int keyIndex) {
    K parentKey = parent.getKey(keyIndex);
    K borrowKey = rightSibling.getKey(0);
    BPlusNode<K, V> borrowChild = rightSibling.getChild(0);

    rightSibling.removeKey(0);
    rightSibling.removeChild(0);

    node.addKey(node.keyCount(), parentKey);
    node.addChild(node.childCount(), borrowChild);
    parent.setKey(keyIndex, borrowKey);
}

/**
 * 合并两个相邻的内部节点
 * 父节点的分隔键下移作为合并后节点的中间键
 */
private void mergeInternals(InternalNode<K, V> left, InternalNode<K, V> right,
                             InternalNode<K, V> parent, int keyIndex) {
    // 父节点的分隔键下移
    left.addKey(left.keyCount(), parent.getKey(keyIndex));

    // 将右节点的键和子节点全部移入左节点
    for (int i = 0; i < right.keyCount(); i++) {
        left.addKey(left.keyCount(), right.getKey(i));
    }
    for (int i = 0; i < right.childCount(); i++) {
        left.addChild(left.childCount(), right.getChild(i));
    }

    parent.removeKey(keyIndex);
    parent.removeChild(keyIndex + 1);

    if (parent == root && parent.keyCount() == 0 && parent.childCount() == 1) {
        root = left;
        left.parent = null;
        return;
    }

    if (parent != root && parent.keyCount() < minInternalKeys) {
        rebalanceInternal(parent);
    }
}

四、范围查询与顺序遍历

B+树最具特色的优势是高效的范围查询。由于叶子节点通过链表串联，范围查询只需定位起始键所在的叶子，然后沿链表顺序遍历直到超出范围上限。

/**
 * 范围查询：返回键在 [start, end] 区间内的所有键值对
 * 时间复杂度：O(log_M N + K)，K 为结果数量
 */
public List<V> rangeQuery(K start, K end) {
    List<V> result = new ArrayList<>();
    if (start.compareTo(end) > 0) {
        return result;
    }

    LeafNode<K, V> leaf = findLeafNode(start);

    while (leaf != null) {
        for (int i = 0; i < leaf.keyCount(); i++) {
            K key = leaf.keys.get(i);
            if (key.compareTo(start) < 0) {
                continue;
            }
            if (key.compareTo(end) > 0) {
                return result;
            }
            result.add(leaf.getValue(i));
        }
        leaf = leaf.getNext();
    }
    return result;
}

/**
 * 获取所有键值对的有序遍历结果
 */
public List<java.util.AbstractMap.SimpleEntry<K, V>> traverse() {
    List<java.util.AbstractMap.SimpleEntry<K, V>> result = new ArrayList<>();
    LeafNode<K, V> leaf = leftmostLeaf;

    // 若树为空，leftmostLeaf可能已失效，需从根重新定位
    if (leaf == null || leaf != root && leaf.parent == null) {
        BPlusNode<K, V> node = root;
        while (!node.isLeaf()) {
            node = ((InternalNode<K, V>) node).getChild(0);
        }
        leaf = (LeafNode<K, V>) node;
    }

    while (leaf != null) {
        for (int i = 0; i < leaf.keyCount(); i++) {
            result.add(new java.util.AbstractMap.SimpleEntry<>(leaf.keys.get(i), leaf.getValue(i)));
        }
        leaf = leaf.getNext();
    }
    return result;
}

五、完整测试与演示

/**
 * B+树测试主程序
 */
public class BPlusTreeDemo {
    public static void main(String[] args) {
        // 创建阶数为4的B+树（每个节点最多3个键）
        BPlusTree<Integer, String> tree = new BPlusTree<>(4);

        System.out.println("=== 插入测试 ===");
        int[] keys = {50, 30, 80, 10, 40, 60, 90, 20, 70, 100, 15, 35, 55, 85};
        for (int k : keys) {
            tree.insert(k, "Value-" + k);
            System.out.println("插入 " + k);
        }

        System.out.println("\n=== 中序遍历结果 ===");
        for (var entry : tree.traverse()) {
            System.out.print(entry.getKey() + "=" + entry.getValue() + " ");
        }
        System.out.println();

        System.out.println("\n=== 精确查询 ===");
        System.out.println("search(40) = " + tree.search(40));
        System.out.println("search(99) = " + tree.search(99));

        System.out.println("\n=== 范围查询 [30, 70] ===");
        for (String v : tree.rangeQuery(30, 70)) {
            System.out.print(v + " ");
        }
        System.out.println();

        System.out.println("\n=== 删除测试 ===");
        System.out.println("删除 30: " + tree.delete(30));
        System.out.println("删除 50: " + tree.delete(50));
        System.out.println("删除 80: " + tree.delete(80));

        System.out.println("\n=== 删除后的中序遍历 ===");
        for (var entry : tree.traverse()) {
            System.out.print(entry.getKey() + "=" + entry.getValue() + " ");
        }
        System.out.println();

        System.out.println("\n=== 范围查询 [20, 70]（删除后）===");
        for (String v : tree.rangeQuery(20, 70)) {
            System.out.print(v + " ");
        }
        System.out.println();

        // 大规模性能测试
        System.out.println("\n=== 大规模性能测试（100,000条数据）===");
        BPlusTree<Integer, Integer> largeTree = new BPlusTree<>(128);
        java.util.Random rand = new java.util.Random(42);
        long t1 = System.currentTimeMillis();
        for (int i = 0; i < 100_000; i++) {
            largeTree.insert(i, i);
        }
        long t2 = System.currentTimeMillis();
        System.out.println("插入100,000条耗时: " + (t2 - t1) + "ms");

        long t3 = System.currentTimeMillis();
        for (int i = 0; i < 100_000; i++) {
            Integer v = largeTree.search(i);
            if (v == null || v != i) {
                throw new RuntimeException("数据不一致: " + i);
            }
        }
        long t4 = System.currentTimeMillis();
        System.out.println("查询100,000条耗时: " + (t4 - t3) + "ms");

        long t5 = System.currentTimeMillis();
        List<Integer> rangeResult = largeTree.rangeQuery(25000, 75000);
        long t6 = System.currentTimeMillis();
        System.out.println("范围查询[25000, 75000]结果数: " + rangeResult.size() + ", 耗时: " + (t6 - t5) + "ms");
    }
}

六、复杂度分析

其中 M 为B+树的阶数，N 为数据总量。当 M=128 且 N=100万 时，树高约为 log_128(10^6) ≈ 3，即最多只需3次磁盘I/O即可完成任意数据的定位。这也是MySQL InnoDB引擎采用B+树作为索引结构的根本原因。

七、总结

本文从B+树的核心设计思想出发，用Java完整实现了一个支持插入、删除、精确查询、范围查询的B+树。关键实现要点包括：

• 节点抽象：通过抽象基类统一内部节点与叶子节点的公共行为，利用泛型支持任意可比较键类型
• 分裂机制：叶子分裂后提升首键到父节点，内部分裂后提升中间键到父节点，保持键值的有序分隔性质
• 再平衡策略：删除后优先向兄弟节点借用键值，无法借用时执行合并，合并可能递归向上传播
• 范围查询优化：叶子节点通过next指针串联成有序链表，范围扫描无需回溯父节点

B+树的价值不仅在于其出色的时间复杂度，更在于它对磁盘I/O的友好设计。理解B+树的实现原理，是深入掌握数据库索引优化、文件系统设计的必要基础。读者可在此基础上继续扩展：支持并发操作的B+树锁机制、磁盘页映射的缓存管理、或结合LSM树实现写优化的混合索引结构。