B-Tree 与崩溃恢复

B-Tree 是一种非常优秀的数据结构，适用于数据库和文件系统等场景。本文将从以下几个角度解析 B-Tree 的特点与实现。

B-Tree 作为平衡的 n 叉树

高度平衡的树

许多实用的二叉树（如 AVL 树或红黑树）被称为**高度平衡树**，即树的高度（从根到叶的深度）被限制为 \(O(\log(N))\)，因此查找操作的复杂度为 \(O(\log(N))\)。

B-Tree 同样是一种高度平衡的树，其所有叶节点的高度相同，这确保了其良好的查找性能。

从二叉树到 n 叉树的推广

B-Tree 可以看作是从二叉树推广而来的 n 叉树。例如，2-3-4 树是一种 B-Tree，其中每个节点可以有 2、3 或 4 个子节点。2-3-4 树可以等价于红黑树（RB 树），但具体的映射细节对理解 B-Tree 并不是必须的。

以下是排序序列 [1, 2, 3, 4, 6, 9, 11, 12] 构建的 2 层 B+ 树示意图：

     [1,   4,   9]
     /     |     \
    v      v      v
[1, 2, 3] [4, 6] [9, 11, 12]

在 B+ 树中： - 只有叶子节点存储实际的值； - 内部节点存储键，用于指示子树的范围。

例如，节点 [1, 4, 9] 将区间划分为 [1, 4), [4, 9) 和 [9, +∞)。为了优化存储，B+ 树的区间划分可进一步简化为 (-∞, 4), [4, 9), (9, +∞)。

B-Tree 作为嵌套数组

两层嵌套数组

即使不深入了解红黑树或 2-3-4 树的细节，也可以通过排序数组的扩展来直观理解 B-Tree。

问题：排序数组在更新时的复杂度为 \(O(N)\)。
改进：如果将数组分为 \(m\) 个不重叠的子数组，则更新复杂度可降为 \(O(N/m)\)。但查找时需要先定位子数组，这需要额外的索引数组。

这种嵌套结构可表示为：

[[1,2,3], [4,6], [9,11,12]]

通过两次二分查找，查找成本仍然是 \(O(\log(N))\)。如果选择 \(m = \sqrt{N}\)，更新复杂度变为 \(O(\sqrt{N})\)，这与 2 层排序数组的效果一致。

多层嵌套数组

对于数据库而言，\(O(\sqrt{N})\) 的复杂度仍然不够高效。通过进一步拆分数组并增加嵌套层数，可以将复杂度进一步降低。

假设： - 每层数组大小不超过常数 \(s\)，那么可以通过 \(\log(N/s)\) 层完成分割； - 查找复杂度为 \(O(\log(N/s) + \log(s))\)。

由于 \(s\) 为常数，这最终简化为 \(O(\log(N))\)。
插入与删除的复杂度主要体现在维护叶节点的不变性，通常操作成本为 \(O(s)\)。

B+ 树的维护

更新 B+ 树时，需要维持以下三个不变量： 1. 所有叶节点的高度相同； 2. 每个节点的大小受常数限制； 3. 节点不能为空。

通过节点分裂扩展 B 树

插入操作可能导致叶节点超出大小限制，从而违反第二个不变量。解决方法是将叶节点拆分为两个较小的节点，并将新的分裂信息传递给父节点。

    parent              parent
   /  |  \     =>      /  | |  \
L1   L2   L6         L1  L3 L4  L6
     *                   *  *

如果父节点的大小也超过限制，则分裂会继续向上传播，甚至可能影响根节点：

                        new_root
                          / \
    root                 N1 N2
   /  |  \     =>      /  | |  \
L1   L2   L6         L1  L3 L4  L6

此过程保持了树的高度平衡，所有叶节点的高度同步增加 1。

通过节点合并收缩 B 树

删除操作可能导致节点为空，从而违反第三个不变量。通过将空节点合并到兄弟节点，可以恢复平衡状态。

合并操作是分裂的逆过程，同样可以向上传播，从而降低树的高度。

B-Tree on disk

B-Tree 在磁盘上的实现需要特别考虑以下几点：

Block-based allocation

对于内存中的 B+ 树，可以通过限制每个节点的键数量来控制节点大小。然而在磁盘上，必须考虑固定块大小（如 4KB）。这使得节点的大小固定，有助于简化空间分配与回收。

Copy-on-write B-tree for safe updates

为了保证崩溃恢复，常见的方法包括： 1. 文件重命名； 2. 日志记录； 3. LSM 树。

B+ 树可以采用**写时复制（Copy-on-Write, COW）**的方式更新节点，确保旧数据在更新过程中不被破坏。

原理： - 插入或删除操作从叶节点开始，将被修改的节点复制为新节点； - 更新其父节点以指向新节点，父节点的更新同样通过复制完成； - 修改可能传播到根节点，从而生成一个新的树根。

    d           d         D*
   / \         / \       / \
  b   e  ==>  b   e  +  B*  e
 / \         / \       / \
a   c       a   c     a   C*
            原始树      更新树

在上图中，更新了叶子 c，并复制了相关节点（大写表示新节点）。

编辑于 2024-12-04 11:38

Copy-on-write B-tree asvantages

保留旧版本的好处之一是我们可以免费获得快照隔离。事务从树的一个版本开始，并且不会看到其他版本的更改。

而且崩溃恢复毫不费力；只需使用最后一个旧版本。

另外一个是它符合多读取器单写入器的并发模型，读取器不会阻塞写入器。我们稍后会探讨这些。

Alternative: In-place update with double-write

虽然崩溃恢复在写时复制数据结构中很明显，但由于高写入放大，它们可能是不受欢迎的。每次更新都会复制整个路径 (O(log N))，而大多数就地更新仅涉及 1 个叶节点。

可以通过崩溃恢复进行就地更新，而无需写入时复制：

将整个更新节点的副本保存在某处。这类似于写时复制，但不复制父节点。
fsync 保存的副本。（此时可以回复客户。）
实际上就地更新数据结构。
fsync 更新。

崩溃后，数据结构可能会更新一半，但我们真的不知道。我们所做的就是盲目应用保存的副本，以便数据结构以更新后的状态结束，而不管当前状态如何。

| a=1 b=2 |
    ||  1. Save a copy of the entire updated nodes.
    \/
| a=1 b=2 |   +   | a=2 b=4 |
   data           updated copy
    ||  2. fsync the saved copies.
    \/
| a=1 b=2 |   +   | a=2 b=4 |
   data           updated copy (fsync'ed)
    ||  3. Update the data structure in-place. But we crashed here!
    \/
| ??????? |   +   | a=2 b=4 |
   data (bad)     updated copy (good)
    ||  Recovery: apply the saved copy.
    \/
| a=2 b=4 |   +   | a=2 b=4 |
   data (new)     useless now

保存的更新副本在 MySQL 术语中称为双写。但是如果双写被破坏怎么办？它的处理方式与日志相同：校验和。

如果校验和检测到错误的双写，请忽略它。这是在第一次 fsync 之前，因此主要数据处于良好且旧的状态。
如果双写良好，应用它总是会产生良好的主数据。

有些数据库实际上将双写存储在日志中，称为物理日志记录。有两种日志记录：逻辑日志记录和物理日志记录。逻辑日志记录描述了诸如插入键之类的高级操作，此类操作只能在数据库处于良好状态时才能应用于数据库，因此只有物理日志记录（低级磁盘页面更新）对恢复有用。

The crash recovery pinciple

我们比较双写和写时复制两种策略，可以发现：

双写使得更新幂等；数据库可以通过应用保存的副本来重试更新，因为它们是完整节点。
写入时复制以原子方式将所有内容切换到新版本。

它们基于不同的想法：

双写可确保有足够的信息来生成新版本。
写入时复制可确保保留旧版本。

如果我们用双写保存原始节点而不是更新后的节点会怎么样？这是从损坏中恢复的第三种方法，它像写时复制一样恢复到旧版本。我们可以将 3 种方式结合成 1 个想法：在任何时候对于旧状态或新状态都有足够的信息。

此外，总是需要进行一些复制，因此较大的树节点更新速度较慢。我们将使用写时复制，因为它更简单。