B+ 树并发删除梳理

第一阶段：悲观查找与“安全释放”

函数：bptree_find_leaf_delete_safe
这是并发删除的起点。为了防止死锁，必须自上而下加锁

  1. **全局入口锁：**首先通过 tree->root_lock 找到当前的根节点
1
2
3
4
5
6
struct _bptree {
    bptree_node* root;

    // == 入口指针锁 ==
    pthread_mutex_t root_lock;
};
  1. 蟹行加锁 (Crabbing):
  • 锁住parent,再锁住child。
  • **核心决策（早释放）：**如果child节点是丰满的，（即key_count > MIN_KEYS）,意味着即便在该子树发生删除，也不会导致parent节点发生合并或缩减。
  • **执行弹栈：**一旦发现child安全，立即调用bptree_unlock_all_in_path。这会释放从根节点到该child上方所有的锁。
  1. 最终状态：当函数返回时，path栈中仅保留了可能受删除影响的最少节点集合（通常只有叶子及其父节点）。

第二阶段：逻辑删除

函数：bptree_delete_from_leaf
此时，已经拿到了叶子节点的写锁（WRLOCK）。

  1. **原子操作：**在受保护的叶子节点内执行memmove,移除对应的键值对。

  2. **状态返回：**如果 Key 不存在，立即通过BPTREE_NOT_FOUND信号通知，直接进入收尾阶段（解锁退出）

第三阶段: 结构修复（接力向上）

函数：bptree_delete_fixup → fix_leaf/fix_internal
如果删除后节点下溢（Underflow），修复逻辑启动。此时的并发核心是通过path栈向下管控，而不是向上寻找。

  1. 路径回溯：fixup函数通过path->top--拿到父节点。由于在查找阶段锁住了路径，此时父节点一定已被当前线程持有写锁。

  2. 兄弟节点锁定：

  • 当需要借键或合并时，必须锁住兄弟节点。
  • **顺序保证：**因为父节点已被锁住，其他线程无法在此层插入或者删除，我们可以安全地按照索引顺序（比如先锁左再锁右）获取兄弟锁，从而避免死锁。
  1. 动作解耦：
  • **Borrow(旋转)：**涉及三个节点的数据搬运，修改父节点的 Key。
  • **Merge(合并)：**将两个节点合二为一。
  1. **物理销毁的原子性：**合并完成后，先执行delete_from_internal从父节点彻底摘除废弃节点的指针，最后才执行free(node)。确保了其他线程绝不会访问到悬空指针。

第四阶段：根节点收缩（高度缩减）

函数：bptree_delete尾部特判
这是整棵树高度发生变化的唯一时刻，也是并发最敏感的时刻。

  1. 二次检查（Double-Check）: 获取tree->root_lock后，再次确认root->key_count == 0
  2. **根指针平滑切换：**将tree->root指向它唯一的孩子。
  3. **清理 path 标记：**将path栈中对应的旧指针设为NULL,防止后续重复解锁。

并发安全的三道防线

阶段 核心技术 解决的问题
查找 悲观蟹行加锁 防止多个线程同时修改同一路径导致的结构崩溃。
修复 Path 栈托管 废弃 node->parent 访问，消除自下而上加锁导致的死锁。
清理 NULL 标记 + 防御解锁 解决 free 节点与残留锁释放之间的内存安全冲突。

核心逻辑流转总结

Delete 调度器 → 悲观查找（Lock Path） → 叶子删除 → （若下溢）Fixup（向上回溯 Path） → （若根空）缩高 → Unlock All Path

通过path栈，把一个原本需要全表锁定的全局操作，转化为了一个局部受控的局部操作。

删除模型

1
2
3
4
5
6
7
8
9
10
11
12
13
悲观查找（自上而下 WRLock）
        ↓
安全节点判断（child > MIN_KEYS）
        ↓
提前释放祖先锁（Crabbing）
        ↓
叶子删除
        ↓
Path 托管向上修复
        ↓
Root Double Check 缩高
        ↓
统一释放 path