B-tree（PostgreSQL 14 Internals翻译版）

本文主要是介绍B-tree（PostgreSQL 14 Internals翻译版），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

概览

B树(作为B树访问方法实现)是一种数据结构，它使您能够通过从树的根向下查找树的叶节点中所需的元素。为了明确地标识搜索路径，必须对所有树元素进行排序。B树是为有序数据类型设计的，这些数据类型的值可以进行比较和排序。

下面的机场代码索引构建示意图将内部节点显示为水平矩形；叶节点垂直排列。

在这里插入图片描述
每个树节点包含几个元素，这些元素由一个索引键和一个指针组成。内部节点元素是下一层的引用节点；叶节点元素引用堆元组(图中没有显示这些引用)。

B树具有以下重要属性：

它们是平衡的，这意味着树的所有叶节点都位于相同的深度。因此，它们保证所有值的搜索时间相等。
它们有大量的分支，也就是说，每个节点包含许多元素，通常有数百个元素(为了清晰起见，该图仅显示了三个元素节点)。因此，B树深度总是很小，即使对于非常大的表也是如此。
索引中的数据在每个节点内以及在同一级别的所有节点上按升序或降序排序。对等节点被绑定到一个双向列表中，因此可以通过简单地以一种或另一种方式扫描列表来获得有序的数据集，而不必每次都从根开始。

搜索与插入

等值搜索

让我们看一下如何根据条件“索引-列=表达式”在树中搜索值。我们将尽力找到KJA机场。

搜索从根节点开始，访问方法必须确定要下降到哪个子节点。它选择K i键，满足K i≤表达式< K i+1。

根节点包含键AER和OVB。条件AER < KJA<OVB成立，因此我们需要下降到具有AER键的元素所引用的子节点。

在这里插入图片描述

这个过程递归地重复，直到我们到达包含所需元组ID的叶节点。在这种特殊情况下，子节点满足条件DME≤KJA < KZN，因此我们必须下降到具有DME键的元素所引用的叶节点。

您可以注意到，树的内部节点中最左边的键是冗余的:要选择根的子节点，只要满足条件KJA < OVB就足够了。B树不存储这样的键，所以在下面的插图中，我将保留相应的元素为空。

叶节点中需要的元素可以通过二分查找快速找到。

然而，搜索过程并不像看起来那么简单。必须考虑到，索引中数据的排序顺序可以是升序(如上所示)，也可以是降序。即使是唯一的索引也可以有几个匹配的值，并且必须返回所有这些值。此外，可能有太多的副本，以至于它们不适合单个节点，因此相邻的叶节点也必须处理。

最重要的是，当搜索正在进行时，其他进程可能会修改数据，页面可能被分成两个，树结构可能会发生变化。所有的算法都被设计为尽可能减少这些并发操作之间的争用，并避免过多的锁，但是我们在这里不打算讨论这些技术细节。

不等值搜索

如果搜索是通过条件“索引-列 ⩽expression”(或“索引-列⩾expression”)执行的，我们必须首先搜索满足相等条件的值的索引，然后在所需的方向遍历其叶节点，直到到达树的末端。

该图说明了搜索小于或等于DME的机场代码。

在这里插入图片描述
对于小于和大于操作符，过程相同，只是必须排除第一个找到的值。

范围搜索

当按照“表达式1≤索引列≤表达式2”的范围进行搜索时，我们必须先找到表达式1，然后沿着正确的方向遍历叶节点，直到找到表达式2。该图说明了在LED和ROV之间的范围内搜索机场代码的过程。

在这里插入图片描述

插入

新元素的插入位置由键的顺序明确定义。例如，如果将RTW机场代码插入到表中，则新元素将出现在ROV和SGC之间的最后一个叶节点中。

但是如果叶节点没有足够的空间容纳新元素怎么办?例如(假设一个节点最多可以容纳三个元素)，如果我们插入TJM机场代码，最后一个叶节点将被过度填充。在这种情况下，节点被分成两个，旧节点的一些元素被移动到新节点中，指向新子节点的指针被添加到父节点中。显然，父节点也可能会被填满。然后它也被分成两个节点，以此类推。如果要拆分根，则在生成的节点之上再创建一个节点，以成为树的新根。在这种情况下，树的深度增加了一级。

在本例中，TJM机场的插入导致两个节点分裂;生成的新节点在下面的图中突出显示。为了确保可以拆分任何节点，双向列表绑定了所有级别的节点，而不仅仅是最低级别的节点。

在这里插入图片描述