用于索引的树数据结构的演变：听起来不止于此
我必须承认，我的研究博客帖子越来越长。从一方面来看，我发现这确实令人鼓舞，因为如果只是从头开始就获得大量信息，请想象一下隐藏在表面下的东西！一位大学教授曾经说过：“数据库中可能有什么有趣的东西？”，事实证明吓坏了很多！另一方面，它肯定会给潜在读者带来问题。为了克服它们，我建议一种有趣的方法：打印此博客文章，或在平板电脑/电子阅读器上打开它，在这里您可以用铅笔或记号笔做笔记。现在，在阅读的同时，尝试发现一些特别让您兴奋的想法并加以标记。一路上肯定会出现一些晦涩的部分或问题，也要在侧面写上。您可以尝试使用这些图，更改或扩展它们，或者只是绘制有趣的面孔。但是不要一次阅读所有内容，不要担心将其搁置一会儿，并阅读一些对您方便的块。由于文本是由相对独立的主题构成的，因此可能会跳过某些部分。目录可以帮助和指导您。话虽如此，我们已经准备好踏上旅途。
每当我们谈论索引时，尤其是在PostgreSQL上下文中，都有很多要谈论的话题：B树，哈希，GiST，SP-GiST，GIN，BRIN，RUM。但是，如果Itell告诉您，即使仅此列表中的第一项，也隐藏了令人惊讶的大量有趣细节和多年研究成果，该怎么办？在这篇博客中，我将尝试证明这一说法，我们将主要关注B树作为数据结构。
B树是一种自平衡树数据结构，用于维护排序的数据，并允许在对数时间进行搜索，顺序访问，插入和删除。
您与B树的第一个关联是什么？矿山是“古老而精心研究的，换句话说就是无聊的”。实际上，它显然是在1970年首次推出的！不仅如此，它们已经在1979年无处不在。这是否意味着不再有激动人心的事情了？曾几何时，我遇到了一篇非凡的读物，称为《现代B树技术》，这启发了我深入研究该主题并阅读了一堆闪亮的新白皮书。之后，偶然地我偶然发现了一本书“数据库内部知识：深入研究分布式数据系统的工作原理”，其中包含有关B树设计的重要部分。这两本书都是写这篇博客文章的诱因。我说什么都没剩下什么令人兴奋的东西？最后，我再没错。
事实证明，围绕B树有许多有趣的想法和技术。它们全都来自满足不同（通常兼容）的需求以及适应新兴硬件的渴望。为了演示其中存在的数量，让我们玩一个游戏。您可以在下面找到一张表格，这些表格是我在各种科学论文中找到的名称，以及几个我自己想出来的愚蠢名称。你能找出假的吗？
有任何想法吗？好吧，我有一个表白-他们都是真实的，我只是没有足够的想象力想出这样的名字。考虑到这一点，您将理解，如果我们要进行调查，第一步就是建立一些分类。这不仅将帮助我们构造材料，而且还将解释为什么地球上任何人都需要发明许多我们如此简单的变体！
为了对不同的索引访问方法进行分类，我们需要考虑以下雄心勃勃的问题–几乎任何索引访问方法之间是否存在共同点？ RUM猜想的作者对这个主题提供了有趣的见解：
每个研究人员，系统架构师或设计人员在设计新的访问方法时都面临的基本挑战是如何最大程度地减少以下各项：i）读取时间，ii）更新成本，以及iii）内存（或存储）开销。
在本文中，我们推测，当优化读取更新内存开销时，在任何两个区域进行优化都会对第三个区域产生负面影响
这实质上表明，如果可以在“读取”，“更新”（在图1中将其称为“写入”，以方便绘图），“内存”空间中指定一个索引访问方法，则可以观察到一个有趣的不变性。每次我们修改一种索引访问方法以减少读取或占用内存的开销（即，将相应的点移到“读取” /“内存”的角落更近）时，我们不可避免地会松懈更新工作量（即远离“写入”角）。
实际上，作为一个非科学家，我什至会推测应该有另一个维度称为“复杂性”，但是这个想法仍然很明确。我将尝试通过此博客文章中的示例来展示此不变式，但它已经为脚下提供了有用的基础，并提供了通过在三角形上来回移动点来直观表示B树的不同版本的机会。但是，Firstlet回忆起了基础知识。
那么什么是B树？嗯，这是一个树数据结构：一个根节点，一些分支节点（标记为灰色）和一堆叶子节点（标记为绿色）：
该树的每个节点通常是一定大小的页面，并包含键（节点的阴影切片）和指向其他节点的指针（带箭头的空切片）。页面上的键按排序顺序保留，以便于快速搜索页面。
原始的B树设计假定在所有节点（分支和叶子）中都有用户数据。但是如今，标准方法是一种称为B + -tree的变体，其中用户数据仅存在于叶节点中，而分支节点包含分隔符（PostgreSQL术语中的枢轴元组）。这样，分支和离开节点之间的分离变得更加严格，从而为选择前者的格式和进行删除操作提供了更好的灵活性，从而仅影响后者。实际上，这些天来原始的B树设计几乎不值得一提，而我正在做的就是这样。由于B +树是默认设计，因此从现在开始我们将在本文中交替使用B树和B +树。这里要提到的一个有趣的事情是，对分隔符的唯一要求是将搜索算法引导到正确的叶节点。只要它们满足此条件，它们就可以包含任何东西，不存在其他要求。
严格来说，在此设计中仅真正需要子指针，但是很多时候数据库还维护其他的邻居指针，例如：您可以在图2中叶节点之间看到。对于某些操作（例如索引扫描）可能会有所帮助，但是节点拆分/合并操作需要考虑在内。 PostgreSQL使用雷曼-姚（Lehman-Yao）版本，称为B链接树，同时具有到左右同级节点的链接（在原始B链接树设计中实际上没有显示左链接，这使得向后扫描有点有趣），并且在那里甚至是带有父指针的WiredTiger之类的实现。
将所有这些都放在适当的位置，就可以执行搜索查询，方法是遵循图2上标记为红色的路径，首先击中根节点，找到合适的分隔符，然后沿着下行链路连接并到达正确的页面，在该页面上我们部署Binarysearch以查找结果键。
到目前为止，我们仅谈论B树设计的静态部分，但是当然还有更多内容。例如，有一个非常重要的动态方面（很多时候它甚至像噩梦一样使开发人员感到恐惧），即页面拆分。当要插入新值但目标页面没有足够的空间时，如下图所示，我们该怎么办？
此处发生的是，我们正在尝试将新值（阴影框）插入页面，而没有足够的空间。为了保持这三个平衡，我们需要分配另一个叶子页，在旧叶子和新叶子之间分配密钥，在父页面中升级一个新的分隔符，并更新所有必需的链接（如果存在，则为left / right兄弟姐妹）：
奇怪的是，可以自由选择新的分隔键，只要分隔两个页面，它就可以是任何值。我们可以在优化部分看到它的变化。
锁定显然是页面拆分的重要部分。没有人希望在拆分过程中更新页面时遇到并发问题，因此要拆分的页面被写锁定，例如如果存在，则向右兄弟更新updateleft-link。
如您所见，页面拆分带来了性能开销。我们需要进入一个新页面，四处移动元素，所有内容都应保持一致并正确锁定。在这个非常基本的点上，我们已经可以看到一些有趣的权衡。例如，B * -tree修改尝试在相邻节点之间重新平衡数据，以尽可能长时间地推迟页面拆分。在权衡方面，它看起来像是复杂性和插入开销之间的平衡。
我没有告诉您有关B链接树的所有信息，这将是本节中的下一个主题示例。雷曼-姚（Lehman-Yao）版本不仅添加了到邻居的链接，而且还在每个页面上引入了“高键”，这是页面上允许使用的键的上限。虽然显然会引入一点内存开销，但是这两个更改使得可以通过检查页面高键来检测并发页面拆分，这使得无需保留任何读取锁即可进行搜索树（除了防止在读取单个页面时对其进行修改）[6 ]。我们可以将其视为内存占用和插入开销之间的平衡。
我们花了很多时间讨论页面拆分及其重要性。为了保持对称，可以从页面合并中获得相同的效果，但令人惊讶的是通常情况并非如此。甚至有论文指出：
通过添加树的定期重建，我们可以在许多方面获得理论上优于标准B树的数据结构。我们的结果表明，在删除上进行重新平衡不仅不必要，而且可能有害。
但是，当然，PostgreSQL中的真空仍然可以回收空页面（请参见[6]中的“ PageDeletion”）。
现在只是为了品尝真实的B树，我们在PostgreSQL中生成一个索引并将其可视化。最简单的方法可能是使用pgbench创建一个小的数据集，然后使用pg_query_internals中的脚本绘制B树节点和连接的结果图，结果如图4所示：
您感到困惑，这条坎bump线是什么？好吧，这是我尝试使可视化效果适合屏幕的原因，因为实际上B树非常宽。现在，让我们玩点儿，修改可视化效果脚本，将每个节点显示为一个小点，并对graphviz使用“ neato”布局：
图5很好地展示了B树的另一种观察结果，它们确实非常宽，短，甚至丛生。同样的情况也可以帮助我们理解B树的另一个重要方面，使其在数据库系统中无处不在。原因是，使用B树，可以以合理的效率处理多种工作负载，而在设计时就不会只考虑一个目标。那怎么可能？在“现代B树技术”中，尤其是在“ B树与哈希索引”部分中已对此进行了详细说明，因此，我将仅对摘要进行表述。
首先，B树可以有效地利用内存层次结构，因为您可以看到它非常宽，并且如果索引为“ warm”，则意味着最有可能的所有分支节点都将出现在缓冲池中，或者在准备时可以被提取到缓冲池中查询。对于叶子页，也可以部署有效的驱逐策略，以解决不均匀的工作负载。在一般情况下，B树中的空间管理非常简单，索引可以平滑增长或收缩，而优雅增长或收缩例如哈希索引尚未得到解决。
B树的另一个有助于解决不同工作负载的属性是仅使用一个索引即可支持不同形式的查询（使用索引键前缀的搜索或索引跳过扫描）的能力。
最后但并非最不重要的一点是B树在优化方面的灵活性。一个人可以在不同级别上进行不同的优化，以便能够在大多数情况下解决特定类型的工作负载而不会对性能产生负面影响。
说完所有这些，我们还可以查明在RUM空间中可以放置B树的位置。由于它在读取工作负载方面相当不错，但在内存占用和插入工作负载方面可能会更好，因此我们可以将其放在此处：
正如我们已经提到的，B树在数据库领域如此普遍的原因之一是它们的灵活性和可扩展性。 On可以应用各种不同的局部优化，这些局部优化可以很好地组合而无需牺牲其他内容。让我们来看看其中一些。
可能最简单的方法是密钥规范化，这显然是古老的技术[3]。这个想法很简单，如果有一个索引记录，每一列都有几个键，我们将它们转换成如图7所示的二进制字符串：
这允许在索引创建期间或在引导搜索到正确的记录时使用简单的二进制比较对记录进行排序。这样的编码值需要注意空值和归类，甚至可以包括排序方向。但是一如既往地有利弊，在这种特殊情况下，窍门是，一般而言，不可能收回原始数据。在某些情况下，甚至可能会发生两个不同的值生成相同的规范化键的情况（例如，对于大小写区分大小写的大小写不区分大小写的语言）。这意味着我们要么：
需要同时保留原始数据和规范化密钥，或者以其他方式确保精确恢复是可能的。
就其本身而言，这种修改看起来是无害的，但实际上，它使我们能够在其之上实现更多优化。
借助前缀密钥截断可以更容易地实现此类优化之一。您会惊奇地发现它是如此直接。假设我们在一页上有以下键：
请注意，我们存储的值以相同的前缀开头，这是一种重复数据。如果我们要进行一些簿记，则可以仅将此前缀存储一次，然后从所有键中截断该前缀。
可以想象，这种优化是在消耗较少的休假页面空间与在运行时完成更多工作之间进行权衡。为了减少代码复杂性和运行时开销，尽管更细粒度的方法可以提供更好的压缩率（以及更多），但通常通常根据围栏键（在隔离期间将隔离键的副本发布到父级）在整个可能的键范围内进行前缀截断。插入操作时头痛）。
即使没有直接实现前缀截断并且不更改B树页面格式，也可以基于有关共享前缀和篱笆密钥的知识，使用动态前缀截断来减少比较成本。按照图9的示意图，如果我们要添加一个新键（一个出色的项目），并且页面上的fencekey具有共同的前缀（标记为红色部分），则意味着所有的键都已被剃除，因此可以从比较中省略（留给我们）仅对蓝色部分进行折磨）：
您可能还会在排序算法的上下文中以通用前缀skippingname知道这种方法。不幸的是，术语不一致现象相对频繁发生，因为您可以在整篇博客文章中注意到（另一个有趣的例子是B * -tree，在普遍的B-tree中被称为“ B-tree文学中最被滥用的术语”）。
尽管名称相似，但后缀截断还是有些不同。此技巧可以应用于分支页上的分隔键，最简单的解释方法是显示该图。假设我们有一个要拆分的页面：
如果此页面在中间被分割，我们将以键“ Miller Mary”结尾，并且为了完全区分分割的部分，最小的分隔键应为“ Miller M”。但是，如上所述，我们实际上可以选择任何可用的分隔键，只要它可以分隔两个页面，那么为什么不像下面的示例那样使用较短的分隔键呢？
这几乎就是整个想法，以这样一种方式来获取分割点，使得最终的分离键将最小。
值得一提的是，从版本12开始，PostgreSQL会进行整列后缀截断而不实际实现密钥规范化。相应的Wiki页面上对所有这些技术都有很好的概述。
通常，我们必须处理可变长度的值，处理它们的常规方法是在每个页面上都有一个间接指向向量，并带有指向实际值的指针。在PostgreSQL术语中，那些指针称为行指针。每当我们有一个要比较的键时，我们首先跟随一个指针并获取它指向的值。但是，如果我们扩大该设计范围并为每个此类指针配备一些有用的信息，例如在跟随指针之后将要找到的标准化密钥的前几个字节，如图12所示，该怎么办（例如，第一个字符a ，b，c，d）？
如此小的更改使我们能够确定在此指针之后是否找不到所需的值，因为前几个字节已经不同。这使设计对CPU缓存更友好，因为间接向量通常足够小以适合缓存。有关更多详细信息，请参见[9]。
我发现另一种有趣的方法是溢出页，当页中实际上只直接存储了一定数量的有效载荷字节，其余部分直接进入溢出页时。很少有MySQL InnoDB和SQLite的例子。
页面拆分在B树设计中很重要，显然可以在野外找到如何处理它们的有趣变化。 SB树就是这样一个示例，其中为提高页面拆分效率而在许多页面的较大连续范围内分配了磁盘空间。这在每个范围内都留下了空闲页面，并且每当需要拆分一个节点时，都会在同一节点内“分配”另一个节点。从已经预分配的空间开始扩展，如图13中的下图所示：
当然，这意味着扩展区本身可以达到没有可用空间的程度，因此需要按照与正常页面拆分相同的思路进行拆分。您可能会对SB-tree在此处的“基本操作”感到惊讶，因为这不是标准方法。是的，这不是基本知识，但我还是决定在此提起它，主要是因为它几乎是直觉的。
确实，一切看起来都很不错，为什么我们需要提出其他一些设计？嗯，您可以在RUM空间中记住B树，使其更靠近“读取”角，并非没有原因。 B树设计有几个常见的缺点：
由于采用了指针追踪，因此对CPU缓存的友好程度不是特别高，因为要执行一项操作，我们需要遵循许多指针。
内存占用量和插入性能位于平衡的不同方面，我们可以通过预分配页面来改进插入，并跟踪需要更多内存的页面上的可用空间。这对于数据压缩同样有效。
B树需要页面级的锁耦合来同步访问，这在多核CPU或内存系统中无法很好地扩展（请参见[10]，[11]）。
批量插入也不是特别有效，开箱即用的索引维护可能非常棘手（我最喜欢的部分描述是论文“索引创建后的痛苦之波”）。
同时，有些替代数据结构提供相似的功能，但权衡取舍不同。所有这些使主题变得非常动态，并且充满了有趣的想法。在以下各节中，我将尝试描述一些我认为有趣的设计。睁大眼睛，您可能会注意到许多常见的模式。
如果可以将SB树称为直观树，那么分区B树的想法一开始听起来很混乱。本质上，建议是通过添加人工的前导关键字段来维护具有单个B树的分区（请参见[14]）。这些分区不过是临时分区，一段时间后将在后台合并在一起，因此在正常状态下只有一个分区。我们到底为什么要添加
......
