一起做个简单的数据库(七):B树介绍


用C语言从零开始实现SQLite clone系列:
  1. REPL的介绍和设置
  2. 世上最简单的SQL编译器和虚拟机
  3. 一个在内存中仅能做追加操作的单表数据库
  4. 第一次测试 (含bug处理)
  5. 持久化存储
  6. The Cursor Abstraction


B树是SQLite用来表示表和索引的数据结构,因此它是一个非常重要的概念。本文将仅介绍数据结构,没有任何代码。

为什么树是数据库较好的一种数据结构?
  • 搜索特定值的速度快(指数级logarithmic time)
  • 插入/删除很快(constant-ish time to rebalance重新平衡的时间稳定)
  • 遍历很快(和HASH MAP相比)


B树不同于二叉树(“B”可能是发明者的名字,但也可能是“平衡”的意思)。这是一个B树示例:
1.jpg

不同于二叉树,每个B树的节点都可以有两个以上的孩子,每个节点都可以至多有M个孩子,我们称M为树的阶(order)。为了使树保持平衡,我们规定节点必须至少有M/2个孩子(向上取整)。

例外情况:
  • 叶子没有子节点
  • 跟节点的数量可以小于M,要大于等于2
  • 如果跟节点是叶子节点(意味着整个B树只有一个节点)它的子节点数仍然为0


上面的图片是一个被SQLite用来存储索引的B树。SQLite使用称为B+树的变体SQLite存储表。
2.JPG

在实现索引之前,我将仅讨论B+树,但在这里我称其称为B树。

具有子节点的节点称为“内部”节点。内部节点和叶节点的结构不同:
5.JPG

我们通过个例子来看看当我们向B树中插入个元素,B树是如何变化的。简单起见,树的阶数为3。这意味着:
  • 每个内部节点最多有3个子节点
  • 每个内部节点最多有2个键
  • 每个内部节点最少有2个子节点
  • 每个内部节点最少有1个键


一个空的B树只有一个节点,即根节点。这个根节点一开始等同于叶子节点,键值对为0:
4.jpg

空树

如果我们插入一个键值对,他们将按顺序存储在叶子节点中。
6.jpg

单节点B树

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

内部节点具有1个键和2个指向子节点的指针。如果我们要查找小于或等于5的键,我们在左侧子节点查找。如果我们想查找大于5的键,我们在右侧子节点查找。
8.jpg

我们继续添加键18和21。节点要再次拆分,但是父节点中没有空间可以容纳另一个键/指针对。
9.jpg

解决的办法是把根节点再拆分成2个内部节点,再新生成根节点作为这2个内部节点的父节点。
10.jpg

仅当我们不断地拆分根节点,B树的深度才会不断增加。每个叶子节点具有相同的深度,键值对的数量也趋近相同。所以B树保持平衡,并且查询也会很快。

直到我们实施插入操作之前,我不讨论如何从树中删除键。

当我们采用这种数据结构时,每个节点将对应一个页面。根节点将存在于页面0中。子指针将仅是包含子节点的页码。

下一篇,我们开始实现B树!

原文链接:Part 7 - Introduction to the B-Tree(翻译:吴世曦)

0 个评论

要回复文章请先登录注册