用于索引的树数据结构的演变：比听起来更重要

我不得不承认，我的研究博客文章越来越长。从一方面来说，我觉得这真的很令人鼓舞，因为如果仅仅通过抓住主题就可以获得如此多的信息，想象一下隐藏在表面之下的东西！一位大学教授曾经说过“数据库中有什么有趣的东西？”，结果令人毛骨悚然！另一方面，它肯定会给潜在读者带来问题。为了克服它们，我建议采用一种有趣的方法：将这篇博文打印出来，或者在您的平板电脑/电子阅读器上打开它，您可以在其中用铅笔或记号笔做笔记。现在，在阅读它时，试着找出对你来说特别令人兴奋的想法并标记它们。一路上肯定会有一些晦涩难懂的部分或问题，也可以写在旁边。您可以尝试图表，更改或扩展它们，或者只是绘制有趣的面孔。但不要一口气读完，不要害怕搁置一会，自己方便的分块读。部分内容可以略过，因为文章是由相对独立的主题构成的。目录可以帮助和指导您。说完我们就准备踏上旅程了。每当我们谈论索引时，尤其是在 PostgreSQL 上下文中，我们都会谈论很多：B-tree、Hash、GiST、SP-GiST、GIN、BRIN、RUM。但是，如果它告诉您，即使仅此列表中的第一项就隐藏了惊人数量的有趣细节和多年的研究呢？在这篇博文中，我将尝试证明这一说法，我们将主要关注 B 树作为一种数据结构。 B-tree 是一种自平衡树数据结构，它维护已排序的数据，并允许在对数时间内进行搜索、顺序访问、插入和删除。您与 B 树概念的第一个关联是什么？我的是“古老而深入的研究，或者换句话说很无聊”。事实上，它显然是在 1970 年首次推出的！不仅如此，早在 1979 年，它们就已经无处不在。这是否意味着没有什么令人兴奋的了？曾几何时，我读到了一篇名为现代 B 树技术的非凡读物，这激发了我深入研究该主题并阅读了大量闪亮的新白皮书。后来我偶然偶然发现了一本书“数据库内部：深入研究分布式数据系统如何工作”，其中包含有关 B 树设计的重要部分。这两部作品都是写这篇博文的契机。 Isaying 没有什么令人兴奋的东西了？最后我错得不能再错了。事实证明，围绕 B 树有许多有趣的想法和技术。它们都来自满足不同（通常不兼容）需求以及适应新兴硬件的愿望。为了演示其中存在多少，让我们玩一个游戏。你可以在下面找到一张我在各种科学论文中找到的名字的表格，以及我自己想出来的几个愚蠢的名字。你能找出假货吗？有任何想法吗？好吧，我必须承认——所有这些都是真实的，我只是没有足够的想象力来想出这样的名字。记住这一点，希望您明白，如果我们要进行调查，第一步将是建立一些分类。这不仅将帮助我们构建材料，而且还将解释为什么地球上的任何人都需要发明我们认为如此简单的许多变体！为了对不同的索引访问方法进行分类，我们需要考虑以下这个雄心勃勃的问题——几乎所有的索引访问方法之间有什么共同点吗？ RUM 猜想的作者提供了有关此主题的有趣见解：

每个研究人员、系统架构师或设计人员在设计新访问方法时面临的基本挑战是如何最小化 i) 读取时间、ii) 更新成本和 iii) 内存（或存储）开销。在本文中，我们推测在优化 read-update-memoryoverheads 时，在任何两个方面的优化都会对第三个方面产生负面影响。这实质上是说，如果可以将索引访问方法指定为“Read”、“Update”（在图 1 为方便绘图而称为“Write”），“Memory”空间我们可以观察到一个有趣的不变量。每次我们修改一种索引访问方法以减少读取或内存占用的开销（即将对应点移近“读取”/“内存”角），我们不可避免地会减少更新工作量（即远离“写入”角） ）。事实上，作为一个非科学家，我什至推测应该有另一个维度叫做“复杂性”，但这个想法仍然很清楚。我将尝试通过这篇博文中的示例展示这个不变量在工作中，但它已经为我们提供了一些基础，并有机会通过来回移动三角形上的点来直观地表示 B 树的不同版本。但首先让我们回忆一下基础知识。那么什么是B树呢？嗯，它是一个树数据结构：一个根节点，一些分支节点（标记为灰色）和一堆叶节点（标记为绿色）：这棵树的每个节点通常是一个特定大小的页面并包含键（阴影部分一个节点）和指向其他节点的指针（带箭头的空切片）。页面上的键按排序顺序保存，以方便在页面内快速搜索。最初的 B 树设计假设在所有节点、分支和叶中都有用户数据。但是现在标准方法是一种称为 B+-tree 的变体，其中用户数据仅存在于叶节点中，而分支节点包含分隔键（PostgreSQL 术语中的枢轴元组）。这样分支和离开节点之间的分离变得更加严格，允许更好的灵活性选择前者的格式并使删除操作只影响后者。事实上，现在最初的 B 树设计几乎不值得一提，我这样做只是为了准确。由于 B+-tree 是一种默认设计，所以从现在开始，我们将在本文中交替使用 B-tree 和 B+-tree。这里要提到的一个有趣的事情是，对分隔键的唯一要求是将搜索算法引导到正确的叶节点。只要它们满足这个条件，它们就可以包含任何东西，不存在其他要求。

严格地说，在这种设计中，只有子指针才是真正需要的，但通常数据库还维护额外的邻居指针，例如您可以在图 2 中的叶节点之间看到的内容。它可能对索引扫描等某些操作有帮助，但需要考虑节点拆分/合并操作。 PostgreSQL 使用 Lehman-Yao 版本，称为 B 链接树，链接到左右兄弟节点（左链接在原来的 B 链接树设计中实际上没有出现，它使反向扫描有点有趣），并且有甚至是像 WiredTiger 这样带有父指针的实现。有了所有这些，我们就可以按照图 2 中标记为红色的路径执行搜索查询，首先点击根，找到一个合适的分隔符，跟随一个下行链接并登陆正确的页面，在那里我们部署二进制搜索以找到结果键.到目前为止，我们只讨论 B 树设计的静态部分，但当然还有更多。例如，有一个非常重要的动态方面（通常它甚至像噩梦一样让开发人员感到害怕），即页面拆分。当有新值要插入，但目标页面没有足够的空间（如下图所示）时，我们需要做什么？这里发生的事情是我们试图将新值（阴影框）插入到没有足够空间的页面中。为了保持三者平衡，我们需要分配另一个叶子页面，在新旧叶子之间分配键，将新的分隔键提升到父页面并更新所有必需的链接（左/右兄弟姐妹，如果存在）：奇怪的是，新的分隔键可能是自由选择，它可以是任何值，只要将两个页面分开即可。我们可以在优化部分看到它有什么变化。锁定显然是页面拆分的重要部分。当页面在拆分过程中被更新时，没有人希望以并发问题告终，因此要拆分的页面是写锁定的，例如，如果存在 updateleft-link 的右兄弟。如您所见，页面拆分引入了性能开销。我们需要引入一个新页面，四处移动元素，一切都应该保持一致并正确锁定。在这个非常基本的点上，我们已经可以看到一些有趣的权衡。例如，B*-tree 修改尝试重新平衡相邻节点之间的数据，以尽可能长时间地推迟页面拆分。在权衡方面，它看起来像是复杂性和插入开销之间的平衡。

我没有告诉您有关 B 链接树的所有内容，它将成为本节中的下一个主题示例。雷曼-姚版不仅增加了邻居的链接，还为每个页面引入了一个“高键”，这是页面允许的键的上限。虽然显然引入了一点内存开销，但这两个更改使得可以通过检查页面高键来检测并发页面拆分，这允许在不持有任何读锁的情况下搜索树（除了防止单个页面在读取时被修改）[6] ]。我们可以将其视为内存占用和插入开销之间的平衡。我们花了很多时间讨论页面拆分及其重要性。出于对称的考虑，人们可以期待页面合并也有同样的效果，但令人惊讶的是，通常情况并非如此。甚至有论文指出：通过添加树的周期性重建，我们获得了一种在许多方面理论上优于标准 B 树的数据结构。我们的结果表明，删除时重新平衡不仅不必要，而且可能有害。但是当然 PostgreSQL 中的vacuum 仍然可以回收空页（参见[6] 中的“PageDeletion”）。现在只是为了体验真正的 B 树，让我们在 PostgreSQL 中生成一个索引并将其可视化。最简单的方法可能是使用 pgbench 创建一个小数据集，然后使用 pg_query_internals 中的脚本绘制 B 树节点和连接的结果图，您可以在图 4 上看到结果：您是否感到困惑，这条颠簸的线是什么？好吧，这是我尝试将可视化放入屏幕，因为实际上 B 树非常宽。现在让我们玩一下并修改可视化脚本，将每个节点显示为一个小点，并使用“neato”布局来进行 graphviz：图 5 . 很好地展示了对 B 树的另一种观察，它们确实非常宽、非常短，甚至有点浓密。同样的图片也可以帮助我们理解 B 树的另一个重要方面，它确实在数据库系统中无处不在。原因是 B-tree 可以以合理的效率处理多种工作负载，而不是在设计时只考虑一个目标。这怎么可能？在“现代 B 树技术”中，特别是在“B 树与哈希索引”部分中进行了彻底的解释，因此我将仅制定摘要。

一方面，B-tree 可以有效地利用内存层次结构，因为正如你所看到的，它非常宽，如果一个索引是“温暖的”，这意味着很可能所有分支节点都将出现在缓冲池中，或者在准备时可以被提取到缓冲池中查询。对于叶页面，也可以部署有效的驱逐策略来解决非统一的工作负载。一般来说，B 树中的空间管理相当简单，索引可以平滑地增长或收缩，而优雅的增长或收缩（例如哈希索引）尚未完全解决。 B-tree 有助于解决不同工作负载的另一个特性是它能够仅使用一个索引来支持不同形式的查询（使用索引键的前缀进行搜索，或索引跳过扫描）。最后但并非最不重要的是 B 树在优化方面的灵活性。可以在不同级别组合不同的优化，以便能够解决某些特定类型的工作负载，而不会在其他情况下对性能产生负面影响。说了这么多，我们还可以确定我们可以在 RUM 空间中放置 B 树的位置。由于它在读取工作负载方面相当不错，但在内存占用和插入工作负载方面可能更好，我们可以把它放在这里：正如我们已经提到的，B 树在数据库世界中如此普遍的原因之一是它们的灵活性和可扩展性。 On 可以应用各种不同的局部优化，这些优化可以很好地组合而不会牺牲其他东西。让我们来看看其中的一些。可能我们能做的最简单的就是密钥归一化，这显然是一种非常古老的技术 [3]。这个想法很简单，如果每个列都有一个带有多个键的索引记录，我们将它们转换成一个二进制字符串，如图 7 所示：这允许使用简单的二进制比较在索引创建期间或引导搜索到正确记录。这样的编码值需要处理空值和排序规则，甚至可以包括排序方向。但是一如既往地有利有弊，在这种特殊情况下，诀窍是一般来说不可能回收原始数据。在某些情况下，甚至可能发生两个不同的值产生相同的规范化键（例如，对于具有小写/大写不区分大小写的语言）。这意味着我们要么：

需要同时保留原始数据和规范化密钥，或者以其他方式确保可以进行精确恢复。这种修改本身看起来很无害，但实际上它使我们能够在它之上实现更多优化。在标准化键的帮助下可以更容易实现的优化之一是前缀截断。你会惊讶于它是多么的直接。想象一下，我们在一页上有以下键： 请注意，我们存储的值以相同的前缀开头，这是一种数据重复。如果我们要做一些记账，可以只存储一次这个前缀并从所有键中截断它。正如您可以想象的那样，这种优化是关于在离开页面上消耗较少空间与在运行时完成更多工作之间的权衡。为了降低代码复杂性和运行时开销，通常基于栅栏键在整个可能的键范围内进行前缀截断（这些是在拆分期间发布到父级的分隔键的副本），尽管更细粒度的方法可以提供更好的压缩率（以及更多插入操作头疼）。即使不直接实现前缀截断并且不改变B-tree页面格式，也可以基于共享前缀和栅栏键的知识使用动态前缀截断来降低比较成本。如下图9所示，如果我们想添加一个新的key（一个未完成的item）并且页面上的fencekeys有共同的前缀（标记为红色部分），这意味着所有的keys都有它并且可以在比较中省略（留下我们只处理蓝色部分）：在排序算法的上下文中，您可能还知道在公共前缀 skippingname 下的这种方法。不幸的是，正如您在整篇博文中所注意到的那样，术语不一致的情况相对经常发生（另一个有趣的例子是 B*-树，它在无处不在的 B 树中称为“B 树文献中最被误用的术语”）。

尽管名称相似，但后缀截断有点不同。这个技巧可以应用于分支页面上的分隔键，解释它的最简单方法是显示图表。假设我们有一个页面要拆分：如果这个页面在中间被拆分，我们最终会得到键“Miller Mary”，为了完全区分拆分的部分，最小分隔键应该是“Miller M”。但是正如我上面提到的，我们实际上可以选择任何可用的分隔键，只要它可以分隔两个页面，那么为什么不采用以下示例中的较短的内容呢？这几乎是整个想法，以这样一种方式选择一个分裂点，使得产生的分离键将是最小的。值得一提的是，从 12 版开始，PostgreSQL 会在没有实际实现键规范化的情况下进行整列后缀截断。在相应的 wiki 页面中甚至对所有这些技术都有很好的概述。通常我们必须处理可变长度的值，处理它们的常规方法是在每个页面上都有一个间接向量，并带有指向实际值的指针。在 PostgreSQL 术语中，这些指针称为行指针。每次当我们有一个键要比较时，我们首先跟随一个指针并获取它指向的值。但是，如果我们扩展这个设计，并为每个这样的指针配备一些有用的信息，例如我们将在跟随指针之后找到的规范化密钥的前几个字节，如图 12 中的图表（例如第一个字符 a ,b,c,d)？如此小的更改使我们能够确定是否在此指针之后找不到我们正在寻找的值，因为前几个字节已经不同。这使得设计对 CPU 缓存更加友好，因为间接向量通常足够小以适应缓存。有关更多详细信息，请查看 [9]。我发现另一个有趣的方法是溢出页面，当只有固定数量的有效负载字节实际直接存储在页面中，其余的进入溢出页面时。几个例子是 MySQL InnoDB 和 SQLite。

页面拆分是 B 树设计中的一个大问题，显然在野外可以找到关于如何处理它们的有趣变化。 SB-tree 就是一个这样的例子，其中为了提高页面拆分效率，磁盘空间被分配在许多页面的大连续区中。这会在每个区中留下空闲页面，每当一个节点需要拆分时，另一个节点就会被“分配”在同一个区来自已经预分配空间的extent，如下图13：当然，这意味着当没有更多可用空间时，extent本身可以达到点，并且需要按照与正常页面拆分相同的想法进行拆分。您可能对 SB-tree 在这里所做的事情感到惊讶，在基础部分，因为它不是标准方法。是的，它不是基本的，但我决定在这里提及它，主要是因为它几乎是直观的想法。确实，一切看起来都很好，为什么我们需要想出一些其他的设计？好吧，正如您所记得的，在 RUM 空间中，我们将 B 树放在更靠近“读取”角落的地方，并非没有原因。 B 树设计有几个常见的缺点： 由于指针追逐，它对 CPU 缓存不是特别友好，因为要执行一个操作，我们需要遵循许多指针。内存占用和插入性能位于平衡的不同方面，我们可以通过预分配页面来改进插入，并跟踪需要更多内存的页面上的空闲空间。这同样适用于数据压缩。 B-tree 需要页面级的锁耦合来同步访问，这在多核 CPU 或内存系统上不能很好地扩展（参见 [10]、[11]）。批量插入开箱即用也不是特别有效，并且一般的索引维护可能非常棘手（我最喜欢对这部分的描述是论文“索引创建后的痛苦浪潮”）。

同时，还有一些替代数据结构提供了类似的功能，但有不同的权衡。这一切都让这个话题充满活力，充满了有趣的想法。在接下来的部分中，我将尝试描述一些我觉得有趣的设计。睁大眼睛，你可能会注意到许多常见的模式。如果 SB 树可以被称为直观，分区 B 树的想法起初听起来相当混乱。本质上，建议是通过添加人工前导键字段来维护单个 B 树中的分区（参见 [14]）。这些分区只是临时的，一段时间后会在后台合并在一起，这样在正常状态下只有一个分区。我们到底为什么要添加......