3.B树：原理
# 03. B树：原理
# 3.1 B树和二叉搜索树（BST）的直观理解
我们对B树的初步理解源自平衡二叉搜索树（BST）。二叉树是存储有序数据的常用数据结构。在插入或删除键之后，保持树的良好形态就是 “平衡” 的含义。正如上一章所述，为了利用 “页”（IO的最小单位），应该使用n叉树而非二叉树。
B树可以看作是二叉搜索树的扩展。B树的每个节点包含多个键和多个指向子节点的链接。在节点中查找键时，会依据所有键来确定下一个子节点。
[1, 4, 9]
/ | \
v v v
[1, 2, 3] [4, 6] [9, 11, 12]
2
3
4
B树的平衡方式与二叉搜索树不同。像红黑树（RB树）或AVL树这样常见的二叉搜索树，是通过旋转操作，基于子树高度来实现平衡的。而B树所有叶节点的高度相同，它是依据节点大小来实现平衡的：
- 如果一个节点太大，无法存放在一个页中，就将其分裂为两个节点。这会增加父节点的大小，如果根节点分裂，还有可能增加树的高度。
- 如果一个节点太小，尝试将其与兄弟节点合并。
如果你熟悉红黑树，可能也了解2 - 3树，2 - 3树很容易扩展为B树。
# 3.2 B树和嵌套数组
即便你不熟悉2 - 3树，也可以通过嵌套数组获得一些直观认识。
让我们从一个有序数组开始。查询操作可以通过二分查找来完成。但是，更新数组的时间复杂度是O(n)，这是我们需要解决的问题。更新大数组效率很低，所以我们将其分割成较小的数组。假设我们把数组分成$\sqrt{n}$个部分，每个部分平均包含$\sqrt{n}$个键。
[[1,2,3], [4,6], [9,11,12]]
要查询一个键，我们必须先确定该键位于哪个部分，对$\sqrt{n}$个部分进行二分查找的时间复杂度是O(log(n))。之后，在该部分内对键进行二分查找，时间复杂度同样是O(log(n))，整体效率并不比之前差。而且更新操作的时间复杂度提升到了O($\sqrt{n}$)。
这是一个2层的有序嵌套数组，如果增加更多层级会怎样呢？这就是对B树的另一种直观理解。
# 3.3 B树操作
查询B树和查询二叉搜索树的方式相同。
更新B树则更为复杂。从现在起，我们将使用一种称为 “B + 树” 的B树变体，B + 树仅在叶节点存储值，内部节点只包含键。
插入键从叶节点开始。叶节点本质上就是一个有序的键列表。将键插入叶节点很简单，但插入操作可能会导致节点大小超过页大小。在这种情况下，我们需要将叶节点分裂为2个节点，每个节点包含一半的键，这样两个叶节点都能放入一个页中。
一个内部节点由以下部分组成：
- 指向子节点的指针列表。
- 与指针列表配对的键列表。每个键都是对应子节点的第一个键。
将叶节点分裂为2个节点后，父节点会用新的指针和键替换旧的指针和键。节点大小会增加，这可能会触发进一步的分裂。
parent parent
/ | \ => / | | \
L1 L2 L6 L1 L3 L4 L6
2
3
当根节点分裂时，会添加一个新的根节点。B树就是这样生长的。
new_root
/ \
root N1 N2
/ | \ => / | | \
L1 L2 L6 L1 L3 L4 L6
2
3
4
5
删除键的操作与插入相反。节点永远不会为空，因为较小的节点会与其左兄弟节点或右兄弟节点合并。
当非叶根节点缩减为单个键时，根节点可以由其唯一的子节点替代。B树就是这样收缩的。
# 3.4 不可变数据结构
不可变（Immutable）意味着永远不在原地更新数据。一些类似的术语有 “只追加（append - only）”、“写时复制（copy - on - write）” 和 “持久化数据结构（persistent data structures）”（这里的 “持久化（persistent）” 与我们之前讨论的 “持久化（persistence）” 没有关系）。
例如，向叶节点插入键时，不要在原地修改该节点，而是创建一个新节点，包含要更新节点的所有键以及新插入的键。此时，父节点也必须更新，以指向新节点。
同样，父节点会带着新指针被复制。一直到根节点，整个路径都会被复制。这实际上创建了树的一个新版本，与旧版本共存。
不可变数据结构有几个优点：
- 避免数据损坏。不可变数据结构不会修改现有数据，只是添加新数据，所以即使更新操作被中断，旧版本的数据依然完好无损。
- 易于并发操作。读者可以与写者并发操作，因为读者可以不受影响地处理旧版本数据。
持久化和并发相关内容将在后面的章节介绍。目前，我们先编码实现一个不可变的B + 树。