C++ B+树怎么实现节点的分裂、合并与借键平衡-C++-PHP中文网

B+树分裂必须从中间切分并上提中间键，以维持平衡性、有序性和叶节点链表完整性；上提非中间键会导致子树范围错位或链表断裂。

c++ b+树怎么实现节点的分裂、合并与借键平衡

分裂时为什么必须从中间切分，且新节点要上提父键

分裂不是随便砍一刀，而是为了维持 B+ 树的平衡性和有序性。当一个 Node 的键数量超过阶数 m-1（即满节点），必须拆成两个合法子节点，且中间键（keys[m/2]）**必须上提到父节点**作为分界——这是 B+ 树保持“所有叶节点在最底层且链接成链表”的前提。如果上提的是别的键，会导致子树范围错位或叶节点链表断裂。

实操建议：

分裂前确认当前节点是叶节点还是内节点：叶节点分裂后需更新 next 和 prev 指针，保证链表连续；内节点分裂则只处理键和子指针数组
用整数除法取中位索引：mid = (keys.size() + 1) / 2（注意：B+ 树常用向上取中，确保左子树 ≤ 右子树，尤其在偶数键时）
上提的键不能保留在原节点，否则重复；也不能留在新节点，否则父节点无法正确路由查询
若父节点不存在（即根分裂），需新建根节点，高度+1——这是唯一让树长高的操作

合并与借键前必须检查兄弟节点是否“够借”或“可合”

B+ 树的合并（merge）和借键（borrow）不是无条件触发的，核心判断依据是：当前节点键数 （即低于最小度要求）。但直接合并或借键可能引发连锁反应，比如借键后兄弟变空、合并后父节点欠键。

常见错误现象：Segmentation fault 在递归回溯时访问已释放的 next 指针，或查询返回空结果但实际数据存在——往往源于合并后没重连叶链表。

实操建议：

优先尝试借键（从左兄弟或右兄弟），仅当两个兄弟都 keys.size() == min_keys 时才合并（避免频繁升降高）
借键时，内节点要同步移动子指针（例如从右兄弟借键，需把其最左子指针移给当前节点最右）；叶节点只需挪键+调整 next/prev
合并两个叶节点后，必须修复链表：设被合并节点为 A，接收方为 B，则执行 A->next->prev = B 和 B->next = A->next，再 delete A
合并内节点后，父节点要删掉对应键和子指针——别忘了删键后检查父节点是否也欠键，需递归处理

叶节点分裂/合并时 next/prev 指针容易漏修或错连

B+ 树靠叶节点的双向链表支持范围查询（如 SELECT * FROM t WHERE id BETWEEN 10 AND 20），但多数实现只专注键和子树逻辑，把 next 当作“顺手连一下”，结果一合并就断链、一插入就跳过整段数据。

C++14

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

下载

性能影响：链表断裂不会导致崩溃，但会使 range_scan 退化为全树遍历，O(log n) 变 O(n)。

实操建议：

每次叶节点分裂，新节点 new_node->next = old_node->next，new_node->prev = old_node，然后 old_node->next->prev = new_node，最后 old_node->next = new_node
合并时，若 A 合入 B（A 在 B 右侧），则先执行 B->next = A->next，再 A->next->prev = B，顺序反了会丢节点
在析构函数里打印 next 地址做简单链表校验（调试期），上线后可用轻量断言：assert(next == nullptr || next->prev == this)

std::vector 管理键和指针时要注意移动语义与内存布局

用 std::vector 和 std::vector 存键和子指针很常见，但 vector::insert 或 vector::erase 触发扩容或搬移时，原始指针会失效——尤其在借键过程中临时修改多个节点的 children，若 vector 重分配，那些存着的 Node* 就成野指针。

实操建议：