B-tree是怎么让查询变快的？

B-tree是一种用来搜索大量数据的结构。它是40多年前发明的，但它仍然被大多数现代数据库所使用。尽管有较新的索引结构，如LSM树，但B树在处理大多数数据库查询时仍然是无与伦比的。

下面我们来了解B-tree是如何组织数据的，以及它是如何执行搜索查询的。

一、起源

为了理解B-tree，让我们首先了解二进制搜索树（BST）Binary Search Tree。

看名字是不是看起来差不多？

那么“B”代表什么？

据wikipedia.org报道，B-tree的发明者Edward M.McCreight曾说过：

“你越想B-tree中的B是什么意思，就越能理解B-tree。”

混淆B-tree和BST是非常常见的。无论如何，在我看来，BST是理解B树的一个很好的起点。让我们从BST的一个简单示例开始：

具有三个节点的二进制搜索树

数字越大总是在右边，数字越低总是在左边。当我们增加更多的数字时，情况可能会变得更清楚。

这个树包含七个数字，我们最多需要访问三个节点就能找到任何数字。以下示例搜索14。我使用SQL来定义查询，以便将此树对应实际的数据库索引。

二、硬件
理论上，使用二进制搜索树来运行我们的查询看起来很好。其时间复杂性（搜索时）为
O（logn）
，与B-树相同。然而，在实践中，这种数据结构需要在实际硬件上工作。

一般的，索引必须存储在计算机上的某个位置。
计算机有三个地方可以存储数据：
·CPU缓存
·RAM（内存）
·磁盘（存储）
缓存完全由CPU管理。此外，它相对较小，通常只有几兆字节。索引可能包含千兆字节的数据，所以它不适合放在CPU缓存。
数据库大量使用内存（RAM）。它有一些很大的优点：
确保快速随机访问（下一段将详细介绍）
其大小可能相当大（例如，AWS RDS云服务为实例提供了几TB的可用内存）。
但是，当电源关闭时，数据会丢失。此外，与磁盘相比，它相当昂贵。

最后，内存的缺点是磁盘存储的优点。它很便宜，即使我们失去电源，数据也会留在那里。所以，看起来磁盘才是最终选择。但是读取速度是一个问题，

从磁盘读取速度很快，但只能在特定条件下进行！简单地解释一下。
（1）随机和顺序访问
存储器可以看做值的一行容器，其中每个容器都有编号。

（随机访问）现在让我们假设我们想要从容器1、4和6中读取数据。它需要随机访问：

（顺序访问）然后让我们将其与读取容器3、4和5进行比较。可以按顺序进行：

“随机跳转”和“顺序读取”之间的区别可以根据硬盘驱动器来解释。它由磁头和磁盘组成。

“随机跳跃”需要将磁头移动到磁盘上的指定位置。“顺序读取”就是简单地旋转磁盘，允许磁头读取连续的值。当读取兆字节的数据时，这两种类型的访问之间的差异是巨大的。使用“顺序读取”显著降低了获取数据所需的时间。
Adam Jacobs发表在Acm Queue上的文章《The Pathologies of Big Data》研究了随机访问和顺序访问之间的速度差异：

·HDD上的顺序访问可能比随机访问快数十万倍。
·从磁盘顺序读取可能比从存储器随机读取更快。
现在谁还会用HDD硬盘？都是SSD，这项研究表明，从HDD完全按顺序读取可能比SSD更快。然而，请注意，这篇文章来自2009年，SSD在过去十年中得到了显著发展，因此这些结果可能已经过时。
总之，关键的收获是尽可能地选择顺序访问。接下来，我将解释如何将顺序访问应用于我们的索引结构。

三、优化树以实现顺序访问

二进制搜索树可以与堆相同的方式在内存中表示：

父节点位置为i

左侧节点位置为2i

右侧节点位置为2i+1

这就是基于示例计算这些位置的方式（父节点从1开始）：

根据计算出的位置，将节点排列到内存中：

你还记得上面的可视化的查询吗？

这就是它在存储器上的样子：

当执行查询时，需要访问存储器地址1、3和6。访问三个节点不是问题；然而，当我们存储更多的数据时，树会变得更高。

存储超过一百万个值需要一棵高度至少为20的树。这意味着必须读取内存中不同位置的20个值。完全就是随机访问！

四、页
当一棵树长得越来越高时，随机访问会造成越来越多的延迟。减少这个问题的解决方案很简单：把树长得宽而不是高。它可以通过将多个值存放到单个节点中来实现。

它给我们带来了以下好处：
·这棵树比较浅（两层而不是三层）
·它仍然有很大的空间来创造新的价值观，而不需要进一步增长
对此类索引执行的查询如下所示：

请注意，每次访问节点时，我们都需要加载其所有值。在本例中，我们需要加载4个值（如果树已满，则加载6个值），以便达到我们要查找的值。下面，您将在内存中找到这棵树的可视化视图：

与前面的例子（树的高度）相比，这个搜索应该更快。我们只需要随机访问两次（跳转到单元格0和9），然后依次读取其余值。
随着数据库的增长，此解决方案的效果越来越好。如果您想存储一百万个值，那么您需要：

具有20个级别的二进制搜索树

或者
具有10个级别的3值节点树

来自单个节点的值构成一个页面。在上面的示例中，每个页面由三个值组成。页面是相邻放置在磁盘上的一组值，因此数据库可以通过一次顺序读取一次访问整个页面。
它是如何与现实相联系的？Postgres页面大小为8kB。假设20%用于元数据，那么它还有6kB。页面的一半用于存储指向节点子节点的指针，因此它为我们提供了3kB的值。BIGINT大小为8个字节，因此我们可以在单个页面中存储约375个值。

假设数据库中一些相当大的表有10亿行，我们需要在Postgres树中存储多少级？根据上面的计算，如果我们创建一个可以在单个节点中处理375个值的树，那么它可能会用一个只有四个级别的树存储10亿个值。二进制搜索树需要30个级别的数据量。
总之，在树的单个节点中放置多个值有助于我们降低其高度，从而利用顺序访问的好处。此外，B树不仅可以在高度上生长，还可以在宽度上生长（通过使用较大的页面）。

五、平衡
数据库中有两种类型的操作：写入和读取。在上一节中，我们讨论了从B-树中读取数据的问题。但是，写入也是至关重要的一部分。将数据写入数据库时，B树需要不断更新新值。
树形取决于添加到树中的值的顺序。它在二叉树中很容易看到。如果按不正确的顺序添加值，我们可能会获得不同深度的树。

当树在不同的节点上具有不同的深度时，它被称为不平衡树。基本上有两种方法可以使这样的树恢复到平衡状态：
1.只需按正确的顺序添加值，即可从头开始重建它。
2.随着新值的增加，始终保持平衡。
B树实现了第二个选项。使树始终保持平衡的一个特性称为自平衡。

六、自平衡算法实例
只需创建一个节点并添加新值，直到其中没有可用空间，就可以开始构建B树。

如果相应的页面上没有空间，则需要对其进行拆分。要执行拆分，请选择“拆分点”。在这种情况下，它将是12，因为它是在中间。“分割点”是一个将移动到上页的值。

现在，它把我们带到了一个有趣的地方，那里没有上一页。在这种情况下，需要生成一个新的根页面（它将成为新的根页！）。

最后，在这三个中有一些自由空间，所以可以加上值14。

按照这个算法，我们可以不断地向B树添加新的值，它将始终保持平衡！

在这一点上，你可能有一个合理的担忧，即有很多空闲空间没有机会被填满。例如，值14、15和16在不同的页面上，因此这些页面将永远只保留一个值和两个可用空间。
这是由拆分位置选择引起的。我们总是把页面在中间分开。但每次我们进行拆分时，我们都可以选择任何我们想要的拆分位置。
Postgres有一个算法，每次执行拆分时都会运行！它的实现可以在Postgres源代码中的_bt_findsplilloc（）函数中找到。它的目标是尽可能少地留出空闲空间。

总结
在本文中，您了解了B树是如何工作的。总而言之，它可以简单地描述为一个二进制搜索树产生了两个变化：
1.每个节点可以包含多个值
2.插入新值之后是自平衡算法。
尽管现代数据库使用的结构通常是B-树（如B+树）的一些变体，但它们仍然基于原始概念。在我看来，B树的一大优势是它被直接设计为在实际硬件上处理大量数据。这可能是B树伴随我们这么长时间的原因。

转载：https://blog.allegro.tech/2023/11/how-does-btree-make-your-queries-fast.html