【译】数据库B树索引的工作原理

原文链接:https://dzone.com/articles/database-btree-indexing-in-sqlite

作者：Dhanushka Madushan

当我们考虑数据库的性能时，首先想到的是索引。在这里，我们将研究数据库索引如何在数据库上工作。请注意，这里的架构细节是参考 SQLite 2.x 数据库架构来描述的。您可以通过测试找到 SQLite 2.5.0 的后端实现，这与来自 https://github.com/madushadhanushka/simple-sqlite 的这篇文章相关。

阅读这篇 DZone 文章中的整体 SQLite 数据库架构是如何组成的。

什么是 B-tree ？

B-tree 是一种数据结构，它提供排序的数据，并允许按排序顺序进行搜索、顺序访问、附件和删除。 B-tree 非常适合写入大块数据的存储系统。 B 树通过允许具有两个以上子节点的节点来简化二叉搜索树。以下为样本 B 树示例：

B-tree 存储数据，使得每个节点包含按升序排列的键。这些键中的每一个都有对另外两个子节点的两个引用。左侧子节点键小于当前键，右侧子节点键多于当前键。如果单个节点有“n”个键，那么它最多可以有“n+1”个子节点。

为什么在数据库中使用索引？

想象一下，您需要在文件中存储一个数字列表并在该列表中搜索给定的数字。最简单的解决方案是将数据存储在数组中，并在新值出现时附加值。但是如果你需要检查给定的值是否存在于数组中，那么你需要一一搜索所有的数组元素并检查给定的值是否存在。如果你足够幸运，你可以在第一个元素中找到给定的值。在最坏的情况下，该值可能是数组中的最后一个元素。我们可以用渐近符号将这种最坏情况表示为 O(n)。这意味着如果您的数组大小最多为“n”，则您需要执行“n”次搜索才能在数组中找到给定值。

这次你怎么改进？最简单的解决方案是对数组进行排序并使用二进制搜索来查找值。每当您将值插入数组时，它都应该保持顺序。从数组中间选择一个值开始搜索。然后将所选值与搜索值进行比较。如果所选值大于搜索值，则忽略数组的左侧并搜索右侧的值，反之亦然。

在这里，我们尝试从数组 3、6、8、11、15 和 18 中搜索键 15，它们已经按排序顺序排列。如果您进行正常搜索，则由于元素位于第五个位置，因此需要五个单位的时间进行搜索。但是在二分查找中，它只需要三个查找。

如果我们将此二进制搜索应用于数组中的所有元素，则如下所示。



看着眼熟？它是一棵二叉树。这是 B 树的最简单形式。对于二叉树，我们可以使用指针而不是将数据保存在排序数组中。在数学上，我们可以证明二叉树的最坏情况搜索时间是 O(log(n))。二叉树的概念可以扩展为更广义的形式，称为 B 树。 B-tree 不是为单个节点使用单个条目，而是为单个节点使用条目数组，并为每个条目引用子节点。以下是每种预先描述的方法的一些时间复杂度比较。



B+tree是另一种用于存储数据的数据结构，看起来和B-tree几乎一样。 B+tree 的唯一区别是它在叶子节点上存储数据。这意味着所有非叶节点值再次在叶节点中重复。下面是一个示例 B+树。

13、30、9、11、16 和 38 个非叶值在叶节点中再次重复。你能在叶子节点看到这棵树的特长吗？

是的，叶节点包括所有值，所有记录都按排序顺序排列。 B+tree 的特点是，你可以进行与 B-tree 相同的搜索，此外，如果我们如下放置一个指向每个叶节点的指针，你可以遍历叶节点中的所有值。

如何在数据库中使用索引？

当 B-tree 涉及到数据库索引时，这个数据结构变得有点复杂，不仅有一个键，而且还有一个与键关联的值。该值是对实际数据记录的引用。键和值一起称为有效负载。

假设需要将以下三列表存储在数据库中。

首先，数据库为每个给定记录创建一个唯一的随机索引（或主键），并将相关行转换为字节流。然后，它将每个键和记录字节流存储在 B+树上。这里，随机索引用作索引的键。密钥和记录字节流统称为有效载荷。生成的 B+树可以表示如下。



在这里你可以看到所有的记录都存储在 B+tree 的叶子节点中，并且索引用作创建 B+tree 的 key。没有记录存储在非叶节点上。每个叶节点都引用了树中的下一条记录。数据库可以通过使用索引或顺序搜索来执行二进制搜索，方法是仅通过叶节点来搜索每个元素。

如果不使用索引，则数据库读取这些记录中的每一个以找到给定的记录。启用索引后，数据库会为表中的每一列创建三个 B 树，如下所示。这里的键是用于索引的 B 树键。索引是对实际数据记录的引用。



当首先使用索引时，数据库搜索给定的键对应于 B-tree 并在 O(log(n)) 时间内获取索引。然后，它在 O(log(n)) 时间内使用已经找到的索引在 B+tree 中执行另一次搜索并获取记录。

B-tree 和 B+tree 中的每个节点都存储在 Pages 中。页面大小固定。页面具有从一开始的唯一编号。通过使用页码，一个页面可以是对另一个页面的引用。在页面的开头，页面元详细信息，例如最右边的子页号、第一个空闲单元格偏移量和存储的第一个单元格偏移量。数据库中可以有两种类型的页面：

• 用于索引的页面：这些页面仅存储索引和对另一个页面的引用。

  
  



• 存储记录的页面：这些页面存储实际数据，页面应该是叶子页面。

  
  

使用 SQLite B 树索引

创建 B-tree 索引的基本语法如下：

CREATE INDEX index_name ON table_name;


SQLite 中使用了三种索引方法。

1.单列索引

在这里，索引是基于一个表列创建的。只为索引创建一个 Btree。语法如下：

CREATE INDEX index_name ON table_name (column_name);


2.唯一索引

唯一索引不允许为使用索引的列存储重复值。语法可以写成如下：

CREATE UNIQUE INDEX index_name on table_name (column_name);


3.综合索引

这种类型的索引可以有多个索引。对于每个索引列，都存在一个 B-tree。以下是复合索引的语法：

CREATE INDEX index_name on table_name (column1, column2);


结 论

数据库应该有一种有效的方式来存储、读取和修改数据。 B-tree 提供了一种插入和读取数据的有效方法。在实际的 Database 实现中，数据库同时使用 B-tree 和 B+tree 来存储数据。 B-tree 用于索引，B+tree 用于存储实际记录。 B+tree 除了提供二分查找外，还提供顺序查找功能，这使数据库可以更好地控制在数据库中搜索非索引值。