简单数据库实现——Part7 - B树简介
对数据结构不太熟悉的话可以先补一下数据结构。
B树是sqlite用来表示表和索引的数据结构，此处只介绍数据结构，没有任何代码。
为什么树(tree)对数据库来说是一个好的数据结构？
- 可以很快的查询特定值（对数时间复杂度）
- 可以快速插入/删除已找到的数据（常数时间复杂度）
- 遍历一个区间的至很快（与hash map的不同）
B树不同于二叉树（B可能代表发明者的名字，但也可能代表平衡balanced）。这是一个b树的例子：
https://en.wikipedia.org/wiki/File:B-tree.svg
与二叉树不同，B树中的每个节点可以有两个以上的子节点。 每个节点最多可以有m个子节点，其中m被称为树的“order”。 为了使树保持平衡，节点还必须至少有 ? m 2 ? \lceil \frac{m}{2} \rceil ?2m?? 个子节点。
特例：
- 叶节点有0个子节点
- 根节点可以有少于m个子节点，但必须至少有2个子节点
- 如果根节点是叶节点（唯一的节点），它仍有0个子节点
上面的图片是一个B树，sqlite使用它来存储索引(index)。sqlite使用一种称为B+树的变体来存储表(table)。
| B-tree | B+ tree | |
|---|---|---|
| 用于存储 | 索引 | 表 |
| 节点存储key | Yes | Yes |
| 节点存储value | Yes | No |
| 节点儿子数 | 少 | 多 |
| 内部节点和叶节点 | 相同结构 | 不同结构 |
在实现索引前，我们只讨论B+树（下面统称为B树）。
有子节点的节点我们称为内部节点，内部节点和叶节点的结构是不同的。
| 对于有序m树 | 内部节点 | 叶节点 |
|---|---|---|
| 存储 | key和指向子节点的指针 | key和vaule |
| key数量 | 最多m-1 | 需要多少就有多少 |
| 指针数量 | key数量+1 | 无 |
| value数量 | 无 | 与key数量相同 |
| key的作用 | 用于寻路 | 绑定值 |
| 存储value | No | Yes |
我们通过一个例子来观察B树如何进行插入数据。我们令order为3，也就是m=3。这意味着：
- 每个内部节点最多有3个子节点
- 每个内部节点最多有2个key
- 每个内部节点至少有2个子节点
- 每个内部节点至少有1个key
空的B树只有一个节点：根节点。根节点一开始是一个没有键值对(key/value pair)的叶节点。
如果我们插入几个键值对，他们会排序好存在叶节点中。这里插入键值对：(5,“a”)，(12,“b”)。
此时一个叶节点的容量为2个键值对，当我们插入新的时，我们需要分裂(split)叶节点。我们会有2个新的叶节点，和1个内部节点（根节点）。
内部节点有1个key和2个指向子节点的指针。如果我们要查找小于等于5的key，我们要查找左子节点，反之查询右节点。
现在我们插入key 2，我们首先查找它如果存在的话应该在哪个叶节点中，然后我们到达左叶节点。因为节点已满，所以我们要进行分裂(split)，此时我们拆分叶节点并在父节点中创建新的联系，这是另一种分裂的方式。
继续添加key，18和21。此时右叶节点已满，需要进行分裂，然而分裂之后，父节点没有空间容纳新的键指针对(key/pointer pair)，因为最多只能有3个。
解决方法是将根节点分为两个内部节点。
仅当我们分裂根节点时，树的深度才会增加，每个叶结点深度都相同，并且键值对的数量接近相同，因此树保持平衡并且可以快速搜索。
在我们实现插入之前，暂时不讨论删除的问题。
当我们实现这个数据结构时，每个节点都对应一个页。根节点将存在于页0中。子指针只是包含子节点的页号。
下一部分我们要开始实现B树（B+树）。