B-tree如何使数据查询更快？
# B 树是一种有助于搜索大量数据的结构。它是 40 多年前发明的，但仍然被大多数现代数据库所采用。尽管有更新的索引结构，例如 LSM 树，但 B 树在处理大多数数据库查询时是不败的。
# 二叉搜索树 (BST)
# 那么“B”代表什么？
据wikipedia.org报道，B 树的发明者 Edward M. McCreight 曾说过：“你越多地思考 B 树中的 B 的含义，你就越能理解 B 树。”
一个简单的二叉搜索树(BST)示例
较大的数字始终位于右侧，较小的数字始终位于左侧。
这棵树包含七个数字，但是我们最多需要访问三个节点才能找到任何数字。以下示例可视化搜索 14。我使用 SQL 定义查询，以便将这棵树视为实际的数据库索引。
# 考虑硬件存储
从理论上讲，使用二叉搜索树来运行我们的查询看起来不错。它的时间复杂度（搜索时）与 O(logn)B 树相同。但是，在实践中，此数据结构需要在实际硬件上工作。索引必须存储在计算机上的某个位置。
计算机有三个可以存储数据的位置：
- CPU 缓存
- RAM（内存）
- 磁盘（存储）
# 数据库大量使用内存 （RAM）。它有一些很大的优点：
- 确保快速随机访问（下一段将详细介绍）
- 它的大小可能非常大（例如，AWS RDS 云服务为实例提供几 TB 的可用内存）。
# 缺点:
- 当电源关闭时，您将丢失数据。此外，与磁盘相比，它非常昂贵。
最后，内存的缺点是磁盘存储的优点。它很便宜，即使我们失去电力，数据也会留在那里。但是，天下没有免费的午餐！问题是我们需要小心随机和顺序访问。从磁盘读取速度很快，但仅限于某些条件！
# 随机和顺序访问
内存可以可视化为一行值的容器，其中每个容器都有编号
现在，假设我们想要从容器 1、4 和 6 读取数据。它需要随机访问
然后让我们将其与读取容器 3、4 和 5 进行比较。可以按顺序完成
随机跳转”和“顺序读取”之间的区别可以根据硬盘驱动器来解释。它由磁头和圆盘组成。
“随机跳跃”需要将磁头移动到磁盘上的给定位置。“顺序读取”只是旋转磁盘，允许磁头读取连续值。读取兆字节的数据时，这两种访问类型之间的差异是巨大的。使用“顺序读取”可显著缩短获取数据所需的时间
Adam Jacobs在Acm Queue上发表的文章“The Pathologies of Big Data”中研究了随机访问和顺序访问之间的速度差异。它揭示了一些令人震惊的事实：
- HDD上的顺序访问可能比随机访问快数十万倍。🤯
- 从磁盘按顺序读取可能比从内存中随机读取更快。
现在谁甚至使用硬盘？固态硬盘呢？这项研究表明，完全按顺序读取 HDD 可能比 SSD 更快。但是，请注意，这篇文章是 2009 年的文章，SSD 在过去十年中得到了显着发展，因此这些结果可能已经过时。
总而言之，关键的一点是，我们尽可能选择顺序访问。在下一段中，我将解释如何将其应用于我们的索引结构。
# 优化树以实现顺序访问
二叉搜索树可以以与堆相同的方式在内存中表示：
- 父节点位置为i
- 左节点位置是2i
- 正确的节点位置是2i+1
以下是根据示例计算这些位置的方式（父节点从 1 开始）
根据计算出的位置，节点与内存对齐
你还记得几章前可视化的查询吗？
这就是它在内存级别上的样子
执行查询时，需要访问内存地址 1、3和6。访问三个节点不是问题;但是，随着我们存储的数据越来越多，树会变得更高。存储超过100万个值需要至少20个高度的树。这意味着必须从内存中不同位置读取 20 个值。它会导致完全随机的访问！
# Pages页面
当一棵树长得很高时，随机访问会导致越来越多的延迟。减少这个问题的解决方案很简单：在宽度而不是高度上种植树。它可以通过将多个值打包到单个节点中来实现。
它为我们带来了以下好处：
- 这棵树较浅（两层而不是三层）
- 它仍然有很大的空间来容纳新的价值，而不需要进一步增长
对此类索引执行的查询如下所示：
请注意，每次访问节点时，我们都需要加载其所有值。在此示例中，我们需要加载 4 个值（如果树已满，则为 6 个值）才能到达我们正在寻找的值。下面，您将在内存中找到此树的可视化效果：
与前面的示例（树的高度增长）相比，此搜索速度应该更快。我们只需要随机访问两次（跳转到单元格 0 和 9），然后按顺序读取其余值。
随着我们数据库的增长，这个解决方案的效果越来越好。如果要存储 100 万个值，则需要：
- 有20个级别的二叉搜索树
OR - 具有10个级别的3值节点树
来自单个节点的值构成一个页面。在上面的示例中，每个页面由三个值组成。页面是放置在彼此相邻的磁盘上的一组值，因此数据库可以通过一次顺序读取一次到达整个页面。
它如何指代现实？Postgres 页面大小为 8kB。假设 20% 用于元数据，因此还剩 6kB。需要一半的页面来存储指向节点子节点的指针，因此它为我们提供了 3kB 的值。BIGINT 大小为 8 个字节，因此我们可以在单个页面中存储 ~375 个值
假设数据库中一些相当大的表有 10 亿行，我们需要在 Postgres 树中存储多少个级别来存储它们？根据上面的计算，如果我们创建一个可以在单个节点中处理 375 个值的树，它可能会存储 10 亿个值，而树只有四个级别。二叉搜索树需要 30 个级别才能处理如此数量的数据。
总而言之，在树的单个节点中放置多个值有助于我们降低其高度，从而利用顺序访问的好处。此外，B 树不仅可以在高度上增长，还可以在宽度上增长（通过使用更大的页面）。
# 平衡
数据库中有两种类型的操作：写入和读取。在上一节中，我们解决了从 B 树中读取数据的问题。尽管如此，写作也是一个至关重要的部分。在将数据写入数据库时，B树需要不断更新新值。
树的形状取决于添加到树中的值的顺序。它在二叉树中很容易看到。如果值以不正确的顺序相加，我们可能会获得具有不同深度的树。
当树在不同的节点上具有不同的深度时，称为不平衡树。基本上有两种方法可以将这样的树恢复到平衡状态：
- 只需按正确的顺序添加值即可从头开始重建它
- 随着新值的添加，始终保持平衡
B树实现了第二个选项。使树始终保持平衡的功能称为自平衡。
# 自平衡算法示例
构建 B 树只需创建一个节点并添加新值即可开始，直到其中没有可用空间。
如果对应页面上没有空格，则需要拆分。要执行分割，需要选择“分割点”。在这种情况下，它将是 12，因为它位于中间。“拆分点”是将移动到上页的值。
现在，它把我们带到了一个有趣的点，没有上页。在这种情况下，需要生成一个新的页面（它将成为新的根页面！）
最后，这三个中有一些可用空间，因此可以添加值 14。
按照这个算法，我们可以不断地向 B 树添加新的值，并且它会一直保持平衡！
在这一点上，您可能有一个合理的担忧，即有很多可用空间没有机会被填充。例如，值 14、15 和 16 位于不同的页面上，因此这些页面将永远只有一个值和两个可用空格。
这是由拆分位置选择引起的。我们总是在中间拆分页面。但是每次我们进行拆分时，我们都可以选择我们想要的任何拆分位置。
Postgres有一个算法，每次执行拆分时都会运行！它的实现可以在 Postgres 源代码的 _bt_findsplitloc（） 函数中找到。它的目标是尽可能少地留出可用空间。
# 总结
在本文中，您了解了 B 树的工作原理。总而言之，它可以简单地描述为具有两个变化的二叉搜索树：
- 每个节点可以包含多个值
- 插入新值后跟自平衡算法。
尽管现代数据库使用的结构通常是 B 树的一些变体（如 B+树），但它们仍然基于原始概念。在我看来，B树的一大优势是它直接被设计用于处理实际硬件上的大量数据。这也许就是B树能陪伴我们这么久的原因。