C++如何手写B+树实现基于磁盘存储的高性能索引-C++-PHP中文网

生产环境不建议手写磁盘版b+树，因其需处理页对齐、缓冲淘汰、崩溃恢复、并发控制、文件碎片、direct i/o、校验等复杂问题，远超算法本身；sqlite等成熟实现已迭代十年以上，corner case极易遗漏。

c++如何手写b+树实现基于磁盘存储的高性能索引

为什么不该手写磁盘版B+树

直接说结论：在生产环境里，不建议手写基于磁盘的B+树索引。这不是能力问题，而是成本与风险问题——你得处理页对齐、缓冲区淘汰（LRU/K））、崩溃一致性（WAL/ARIES）、并发控制（latch vs lock）、文件碎片、mmap边界、direct I/O适配、checksum校验……这些加起来远超算法本身。SQLite、LevelDB、RocksDB 的 B+ 树模块都迭代了十年以上，光是 split 和 merge 在 crash 后的恢复逻辑就容易漏掉 corner case。

如果真要动手，先砍掉哪些“高级功能”

想跑通一个可落地的最小磁盘B+树，必须做减法。否则第一天就会卡在 fsync 时机或 readv 返回 EINTR 上。

只支持单线程写入（暂不实现 latch_sharing 或乐观并发）
所有节点固定大小（比如 4KB），用 pwrite + pread 直接寻址，不抽象“页管理器”
不实现 WAL：靠 fsync(fd) 在 insert 后强制落盘（牺牲 crash safety 换简单性）
键类型限定为 int64_t，值类型限定为 int64_t（避免序列化/反序列化歧义）
根节点始终在文件 offset 0，用 struct header { uint64_t root_page_id; uint64_t size; } 开头存 16 字节元数据

关键结构体怎么对齐才不踩 `read` 错位坑

磁盘 I/O 不认 C++ 对象布局，sizeof(node) 必须等于页大小（如 4096），且所有字段偏移必须自然对齐。编译器 padding 不可控，必须显式控制。

错误写法：struct bplus_node { int is_leaf; uint64_t keys[127]; uint64_t children[128]; }; —— 因为 int 是 4 字节，后面 uint64_t 会强制 8 字节对齐，导致实际大小不是 4096。

正确做法（以 4KB 页为例）：

C++14

C++14 对 C++11 的修正与增强版本，适合旧系统维护和较老工具链兼容。

下载

#pragma pack(8)
struct bplus_node {
    uint8_t is_leaf;
    uint8_t _pad1[7];
    uint64_t keys[127];
    union {
        uint64_t children[128]; // 非叶子
        uint64_t values[127];   // 叶子（最后 key 无 value，留空）
    };
    uint64_t next_leaf; // 叶子链表指针，仅叶子节点有效
    uint64_t _pad2[1];  // 确保总长 = 4096
};
static_assert(sizeof(bplus_node) == 4096, "node size mismatch");

#pragma pack 和 static_assert 是硬性要求，缺一不可。x86_64 下 uint64_t 必须 8 字节对齐，否则 pread 进来的内存直接 reinterpret_cast 会触发 SIGBUS。