07 - B-Tree 结构

SQLite 使用 B-Tree 结构来组织表和索引，因此它是其核心思想。本文仅对该数据结构做介绍，因此不会涉及到任何代码。

为什么 tree 是数据库的良好数据结构呢？

B-Tree 与二叉树不同（“B” 可能代表发明者的名字，也可能是平衡 “balanced” 的意思）。下面是一个 B-Tree 的示例：

example B-Tree (https://en.wikipedia.org/wiki/File:B-tree.svg)

与二叉树不同，每个 B-Tree 的节点可以包含 2 个以上的子节点。每个节点可以至多包含 m 个子节点，其中 m 被称为树的 “order”。为了尽可能的保持树的平衡，我们还需要保证节点必须至少包含 m/2 个子节点（向上取整）。

例外情况：

上图是一棵 B-Tree，SQLite 使用它来存储索引。为了存储表，SQLite 使用了一种称为 B+ tree 的变体。

在我们实现索引之前，我们将只讨论 B+ tree，但是我们将其称为 B-tree 或者 btree。

拥有子子节点的节点被称为内部节点（”internal” nodes）。内部节点和叶子节点是不同的：

For an order-m tree…	Internal Node	Leaf Node
Stores	keys and pointers to children	Keys and values
Number of keys	up to m-1	as many as will fit
Number of pointers	number of keys + 1	none
Number of values	none	number of keys
Key purpose	used for routing	paired with value
Stores values?	No	Yes

让我们通过一个示例来展示 B-tree 在插入元素时如何增长。为了简化，我们采用 order 为 3 的树来做说明。这就意味着：

一个空的 B-tree 仅包含一个节点：root 节点（根节点）。根节点从具有零个键/值对的叶节点开始：

empty btree

如果我们插入几个键/值对，它们将按排序顺序存储在叶节点中。

one-node btree

假设叶子节点的容量是两个键/值对。当我们插入另一个时，我们必须拆分叶子节点并将一半键/值对放入每个节点中。两个节点都成为新内部节点的子节点，该内部节点现在将成为根节点。

two-level btree

这个内部节点拥有 1 个键和 2 个指向子节点的指针。如果我们想要查找小于或等于 5 的键，我们将从左子节点中查找。如果我们想要查找大于 5 的键，我们将从右子节点中查找。

现在，我们插入键 2。首先，如果存在的话，我们将查找它所在的叶子节点，然后到达左边的叶子节点。该节点已满，因此我们拆分叶子节点并在父节点中创建一个新条目。

four-node btree

让我们继续添加键，18 和 21。我们到了必须再次拆分的地步，但是父节点中没有空间可以容纳另一个键/指针对。

no room in internal node

解决方案是将根节点分为两个内部节点，然后创建新的根节点作为其父节点。

three-level btree

树的高度仅在叶子节点分裂的时候才会增加。每个叶子节点的深度都相同，并且键/值对的数量接近相同，因此树保持平衡并且可以快速搜索。

在我们实现插入之前，我将不讨论从树中删除键的讨论。

当我们实现此数据结构时，每个节点将对应一个页面。根节点将存在于页面 0 中。子指针将仅是包含子节点的页码。

在下一节中，我们将开始实现 btree!