当我们考虑数据库的性能时，首先想到的是索引。 在这里，我们将研究数据库索引如何在数据库上工作。 请注意，此处基于SQLite 2.x数据库架构描述了架构细节。 您可以在中找到与该博客相关的SQLite 2.5.0后端实现以及示例测试。

什么是Btree？

Btree是一种数据结构，它按排序顺序将数据存储在其节点中。 我们可以将样本Btree表示如下。

Btree存储数据，以便每个节点包含升序的键。 这些键中的每个键都具有对另外两个子节点的两个引用。 左侧子节点密钥小于当前密钥，右侧子节点密钥大于当前密钥。 如果单个节点具有" n"个键，则它最多可以具有" n + 1"个子节点。

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

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

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

> Binary search

在这里，我们尝试从已排序的数组3、6、8、11、15、18和18中搜索键15。 如果您进行常规搜索，则自该元素位于第五位置以来，将需要五个单位的时间进行搜索。 但是，在二进制搜索中，只需要进行三个搜索。

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

> Binary search to all element

看起来很熟悉？ 它是一棵二叉树。 这是Btree的最简单形式。 对于二叉树，我们可以使用指针而不是将数据保留在已排序的数组中。 从数学上讲，我们可以证明二叉树的最坏情况搜索时间为O（log（n））。 二叉树的概念可以扩展为更广义的形式，即Btree。 Btree不是为单个节点提供单个条目，而是为单个节点使用条目数组，并为每个条目引用子节点。 下面是每个上述方法的时间复杂度比较。

┌────────────────┬───────────┬────────────┬───────────┐│      Type      │ Insertion │  Deletion  │  Lookup   │├────────────────┼───────────┼────────────┼───────────┤│ Unsorted Array │ O(1)      │ O(n)       │ O(n)      ││ Sorted Array   │ O(n)      │ O(n)       │ O(log(n)) ││ Btree          │ O(log(n)) │ O(log(n))) │ O(log(n)) │└────────────────┴───────────┴────────────┴───────────┘

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

> B+tree

在此，在叶节点中再次重复13、30、9、11、16、38个非叶值。 您可以在叶节点的这棵树中看到特产吗？

是的，叶节点包含所有值，并且所有记录均按排序顺序。 在B + tree的特殊情况下，您可以进行与Btree相同的搜索，此外，如果我们按如下所示将指针指向每个叶节点，则可以遍历叶节点中的所有值。

> B+tree with leaf node referencing

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

当Btree进行数据库索引时，由于不仅具有键，而且具有与该键关联的值，因此该数据结构几乎没有什么复杂的。 该值是对实际数据记录的引用。 此键和值一起称为有效负载。

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

┌───────┬───────┬─────┐│ Name  │ Marks │ Age │├───────┼───────┼─────┤│ Jone  │     5 │  28 ││ Alex  │    32 │  45 ││ Tom   │    37 │  23 ││ Ron   │    87 │  13 ││ Mark  │    20 │  48 ││ Bob   │    89 │  32 │└───────┴───────┴─────┘

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

> B+tree on database pages

在这里您可以看到，所有记录都存储在B +树的叶节点中，索引用作创建B +树的关键。 没有记录存储在非叶子节点上。 每个叶节点都引用树中的下一个记录。 数据库可以使用索引执行二进制搜索，也可以通过仅遍历叶节点来搜索每个元素来进行顺序搜索。

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

使用索引时首先，数据库在对应的Btree中搜索给定键，并以O（log（n））时间获得索引。 然后，它使用O（log（n））时间中已找到的索引在B + tree中执行另一个搜索并获取记录。

数据库页面实施

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

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

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

结论

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

(本文翻译自dhanushka madushan的文章《Database Btree Indexing in SQLite》，参考：)