如何处理B+树操作中途崩溃后的状态恢复问题？

核心方案分类 #

1. 预写日志（WAL）机制 #

这是工业界最普及的恢复方案，核心逻辑是先写日志，再改数据：

• 所有对树的修改操作（插入、删除、节点分裂/合并等），在实际修改磁盘上的树节点前，必须先把操作的完整元数据写入日志文件。日志写入要保证原子性——要么完整落地到磁盘，要么完全不写，避免日志本身损坏。
• 崩溃恢复时：
  • 扫描日志文件，区分已完成日志写入但未修改树节点的操作，重新执行这些操作；
  • 对已经修改部分树节点的操作，根据日志里记录的旧值回滚到操作前状态，或根据新值补全未完成的修改。
• 日志需要定期清理：当系统完成一次检查点（checkpoint）后，检查点之前的日志即可删除，防止日志文件无限膨胀。

2. 检查点（Checkpoint）辅助恢复 #

单独依赖WAL的话，恢复时可能需要扫描大量日志，耗时很长，检查点机制可以解决这个问题：

• 定期将树的当前完整有效状态写入磁盘的检查点文件，写入过程要保证检查点文件本身的有效性。
• 崩溃恢复时，先加载最近的检查点，再应用检查点之后产生的WAL日志，就能快速恢复到崩溃前的最新有效状态，大幅缩短恢复耗时。

3. 节点级原子更新 #

针对单个节点的修改，确保磁盘写入的原子性，避免单个节点出现半修改状态：

• 双块备份法：给每个节点分配两个磁盘块，修改时先写备用块，确认写入完成后，再更新节点的指针指向备用块；
• 利用磁盘硬件的原子写特性：部分磁盘支持单块数据的原子写入，保证节点的修改要么全部完成，要么完全不变。
• 注意：这种方式仅能处理单节点操作，对于涉及多节点的分裂/合并等复杂操作，必须配合WAL使用。

4. Undo/Redo 组合日志 #

针对事务场景的恢复方案，日志同时记录两种信息：

• Redo日志：用于恢复那些已经提交但还未写入树节点的操作，确保事务的持久性；
• Undo日志：用于撤销那些已经修改了树节点但未提交的事务，确保事务的原子性。
• 恢复时，先通过Redo重做已提交的操作，再通过Undo回滚未提交的操作，最终让树回到一个一致的有效状态。

5. 无日志情况下的结构校验与修复 #

如果系统没有配置日志机制，只能采用全量校验修复的方式（属于兜底方案，可能丢失数据）：

• 从根节点开始遍历整个树，检查每个节点的键值数量是否符合B+树/B树的规则（如最小/最大键数限制）；
• 校验叶子节点的链表连续性，以及非叶子节点指针与子节点的对应关系；
• 对于发现的损坏节点，尝试通过相邻节点（父节点、兄弟节点）的信息修复缺失的键值，或标记损坏节点并跳过（需接受数据丢失风险）。

内容的提问来源于stack exchange，提问作者HelloGoodbye