发现Postgres索引背后的计算机科学

这是Pat Shaughnessy根据其在巴塞罗那Ruby会议上的演讲而撰写的一系列Postgres帖子中的最后一篇。 您还可以观看演示文稿的录像 。 该系列最初发布在他的个人博客上，经他的允许，我们正在Codeship上重新发布该系列。 您还可以阅读系列中的文章 1，2和3 。

众所周知，索引是关系数据库服务器最强大，最重要的功能之一。 您如何快速搜索值？ 创建一个索引。 将两个表连接在一起时，您要记住做什么？ 创建一个索引。 您如何加快开始缓慢运行的SQL语句？ 创建一个索引。

但是什么是索引呢？ 以及它们如何加快我们的数据库搜索？

为了找出答案，我决定在PostgreSQL数据库服务器中读取C源代码，以在其搜索索引中查找简单字符串值时遵循该源代码。 我期望找到复杂的算法和有效的数据结构。 而我做到了。

今天，我将向您展示Postgres中的索引是什么样的，并解释它们如何工作。 我没想到的发现-我第一次阅读Postgres C源代码时发现的-是计算机科学理论在做的事。 阅读Postgres资料就像是回到学校，上了我小时候从未有过的课。 Postgres中的C注释不仅解释了Postgres的功能，还解释了原因。

您知道索引很强大。 你知道他们很重要。 但是您知道它们如何工作吗？

点击鸣叫

序列扫描：轻松搜索

当我们离开Nautilus的工作人员时，他们筋疲力尽，开始晕倒：Postgres序列扫描算法无意识地遍历了user表中的所有记录！

在我的上一篇文章中，我们执行了以下简单的SQL语句来查找Nemo上尉：

Postgres首先解析，分析并计划了查询。 然后ExecSeqScan ，Postgres内部的C函数，实现了序列扫描（SEQSCAN）计划节点，Swift找到了Nemo上尉：

但是随后，莫名其妙的Postgres继续遍历整个用户表，将每个名称与“ Nemo船长”进行了比较，即使我们已经找到了所要的东西！

假设我们的用户表中有数百万条记录； 这可能需要很长时间。 当然，我们可以通过删除排序并重写查询以接受名字来避免这种情况，但更深层的问题是Postgres搜索目标字符串的方式效率低下。

使用序列扫描将用户表中的每个单个值与“ Nemo船长”进行比较是缓慢，低效的，并且取决于名称出现在表中的随机顺序。 我们做错了什么？ 肯定有更好的办法！

答案很简单：我们忘记了创建索引。 现在开始吧。

创建索引

创建索引非常简单-我们只需要运行以下命令：

作为Ruby开发人员，我们当然会使用add_index ActiveRecord迁移； 这将在幕后运行相同的CREATE INDEX命令。 当我们重新运行select语句时，Postgres将像往常一样创建一个计划树-但是这次计划树将略有不同：

注意底部的Postgres现在使用INDEXSCAN而不是SEQSCAN。 与SEQSCAN不同，INDEXSCAN不会遍历整个用户表。 取而代之的是，它将使用我们刚创建的索引来快速有效地查找并返回Nemo船长记录。

创建索引已解决了我们的性能问题，但同时也给我们带来了许多有趣的未解决的问题：

• 究竟什么是Postgres索引？
• 如果我可以进入Postgres数据库并仔细查看索引， 它将是什么样 ？
• 索引如何加快搜索速度？

让我们尝试通过阅读Postgres C源代码来回答这些问题。

究竟什么是Postgres索引？

我们可以从CREATE INDEX命令的文档开始。

在这里，您可以看到我们可以用来创建索引的所有选项，例如UNIQUE和CONCURRENTLY 。 注意，有一个名为USING method的选项。 这告诉Postgres我们想要什么样的索引。 在同一页面的最下方是有关方法的一些信息，即USING关键字的参数：

事实证明Postgres实现了四种不同类型的索引。 您可以将它们用于不同类型的数据和不同的情况。 因为我们根本没有指定USING ，所以index_users_on_name索引是默认的“ btree”（或B-Tree）索引。

这是我们的第一个线索：Postgres索引是B树。 但是什么是B树？ 我们在哪里可以找到一个？ 当然在Postgres内部！ 让我们在Postgres C源代码中搜索包含“ btree：”的文件。

关键结果以粗体显示：“ ./ backend / access / nbtree”。 在此目录中是一个README文件。 让我们看一下：

令人惊讶的是，这个README文件竟然是一个详尽的12页文档！ Postgres源代码不仅包含有用的和有趣的C注释，还包含有关数据库服务器的理论和实现的文档。

阅读和理解开源项目中的代码通常会令人生畏和困难，但对于Postgres而言并非如此。 Postgres背后的开发人员竭尽全力帮助我们其他人了解他们的工作。

自述文件的标题为“ Btree索引”，确认该目录包含实现Postgres B-Tree索引的C代码。 但是第一句话更加有趣：这是对一篇学术论文的引用，该论文解释了B树是什么，以及Postgres索引如何工作：Lehman和Yao的有效锁定B树上的并发操作 。

我们将首先在此学术论文中发现B-树。

B树索引是什么样的？

雷曼和姚明的论文解释了他们在1981年对B-Tree算法进行的一项创新。我将在稍后讨论。 但是他们从简单介绍B-Tree数据结构入手，该结构实际​​上是在1972年9年前发明的。其中一张图显示了一个简单的B-Tree的示例：

术语B树实际上代表“平衡树”。 B树使搜索变得轻松快捷。 例如，如果在此示例中要搜索值53，则首先从包含值40的根节点开始：

我们将目标值53与在树节点中找到的值进行比较。 53是否大于或小于40？ 因为53大于40，所以我们将指针向右下方移动。 如果要搜索29，我们将向左走。 右边的指针导致更大的价值； 左侧的指针指向较小的指针。

沿着树下的指针指向下一个子树节点，我们遇到一个包含2个值的节点：

这次我们将53与47和62进行比较，发现47 <53 <62。请注意，树节点中的值已排序，因此这很容易做到。 这次我们跟随中心指针向下。 现在我们转到另一个树节点，其中有3个值：

浏览排序的数字列表，我们发现51 <53 <56，并跟随四个指针中的第二个向下。 最后，我们来到树中的叶子节点：

我们发现值53！

B树加快了搜索速度，因为：

• 它们对每个节点内的值（称为keys ）进行排序。
• 它们是平衡的 ：B树在各个节点之间平均分配**，从而最大程度地减少了我们必须将指针从一个节点指向另一个节点的次数。 每个指针都指向一个子节点，该子节点或多或少地包含彼此相同的键数。

Postgres索引是什么样的？

雷曼（Lehman）和姚明（Yao）绘制了这张图表，距今已有30年之久–它与Postgres今天的工作方式有什么关系？ 令人惊讶的是，我们先前创建的index_users_on_name索引与图2非常相似：我们在2014年创建了一个索引，该索引看起来就像是1981年的图表！

当我们执行CREATE INDEX命令时，Postgres将用户表中的所有名称保存到B树中。 这些成为树的钥匙。 这是Postgres B树索引内的节点的样子：

索引中的每个条目都包含一个称为IndexTupleData的C结构，后跟一个位图和一个值。 Postgres使用位图记录键中的任何索引属性是否为NULL，以节省空间。 索引中的实际值出现在位图之后。

让我们仔细看一下IndexTupleData结构：

在上方可以看到每个IndexTupleData结构包含：

• t_tid ：这是指向另一个索引元组或数据库记录的指针。 注意，这不是指向物理内存的C指针。 相反，它包含数字Postgres可以用来在其内存页面中查找引用的值。
• t_info ：这包含有关索引元组的信息，例如它包含多少个值以及是否有空值。

为了更好地理解这一点，让我们从index_users_on_name索引中显示一些条目：

现在，我用用户表中的一些名称替换了“值”。 上层树节点包含键“ Dr. Edna Kunde”和“ Julius Powlowski”，而较低的树节点包含“ Julius Powlowski”和“ Juston Quitzon”。

请注意，与Lehman和Yao的图不同，Postgres在每个子节点中重复父键。 “ Julius Powlowski”是上层节点和子节点中的键。 来自较高节点中的Julius的t_tid指针在较低节点中引用了相同的Julius名称。

要详细了解Postgres如何将键值存储到B-Tree节点中，请参阅itup.h C头文件：

寻找包含尼莫船长的B树节点

现在，让我们再次返回原始的SELECT语句：

Postgres如何在我们的index_users_on_name索引中搜索“尼莫船长”？ 为什么使用索引比我们在上一篇文章中看到的序列扫描更快？ 为了找出答案，让我们缩小一点，看看索引中的一些用户名：

这是index_users_on_name B树的根节点 。 我把树转向侧面，这样名称就合适了。 您可以看到4个名称和一个NULL值。 当我创建index_users_on_name时，Postgres创建了这个根节点。

请注意，除了第一个NULL值（代表索引的开头）之外，其他4个名称或多或少都按字母顺序均匀分布。

请记住，B树是平衡树。 在此示例中，B树具有5个子节点：

• 按字母顺序出现在Edna Kunde博士之前的名字
• 出现在Edna Kunde博士和Julius Powlowski之间的名字
• 朱利叶斯·波洛夫斯基（Julius Powlowski）和蒙特·尼古拉斯（Monte Nicolas）之间出现的名字
• 等等…

因为我们正在搜索Nemo上尉，所以Postgres跟随右边的第一个顶部箭头。 这是因为尼莫船长按字母顺序排在爱德娜·昆德博士之前：

您可以在右侧看到Postgres已找到包含Nemo上尉的B树节点。 为了测试，我在users表中添加了1000个名称。 B树中的这个子节点包含大约200个名称（实际上是240个）。 B树大大缩小了Postgres的搜索范围。

要了解有关Postgres用于在树中所有节点中搜索目标B-Tree节点的精确算法的更多信息，请阅读_bt_search函数。

在单个B树节点中查找Nemo船长

现在，Postgres将搜索范围缩小到包含大约200个名称的B-Tree节点，它仍然必须找到Nemo上尉……它是如何做到的？ 它会在这个较短的列表上执行序列扫描吗？

否。要在树节点内部搜索键值，Postgres切换为使用二进制搜索算法。 首先，将树节点中50％位置上显示的键与“船长尼莫：”进行比较。

由于Nemo队长是在Breana Witting之后按字母顺序排列的，因此Postgres跳到75％的位置并执行另一个比较：

这次Nemo队长出现在Curtis Wolf之前，因此Postgres跳回了一点。 跳过了几步（在我的示例中，实际上花了Postgres 8比较才能找到Nemo上尉），Postgres最终找到了我们想要的东西：

要详细了解Postgres如何在单个B-Tree节点中搜索值，请阅读_bt_binsrch函数 ：

有更多的东西要学习

我在这篇博文中没有足够的空间来介绍有关B树，数据库索引或Postgres内部结构的许多其他令人着迷的细节……也许我应该在显微镜下写Postgres 。 但是目前，这里只有一些有趣的理论，您可以在B树上的并发操作的有效锁定或它引用的其他学术论文中阅读。

• 插入B树： B树算法最漂亮的部分与将新**插入树有关。 将**按排序顺序插入适当的树节点中-但是，当没有更多空间容纳新**时会发生什么？ 在这种情况下，Postgres将节点拆分为两个，将新**插入其中一个，然后还将拆分点中的**与指向新子节点的指针一起添加到父节点。 当然，可能还必须拆分父节点以适应其新**，从而导致复杂的递归操作。
• 从B树中删除：逆操作也很有趣。 从节点删除**时，Postgres会在可能的情况下将同级节点组合在一起，并从其父级中删除**。 这也可以是递归操作。
• B-Link-Trees：雷曼和姚的论文实际上讨论了他们研究的与多个线程使用同一B-Tree时的并发和锁定相关的创新。 记住，Postgres的代码和算法需要多线程，因为许多客户端可能同时搜索或修改相同的索引。 通过从每个B-Tree节点向另一个下一个兄弟节点添加另一个指针（即所谓的“右箭头”），即使第二个线程在不锁定整个索引的情况下拆分节点，一个线程也可以搜索树：

不要害怕在表面之下探索

Aronnax教授冒着生命危险和职业生涯寻找难以捉摸的鹦鹉螺，并与Nemo船长一起进行了一系列令人惊叹的水下冒险。

我们应该做同样的事情：不要害怕在水下潜水-每天使用的工具，语言和技术的内部和下方。 您可能知道如何使用Postgres，但是您真的知道Postgres本身在内部如何工作吗？

看看里面； 在不知不觉中，您将自己进行水下冒险。

在我们的应用程序的幕后工作时学习计算机科学不仅是获得乐趣的问题，而且是成为优秀开发人员的一部分。

随着软件开发工具的逐年改进，以及构建网站和移动应用程序变得越来越容易，我们不应忽视我们所依赖的计算机科学。 我们都站在巨人的肩膀上，像雷曼兄弟（Lehman）和姚明（Yao）这样的人，以及使用他们的理论构建Postgres的开源开发人员。

不要将您每天使用的工具视为理所当然-深入了解它们！ 您将成为一个更明智的开发人员，并且会发现以前无法想象的见识和知识。

通过@pat_shaughnessy“发现Postgres索引背后的计算机科学”

点击鸣叫

翻译自: https://www.javacodegeeks.com/2015/06/discovering-the-computer-science-behind-postgres-indexes.html