B树的异常恢复-EW帮帮网

B-Tree & Crash Recovery

B树作为平衡的n叉树

高度平衡树

许多实用的二叉树（如AVL树或红黑树）被称为高度平衡树，这意味着树的高度（从根节点到叶子节点）被限制为Ο(log 𝑁)，因此查找操作的时间复杂度也是Ο(log 𝑁)。

B树同样是一种高度平衡的树；所有叶子节点的高度相同。

从二叉树推广到n叉树

n叉树可以从二叉树推广而来（反之亦然）。一个典型的例子是2-3-4树，它是一种特殊的B树，其中每个节点可以有2、3或4个子节点。2-3-4树与红黑树等价，但为了理解B树，我们不需要深入探讨这些细节。

可视化一个2层的B+树

以下是一个排序序列 [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)：第一个子树 [1, 2, 3]。
[4, 9)：第二个子树 [4, 6]。
[9, +∞)：第三个子树 [9, 11, 12]。

然而，实际上只需要两个键即可划分三个区间：

(-∞, 4)：表示小于4的所有键。
[4, 9)：表示大于等于4且小于9的键。
[9, +∞)：表示大于等于9的所有键。

因此，第一个键 1 可以省略，简化后的键范围如下：

(-∞, 4)。
[4, 9)。
[9, +∞)。

这种设计使得B+树的内部节点能够更高效地存储键，并减少冗余信息。

B+树的关键特性总结

叶节点存储实际数据：
- 所有的实际数据都存储在叶节点中，这使得查询路径更加一致和简单。
内部节点仅存储引导键：
- 内部节点的键用于划分子树的范围，帮助快速定位目标数据所在的叶节点。
高度平衡：
- B+树的高度始终保持平衡，确保查找、插入和删除操作的时间复杂度为Ο(log 𝑁)。
高效的范围查询：
- 由于所有叶节点通过指针链接在一起，范围查询变得非常高效。例如，查询 [4, 9) 范围内的所有数据时，只需遍历相关的叶节点。
空间利用率高：
- 每个节点可以存储多个键和子节点，减少了树的高度，从而降低了磁盘访问次数。

为什么选择B+树？

相比于普通的B树，B+树更适合数据库和文件系统等需要频繁进行范围查询和顺序访问的应用场景。以下是B+树的主要优势：

叶节点链式结构：支持高效的范围查询和顺序扫描。
内部节点优化存储：内部节点只存储键而不存储实际数据，使得每个节点可以容纳更多的键，进一步降低树的高度。
写入友好：新数据总是插入到叶节点中，避免了频繁更新内部节点。

3.2 B树作为嵌套数组

理解B树的一种方法是从排序数组的角度出发，尤其是通过构建多级嵌套数组来模拟B树的行为。

两层嵌套数组

对于一个简单的排序数组，更新操作的时间复杂度是Ο(𝑁)。为了优化这一点，可以将数组分割成𝑚个较小的、互不重叠的数组。这样，更新操作的时间复杂度降低为Ο(𝑁 / 𝑚)。然而，为了找到需要更新或查询的具体小数组，我们需要另一个包含对这些小数组引用的排序数组，这实际上对应于B+树中的内部节点。

例如：

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

在这个例子中，外层数组（即内部节点）包含了指向各个子数组（即叶节点）的引用。查找操作仍然可以通过两次二分查找完成，总时间复杂度为Ο(log 𝑁)。如果选择𝑚为 $(\sqrt{N})$ ，那么更新操作的时间复杂度变为 $O(\sqrt{N})$ ，这是两层排序数组能达到的最佳效果。

$O(\sqrt{N})$

多层嵌套数组

尽管 $O(\sqrt{N})$ 的更新成本对于数据库来说可能还是不够理想，但如果继续增加层级，通过进一步分割数组，可以进一步减少成本。具体做法如下：

不断地分割数组直到所有的数组大小都不超过一个常数𝑠。
最终得到log (𝑁 / 𝑠)层，查找的成本为Ο(log (𝑁 / 𝑠) + log (𝑠))，简化后仍然是Ο(log 𝑁)。

对于插入和删除操作，找到对应的叶节点后，更新叶节点的时间复杂度通常是常数Ο(𝑠)。剩下的挑战在于维护节点大小不超过𝑠且非空的不变性条件。

维护节点的不变性

为了确保每个节点的大小保持在𝑠以内并且不为空，需要采取一些策略来处理插入和删除操作带来的影响：

分裂与合并：当某个节点超过最大容量𝑠时，需要将其分裂成两个较小的节点，并将中间元素提升到父节点。相反，当删除操作导致某个节点过小时，可能需要从兄弟节点借取元素或者与兄弟节点合并。
平衡树结构：通过上述分裂和合并操作，确保整个树的高度保持平衡，从而保证查找、插入和删除操作的时间复杂度均为Ο(log 𝑁)。

这种多级嵌套数组的设计思想实际上揭示了B树的核心机制：通过合理组织数据结构，使得即使在大规模数据集上也能高效地进行各种操作。它不仅提高了更新效率，还保证了查找性能的一致性。这种方法为理解和实现B树提供了一个直观的视角。

维护B+树

在更新B+树时，需要维护以下三个不变性（invariants）：

所有叶子节点具有相同的高度。
节点大小由一个常数限制。
节点不为空。

通过分割节点扩展B树

当向叶节点插入数据时，可能会违反第二个不变性（节点大小超出限制）。此时，可以通过将节点分割成更小的部分来恢复这一不变性。

例如，假设我们在叶节点L2中插入了一个新元素，导致其大小超过了限制：

Before:
 parent
 / | \
L1 L2 L6

After inserting an element into L2:
 parent
 / | \
L1 L2 L6
    *
Splitting L2:
parent
/ | | \
L1 L3 L4 L6
   *   *

分割叶节点后，其父节点会获得一个新的分支。如果这个父节点也超出了大小限制，则可能也需要进行分割。这种节点分割的过程可以一直传播到根节点，从而增加树的高度。

Before growing the tree height:
  root
 / | \
L1 L2 L6

After growing the tree height by splitting nodes:
  new_root
    / \
   N1 N2
  / | | \
L1 L3 L4 L6

由于所有的叶子节点同时增加了高度，因此第一个不变性得到了保持。

通过合并节点收缩B树

删除操作可能导致某些节点变为空节点，这就违反了第三个不变性（节点不能为空）。为了恢复这一不变性，可以通过将空节点与其兄弟节点合并来实现。合并是分割的逆过程，它同样可以从某个节点开始，并可能传播至根节点，导致树的高度减少。

例如，假设我们从L2中删除了一个元素，使得L2变为空节点：

Before merging:
 parent
  / | \
L1 L2* L6

Merging L2 with a sibling (e.g., L1):
 parent
 / | \
L1' L6

在这个例子中，L2与L1进行了合并，形成了新的L1’节点。合并可以在非空节点达到下限时提前执行，以减少空间浪费。这有助于维持树结构的紧凑性并提高性能。

总结

扩展B树：通过分割节点来处理节点过大问题。分割操作可能会沿着树向上直至根节点，导致树的高度增加。
收缩B树：通过合并节点来解决节点过小或为空的问题。合并操作可能会沿树向上直至根节点，导致树的高度减少。
维护不变性：确保所有叶子节点的高度一致、节点大小受控且不为空。这些不变性的维护对于保证B+树的高效查询和更新至关重要。

磁盘上的B树

在内存中实现B树已经可以通过上述原则完成，但在磁盘上实现B树时需要额外考虑一些因素。

基于块的分配

一个关键细节是如何限制节点大小。对于内存中的B+树，可以通过限制节点中键的最大数量来控制节点大小，而在磁盘上的数据结构中，则没有malloc/free或垃圾回收机制可供依赖；空间分配和重用完全取决于我们自己。

如果所有分配都是相同大小的，可以使用空闲列表来进行空间重用，这将在后续实现。目前，所有的B树节点都被设定为相同的大小。

写时复制（Copy-on-Write）B树以确保安全更新

为了使磁盘数据更新具有抗崩溃能力，我们已经了解了三种方法：重命名文件、日志记录以及LSM树。核心思想是在更新过程中不破坏任何旧数据。这个概念也可以应用于树结构：通过复制节点并在副本上进行修改。

插入或删除操作从叶节点开始；在创建带有修改的副本后，必须更新其父节点以指向新的节点，这也需要在其副本上完成。这种复制过程会传播到根节点，最终形成一个新的树根。

原始树保持不变，并且可以从旧根访问。
新根，包含一直延伸到叶节点的所有更新副本，与其他部分共享原有的子树。

    d
   / \
  b   e
 / \
a   c

更新叶节点c：
    D*
   / \
  B*  e
 / \
a   C*

这里，被复制的节点用大写字母表示（D, B, C），而共享的子树用小写字母表示（a, e）。

这种方法被称为写时复制数据结构，也被描述为不可变的、仅追加的（不是字面意义上的），或者是持久化的（与耐久性无关）。需要注意的是，数据库术语并不总是有一致的意义。

写时复制B树还剩下两个问题：

如何找到树根，因为每次更新后它都会改变？这个问题简化为单个指针更新的问题，稍后解决。
如何重用来自旧版本的节点？这是空闲列表的工作。

写时复制B树的优势

保留旧版本的一个优势是自动获得了快照隔离。事务从树的一个版本开始，并不会看到其他版本的变化。崩溃恢复也变得轻松；只需使用最后一个旧版本即可。

另一个优势是它适合多读取者单一写入者的并发模型，且读者不会阻塞写入者。这些将在后面探讨。

替代方案：带双写（Double-Write）的就地更新

虽然写时复制数据结构在崩溃恢复方面很明显，但由于高写放大效应，它们可能是不可取的。每次更新都需要复制整个路径Ο(log 𝑁)，而大多数就地更新只触及一个叶节点。

可以在不使用写时复制的情况下进行带崩溃恢复的就地更新：

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

崩溃后，数据结构可能处于半更新状态，但我们无法确切知道。我们所做的是盲目应用保存的副本，这样无论当前状态如何，数据结构最终都会处于更新后的状态。
在这里插入图片描述

双写（double-write）在MySQL术语中指的是保存的更新副本。但如果双写本身损坏了呢？这与处理日志的方式相同：使用校验和。

如果校验和检测到坏的双写，忽略它。因为它发生在第一次fsync之前，所以主数据仍处于良好且旧的状态。
如果双写良好，应用它将始终产生良好的主数据。

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

崩溃恢复的原则是比较双写与写时复制：

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

两者基于不同的理念：

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

如果我们保存原始节点而不是更新节点用于双写，那就是第三种从损坏中恢复的方法，并且像写时复制一样恢复到旧版本。我们可以将这三种方式合并为一个想法：在任何时候都有足够的信息来恢复到旧状态或新状态。

此外，某些复制总是必要的，因此较大的树节点更新速度较慢。我们将使用写时复制，因为它更简单，但可以根据具体情况偏离这一做法。

代码仓库地址：database-go

B树的异常恢复