第七部分 - B树

SQLite 的表和索引的数据结构都采用了B树（B-Tree），因此B树是一个非常重要的概念。在本章中，我们将只介绍B树这种数据结构，因此不会有任何代码。

为什么说树是一个非常适合数据库的数据结构呢？

B树不同于二叉树（“B”可能表示的是发明者的名字，也可以表示“balanced” 注：「平衡的」）。下面是一个B树的例子：

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

和二叉树不同，B树的每一个节点可以拥有超过两个子节点。每个节点可以拥有最多 m 个子节点，m 又被叫做树的“阶”。为了使树尽可能的接近平衡，我们还说节点必须拥有至少 m/2 （向上取整）个子节点。

例外：

上图所示是一个B树，在 SQLite 中被用于存储索引，而为了存储表数据，SQLite 用了B树的一种变体，我们称之为 B+ 树。

在我们开始实现索引之前，我将只介绍 B+ 树，但我会将它称之为B-树（B-Tree）或者B树（btree）。

“内部”节点指那些拥有子节点的节点。内部节点和叶子节点的结构是不一样的：

让我们通过一个例子来了解当你往一棵B树插入一个元素会发生什么。对了，简单起见，我们用一棵三阶树来示范，这就意味着：

一棵空B树只有一个节点：根节点。开始的时候，由于没有键/值对，根节点也是叶子节点：

空B树

如果这时我们插入一组键值对，那么它们会被排序后保存到叶子节点中。

一个节点的B树

假设叶子节点的容量是两个键/值对。当再插入一个键/值对时，我们就必须将这个叶子节点拆分到两个节点，每个节点拥有一半键/值对。这时根节点就会变成一个新的内部节点，且刚刚拆分的两个节点将成为这个内部节点的子节点。

两层的B树

内部节点有一个键和两个指向子节点的指针。如果我们想要查找小于等于 5 的 key ，那么我们需要找左子节点；而如果我们要找的 key 是大于 5 的，则找右子节点。

我们试着插入一个 key “2”。首先我们先判断假如它已经存在于B树上，它会在哪个叶子节点，会发现我们找到了左叶子节点。这个节点现在是满的，所以我们要将这个叶子节点拆分，然后在父节点创建一个入口。

four-node btree

我们继续插入新的 key，18 和 21。然后我们就会再次面临需要再次拆分，但这个时候在父节点已经没有空间来存放更多的键/值对了。

no room in internal node

解决方案就是拆分根节点成两个内部节点，然后创建一个新的根节点作为它们的父节点。

three-level btree

当我们拆分根节点的时候，树的深度就增加了。每个叶子节点都有相同的深度和相近的键/值对数，这棵树保持了平衡因此查找是很快的。

在我们实现了插入之前，我将先不展开关于删除 key 的介绍了。

在我们实现这个数据结构的时候，每个节点对应一页。根节点会保存在 0 号页，子节点指针将只是包含了子节点的页号。

在下一章，我们将开始实现B树！