B树节点分裂逻辑是：当节点键数达2t−1时，取下标t−1的中间键上移至父节点，原节点拆为两个含t−1键的子节点，子指针与键数量须同步维护为n键对应n+1指针。

什么是B树节点的分裂逻辑

B树插入失败通常不是因为代码写错，而是没处理好节点满时的分裂。一个 BTreeNode 满了（比如阶数为 t 时，键数量达到 2*t - 1），再插入就必须分裂：中间键上移，左右两半各成新节点，父节点新增指向它们的指针和键。

关键点在于：分裂必须自底向上触发，但上移操作要由父节点完成；若根节点分裂，则树高+1——这是唯一让B树长高的方式。

• 分裂前先确保父节点有空位，否则递归分裂父节点
• 中间键（下标为 t-1）不属于左右子节点，它被提取出来插入父节点
• 子节点分裂后，原节点不保留该中间键，也不清空，而是拆成两个含 t-1 个键的节点

insert() 函数如何避免重复键覆盖

B树作为索引结构，通常要求键唯一（尤其在数据库场景）。如果直接覆盖已有键值，会丢失数据语义。标准做法是：遇到重复键时，拒绝插入并返回 false，由上层决定是否更新 value 或报错。

实现上要在查找插入位置时就比对键值：

if (node->keys[i] == key) {
    return false; // 已存在，不插入
}

注意：不能只在叶子节点判断，因为内部节点也可能存有该键（作为分界符），但只有叶子节点才真正关联 value，所以只需在最终定位到的叶子节点中检查。

• 比较必须用 == 而非 判断相等，避免自定义比较器漏判
• 若支持重复键（如B+树的非唯一索引），则需改用 vector 存 value 或链表挂载多个记录

如何正确维护 child pointer 和 key 的数量同步

B树节点里 keys 和 children 数量关系极易出错：n 个键对应 n+1 个子指针。插入新键后，若它不是最右位置，就得把右侧所有子指针左移一位，再把新子节点插到对应位置。

典型错误是只动 keys 数组，忘了调整 children 指针数组，导致后续遍历跳过子树或访问野指针。

• 插入键到位置 i 后，需将 children[i+1..n] 整体右移一位

• 删除键时同理：删掉 keys[i] 后，要把 children[i+1..n] 左移，并丢弃最右 child
• 初始化节点时，numKeys = 0，children[0] 应始终指向有效子树（非 null），除非是叶子

C++ 中使用模板实现时要注意什么

用 template 写通用 BTree，最常踩的坑是 K 类型缺乏默认构造或拷贝成本高。B树内部频繁复制键（尤其分裂时），若 K 是大对象或不可拷贝类型（如 std::unique_ptr），会导致编译失败或性能骤降。

推荐约束：

static_assert(std::is_trivially_copyable_v, "Key type must be trivially copyable");
static_assert(std::is_default_constructible_v, "Key must be default constructible");

另外，t 必须是编译期常量，且至少为 2（否则退化为二叉树）；实际项目中 t=3 或 t=4 较常见，兼顾扇出与内存局部性。

• 不要在节点内用 std::vector，改用固定大小数组 K keys[2*t - 1]，避免动态分配破坏缓存友好性
• value 类型 V 可以是引用包装器（如 std::reference_wrapper），但需确保生命周期长于树本身

B树插入看着像二叉搜索树扩展，实则每个节点的“平衡责任”都落在分裂逻辑上。最容易被忽略的是：分裂不是独立操作，它依赖父节点状态；而父节点状态又可能因上层分裂改变——这意味着你得把“分裂传播”当成核心控制流来设计，而不是补丁式处理。