Build Your Own Database from Scratch-3

目录

1. 2、Generalizing binary trees
2. 2、B-tree as nest arrays
3. 1、Two-level nested arrays
4. Without knowing the details of the RB tree or the 2-3-4 tree, the B-tree can be understood from sorted arrays. The problem with sorted arrays is the 𝑂(𝑁) update. If we split the array into 𝑚 smaller non-overlapping ones, the update becomes 𝑂(𝑁/𝑚). But we have to find out which small array to update/query first. So we need another sorted array of references to smaller arrays, that’s the internal nodes in a B+tree. [[1,2,3], [4,6], [9,11,12]] The lookup cost is still O(log𝑁) with 2 binary searches. If we choose 𝑚 as `√n` become O(`√ 𝑁`) , that’s as good as 2-level sorted arrays can be. 无需了解红黑树（RB Tree）或2-3-4树的细节，B树可通过排序数组（Sorted Array）的设计思想理解。 排序数组的痛点在于更新操作的时间复杂度为 𝑂(𝑁)。若将数组分割为 𝑚 个非重叠的小数组，则更新操作的时间复杂度可降至 𝑂(𝑁/𝑚)。但此时需先定位到目标小数组进行更新或查询，因此需要另一个排序数组作为导航结构来索引这些小数组——这便是 B+树中内部节点(Internal Nodes)的由来。
5. 1. 多层级设计的核心思想
6. 3. 节点维护策略
7. 4. 实际应用中的设计考量
8. 5. 优化技术与变种
9. 总结
10. 3、Maintaining a B+tree
11. 1、Growing a B-tree by splitting nodes
12. 2、Shrinking a B-tree by merging nodes
13. 3. 崩溃安全与根指针管理
14. 4. 旧节点回收与多版本控制
15. 5. 性能优化与权衡
16. 总结
17. 3、Copy-on-write B-tree for advantages
18. One advantage of keeping old versions around is that we got snapshot isolation for free. A transaction starts with a version of the tree, and won’t see changes from other versions. And crash recovery is effortless; just use the last old version. Another one is that it fits the multi-reader-single-writer concurrency model, and readers do not block the writer. We’ll explore these later.
19. 1. 快照隔离（Snapshot Isolation）的自动实现
20. 2. 多读者单写者（Multi-Reader-Single-Writer）并发模型
21. 3. 崩溃恢复的简便性
22. 4. 空间回收与垃圾收集
23. 5. 写放大（Write Amplification）的优化
24. 6. 实际应用与系统案例
25. 总结
26. 4、Alternative: In-plcae update with double-write
27. 5、The crash recovery principle
28. 让我们比较一下双写和写时复制： • 双写使更新具有幂等性；数据库可以通过应用已保存的副本重试更新，因为它们是完整节点。 • 写时复制以原子方式将所有内容切换到新版本。 它们基于不同的理念： • 双写确保有足够的信息来生成新版本。 • 写时复制确保保留旧版本。 如果我们使用双写保存原始节点而不是更新的节点会怎样？ 这是从损坏中恢复的第三种方法，它可以像写时复制一样恢复到旧版本。 我们可以将这三种方式合并为一个理念：在任何时候都有足够的信息来表示旧状态或新状态。 此外，某些复制操作始终是必需的，因此较大的树节点更新速度较慢。我们将使用写时复制，因为它更简单，但您可以在此处进行更改。

# 1、B-Tree & Crash Recovery ## 1、Height-balance tree Many practical binary trees, such as the AVL tree or the RB tree, are called height-balanced trees , meaning that the height of the tree (from root to leaves) is limited to 𝑂 ( log 𝑁 ) , so a lookup is 𝑂 ( log 𝑁 ) . A B-tree is also height-balanced; the height is the same for all leaf nodes. **高度平衡树的实践应用** 许多实际应用的二叉树（如**AVL树** 和**红黑树（RB树）**）被称为**高度平衡树（Height-Balanced Tree）**，其核心特性是树的高度（从根节点到叶节点的最长路径）被限制在 **𝑂(log 𝑁)**，从而确保查找操作的时间复杂度为**𝑂(log 𝑁)**。 **B树**同样属于高度平衡树，其所有叶节点到根节点的路径长度一致（即树高统一）。 ### **深度解析与对比** ### **1. 高度平衡的核心目标** - **控制树高**：通过动态调整（如旋转、节点分裂/合并），确保树高始终为 **𝑂(log 𝑁)**，避免退化为链表（𝑂(𝑁) 查找）。 - **优化查询效率**：平衡树高使得每次查询只需遍历约 **log₂𝑁** 个节点。 ### **2. 经典高度平衡树对比**

**示例代码（红黑树插入调整）**：
<empty-block/>
```python

class RBTree: def insert(self, key): node = Node(key) self._insert_node(node) self._fix_insert(node) # 通过旋转和颜色调整维持平衡

def _fix_insert(self, node):
    while node.parent and node.parent.color == RED:
        # 根据叔节点颜色选择旋转策略
        if uncle.color == RED:
            self._recolor(node)
        else:
            if node.is_left_child() != uncle.is_left_child():
                self._rotate(node.parent)
            self._rotate(grandparent)
            self._swap_colors(grandparent, parent)
```
### **3. B树的高度平衡特性**
- **多叉结构**：每个节点存储 **𝑚 个键和 𝑚+1 个子节点指针**（𝑚 ≥ 2）。
- **节点容量控制**：
	- **最小键数**：除根节点外，每个节点至少有 **⌈𝑚/2⌉−1** 个键。
	- **分裂与合并**：插入导致溢出时分裂节点，删除导致不足时合并节点。
**B树高度公式**：
$$
树高 h≤log⌈m/2⌉((N+1)/2)
$$
- **示例**：
	- 若 𝑚=500，存储 1 亿条数据时，树高 𝑁 ≈ 3（3次磁盘IO即可定位数据）。
### **4. 实际应用场景**
- **AVL树**：
	- **优势**：严格平衡，查询效率极致。
	- **案例**：内存数据库（如 Redis 的有序集合通过跳表实现类似效果）。
- **红黑树**：
	- **优势**：插入/删除效率高（平均仅需1次旋转）。
	- **案例**：Java 的 **`TreeMap`**、C++ 的 **`std::map`**。
- **B/B+树**：
	- **优势**：减少磁盘IO（节点大小对齐磁盘页）。
	- **案例**：MySQL InnoDB 的索引、文件系统（NTFS、Ext4）。
---
### **平衡树的工程权衡**

---
### **总结**
高度平衡树通过动态调整策略（旋转、分裂、合并），在增删改查操作中维持 **𝑂(log 𝑁)** 的时间复杂度。选择具体实现需权衡：
- **读写比例**：读多写少选 AVL，写多读少选红黑。
- **存储介质**：内存场景用二叉树，磁盘场景用 B/B+树。
	这一设计哲学深刻影响了数据库、文件系统及语言标准库的实现。

2、Generalizing binary trees#

n-ary trees can be generalized from binary trees (and vice versa). An example is the 2-3-4 tree, which is a B-tree where each node can have either 2, 3, or 4 children. The 2-3-4 tree is equivalent to the RB tree. However, we won’t go into the details because they are not necessary for understanding B-trees. Visualizing a 2-level B+tree of a sorted sequence [1, 2, 3, 4, 6, 9, 11, 12]. In a B+tree, only leaf nodes contain value, keys are duplicated in internal nodes to indicate the key range of the subtree. In this example, node [1, 4, 9] indicates that its 3 subtrees are within intervals [1, 4), [4, 9), and [9, + ∞ ). However, only 2 keys are needed for 3 intervals, so the first key (1) can be omitted and the 3 intervals become (- ∞ , 4), [4, 9), and (9, + ∞ ). 多叉树（n-ary trees）与二叉树的相互推广 多叉树可从二叉树推广而来（反之亦然）。例如，2-3-4树 是一种 B 树的特例，其每个节点可含 2、3 或 4 个子节点。2-3-4树与红黑树（Red-Black Tree）本质等价，但由于理解 B 树无需此细节，此处暂不深入。 B+树的结构可视化示例 以下是一个两层的 B+树，存储有序序列 [1, 2, 3, 4, 6, 9, 11, 12]： 在 B+树中：

• 叶子节点：存储实际数据（键值对）。
• 内部节点：仅存储导航键（重复叶子节点的键），用于指示子树键范围。

---

** 关键技术解析** 1. B+树内部节点的键作用

• 键范围划分： 内部节点的键定义子树的键区间。以上例中，根节点 [1,4,9] 表示：
  • 第一个子树：键范围 (-∞, 4)
  • 第二个子树：键范围 [4, 9)
  • 第三个子树：键范围 [9, +∞)
• 键省略优化： 第一个键（如 1）可省略，因为左子树的下界默认延伸至负无穷，从而减少冗余存储。优化后内部节点变为 [4,9]，区间划分更简洁。 2. B+树与2-3-4树的联系

3. 键范围的实际表示

• 未优化前：

根节点键：1, 4, 9 子树区间：[1,4), [4,9), [9,+∞) ```

• 优化后：

根节点键：4, 9 子树区间：(-∞,4), [4,9), [9,+∞) ``` - 优势：减少一个键的存储开销，同时保持区间逻辑不变。 4. B+树的查询流程

1. 根节点定位：
   • 查找键 K=6 → 比较根节点键 4 和 9，确定进入第二子树 [4,9)。
2. 叶子节点访问：
   • 加载子节点 [4,6]，发现 6 属于该节点范围，返回对应值。 5. 实际系统的键管理

• 键压缩技术：
  • 前缀压缩：若键有序（如时间戳），仅存储差异部分。
  • 字典编码：将重复键映射为短标识符。
• 区间合并优化： 对删除操作频繁的区间，合并相邻叶子节点以减少碎片。

---

总结 B+树通过以下设计实现高效存储与查询：

1. 层级化导航键：内部节点通过省略冗余键优化存储，定义清晰的子树区间。
2. 叶子节点链表：支持高效范围扫描（如 WHERE age BETWEEN 20 AND 30）。
3. 平衡与扩展性：通过节点分裂/合并动态适应数据增长，保持 𝑂(log 𝑁) 时间复杂度。 这一设计被 MySQL InnoDB、Oracle Berkeley DB 等数据库广泛采用，成为处理海量数据的核心索引结构。理解其键范围划分与优化策略，是调优存储性能的关键。

2、B-tree as nest arrays#

1、Two-level nested arrays#

Without knowing the details of the RB tree or the 2-3-4 tree, the B-tree can be understood from sorted arrays. The problem with sorted arrays is the 𝑂(𝑁) update. If we split the array into 𝑚 smaller non-overlapping ones, the update becomes 𝑂(𝑁/𝑚). But we have to find out which small array to update/query first. So we need another sorted array of references to smaller arrays, that’s the internal nodes in a B+tree. [[1,2,3], [4,6], [9,11,12]] The lookup cost is still O(log𝑁) with 2 binary searches. If we choose 𝑚 as $`√n`$‘√n‘ become O($`√ 𝑁`$‘√N‘) , that’s as good as 2-level sorted arrays can be. 无需了解红黑树（RB Tree）或2-3-4树的细节，B树可通过排序数组（Sorted Array）的设计思想理解。 排序数组的痛点在于更新操作的时间复杂度为 𝑂(𝑁)。若将数组分割为 𝑚 个非重叠的小数组，则更新操作的时间复杂度可降至 𝑂(𝑁/𝑚)。但此时需先定位到目标小数组进行更新或查询，因此需要另一个排序数组作为导航结构来索引这些小数组——这便是 B+树中内部节点(Internal Nodes)的由来。#

深度解析与扩展

1. 多层级设计的核心思想#

通过递归分割将数据组织为多级结构，确保每个节点的数据量上限为常数 𝑠，从而控制单次操作的局部性。 示例：3 层级 B+树（𝑠=4） plain text 层级1（根节点）： [ 20, 40] / | \ 层级2： [10] [30] [50] / \ | \ 层级3（叶节点）：[5,7,9] [12,15,18] [25,28] [35,38] [45,47,55,60] - 查询键 28： 1. 根节点定位到中间子树（20 < 28 ≤ 40）。 2. 中间子树定位到叶节点 [25,28]。 3. 时间复杂度：𝑂(log(𝑁/4) + log 4) = 𝑂(log 𝑁)。 --- ### 2. 时间复杂度分析

**关键点**：
- **log(𝑁/𝑠) + log 𝑠 = log 𝑁**（对数运算性质）。
- 常数 𝑠 的设计使得叶节点操作（如插入、删除）的局部成本可控（𝑂(𝑠) ≈ 常数时间）。
---
### **3. 节点维护策略**
### **(1) 分裂（Split）**
**触发条件**：节点键数超过 𝑠。
**流程**：
1. 将节点分为两个子节点（如原节点键为 \[1,3,5,7,9\]，𝑠=4 → 分裂为 \[1,3\] 和 \[7,9\]，中间键 5 提升至父节点）。
2. 若父节点因此溢出，递归向上分裂。
### **(2) 合并（Merge）与重平衡（Rebalance）**
**触发条件**：节点键数低于最小阈值（如 𝑠/2）。
**策略**：
- **借键**：从相邻兄弟节点借一个键（若兄弟节点有富余）。
- **合并**：与相邻节点合并，并更新父节点键。
**示例（𝑠=4，最小键数=2）**：
- 删除导致叶节点键数从 \[5,7\] 变为 \[5\] → 需从相邻节点 \[12,15,18\] 借键或合并。
---
### **4. 实际应用中的设计考量**
### **(1) 节点大小 𝑠 的选择**

**经验值**：
- **内存数据库**：𝑠 ≈ 100\~500（平衡树高与缓存行）。
- **磁盘数据库**：𝑠 对齐磁盘页大小（如 4KB页 → 𝑠=512键，假设每键8B）。
### **(2) 并发控制**
- **锁粒度**：节点级锁（B+树常见） vs. 子树级锁（B-link树优化）。
- **无锁结构**：COW（Copy-on-Write）技术，如 LMDB 使用 B+树 + 影子分页。
---
### **5. 优化技术与变种**
- **B+树与 LSM-tree 融合**：
	- 内存使用 B+树（MemTable），磁盘使用 SSTable（日志结构合并）。
	- **优势**：结合 B+树的低查询延迟与 LSM-tree 的高写入吞吐。
- **自适应节点大小**：
	动态调整 𝑠 值（如根据负载自动增减），平衡读写性能。
---
### **总结**
通过多级分块与节点大小约束（𝑠），B+树实现了：
1. **稳定对数时间复杂度**：查询、插入、删除均为 𝑂(log 𝑁)。
2. **高效IO利用**：节点对齐磁盘页，减少随机访问。
3. **动态平衡**：分裂/合并维护节点填充率，避免性能退化。
实际系统（如 **MySQL InnoDB、Oracle Berkeley DB**）通过精细调整 𝑠 和合并策略，应对不同负载场景。理解这一机制是优化存储引擎性能的基石。