实战：B+树索引（磁盘模拟+范围查询）

说实话，B+树这东西，我当年在学校学数据库原理时，觉得就是个理论模型。直到工作后第一次接手一个千万级数据的存储引擎优化，才真正体会到它的威力。今天咱们就来手写一个简化版的B+树索引，重点模拟磁盘读写，并实现范围查询。

为什么是B+树？

你想想看，如果让你设计一个索引结构，要支持快速查找、范围查询，还要能高效利用磁盘块，你会选什么？

哈希表？查找快，但没法做范围查询。二叉搜索树？磁盘IO次数太多，树太高了。B+树呢，它把数据都放在叶子节点，内部节点只存键值，这样每个节点可以塞很多键，树就矮了。我做过测试，一个三层的B+树，就能管理上亿条记录。

磁盘模拟的思路

真正的磁盘读写，是按块（block）来的。一次IO读一个块，哪怕你只想要一个字节。所以我们的B+树节点大小，应该等于一个磁盘块的大小。

我习惯用固定大小的节点来模拟。比如每个节点固定存4个键值对，这样节点大小是固定的，方便我们模拟「从磁盘读取一个节点」的操作。

// 模拟磁盘块大小
const int BLOCK_SIZE = 4096;  // 4KB
const int MAX_KEYS = 4;       // 每个节点最多存4个键

// 节点类型
enum NodeType {
    INTERNAL,  // 内部节点
    LEAF       // 叶子节点
};

// B+树节点
struct BPlusNode {
    NodeType type;
    int keys[MAX_KEYS];
    long children[MAX_KEYS + 1];  // 子节点在磁盘中的位置
    long next_leaf;               // 叶子节点的下一个兄弟（用于范围查询）
    int key_count;
    
    // 模拟写入磁盘
    void write_to_disk(long position) {
        // 这里用文件偏移模拟磁盘地址
        // 实际项目中会用文件流写入
    }
    
    // 模拟从磁盘读取
    static BPlusNode read_from_disk(long position) {
        BPlusNode node;
        // 从文件指定位置读取
        return node;
    }
};

范围查询的实现

范围查询是B+树的拿手好戏。比如你要查「年龄在20到30之间」的所有记录，B+树怎么做？

先找到20所在的叶子节点，然后沿着叶子节点的链表往后遍历，直到遇到大于30的键为止。整个过程只需要一次树搜索，剩下的全是顺序读。

我在项目中遇到过一个问题：如果范围很大，比如查「所有年龄大于18的」，那几乎要遍历整个叶子链表。这时候如果叶子节点之间是单向链表，你就只能从头走到尾。所以我建议用双向链表，虽然多占一点空间，但灵活性好很多。

核心操作：插入与分裂

插入操作是B+树最复杂的部分。说白了，就是找到叶子节点，塞进去。如果满了，就分裂。

分裂时，把一半的键分给新节点，然后把中间键提升到父节点。如果父节点也满了，继续往上分裂。最坏情况一直裂到根，树就长高一层。

void insert(BPlusNode* root, int key, long value) {
    // 1. 找到应该插入的叶子节点
    BPlusNode* leaf = find_leaf(root, key);
    
    // 2. 如果叶子节点没满，直接插入
    if (leaf->key_count < MAX_KEYS) {
        insert_into_leaf(leaf, key, value);
        leaf->write_to_disk(leaf->disk_pos);
        return;
    }
    
    // 3. 叶子节点满了，需要分裂
    BPlusNode* new_leaf = split_leaf(leaf);
    // 把key插入到合适的叶子中
    if (key < new_leaf->keys[0]) {
        insert_into_leaf(leaf, key, value);
    } else {
        insert_into_leaf(new_leaf, key, value);
    }
    
    // 4. 把中间键提升到父节点
    int middle_key = new_leaf->keys[0];
    insert_into_parent(root, leaf, middle_key, new_leaf);
}

完整的范围查询代码

// 范围查询：返回所有在 [low, high] 之间的键值对
vector<pair<int, long>> range_query(BPlusNode* root, int low, int high) {
    vector<pair<int, long>> result;
    
    // 1. 找到 low 所在的叶子节点
    BPlusNode* leaf = find_leaf(root, low);
    if (!leaf) return result;
    
    // 2. 在叶子节点内找到第一个 >= low 的位置
    int start = 0;
    while (start < leaf->key_count && leaf->keys[start] < low) {
        start++;
    }
    
    // 3. 遍历叶子节点链表
    BPlusNode* current = leaf;
    while (current) {
        for (int i = start; i < current->key_count; i++) {
            if (current->keys[i] > high) {
                return result;  // 超出范围，结束
            }
            result.push_back({current->keys[i], current->children[i]});
        }
        // 移动到下一个叶子节点
        if (current->next_leaf != -1) {
            current = BPlusNode::read_from_disk(current->next_leaf);
            start = 0;  // 新节点从头开始
        } else {
            break;
        }
    }
    
    return result;
}

知识体系结构图

避坑指南

我曾经在实现B+树时踩过一个坑：叶子节点的next指针指向的是磁盘位置，而不是内存地址。因为节点可能被换出内存，再读回来时地址就变了。所以一定要用「磁盘地址」来链接，而不是指针。

另一个容易忽略的点：删除操作时，如果节点太稀疏，需要合并。但合并比分裂复杂得多，要考虑兄弟节点的情况。我建议初学者先实现插入和查询，删除可以放一放。

好了，B+树索引的核心就这些。代码量不大，但逻辑要理清楚。动手写一遍，比看十遍都管用。

公众号:蓝海资料掘金营，微信deep3321