> Photo by Todd Quackenbush on Unsplash

引入没有任何公式和计算机科学理论的B + Tree索引

如果您不是DBA或数据库开发人员，则可能不知道数据库索引的机制。 但是，只要您可以编写一些SQL查询，您就一定已经听说过数据库索引，并且知道索引可以提高SQL查询的性能。

在本文中，我将尝试使用最简单的语言和图表来说明B + tree索引如何改善SQL查询的性能。 我以B + tree索引为例的原因是

· 大多数关系数据库管理系统（例如MySQL，SQL Server和Oracle）都使用它

· 它可以提高大多数类型的SQL查询的性能，而不是特定类型的性能

它看起来怎样？

> Photo by Shane Hauser on Unsplash

让我们简化该指令，这是一个简化的图，说明了B + tree索引的结构。

在上面的B + Tree示例中，每个矩形代表硬盘中的一个块，而蓝色填充点代表将这些块链接在一起的指针。

请注意，此图出于演示目的极大地简化了B + Tree，因为它假定每个硬盘块只能包含2个键。 实际上，这将更大。

重要的是要了解如何构造B + tree索引。 我们需要知道，"叶子节点"级别假定具有创建此索引的字段的所有值。 在上面的示例中，很明显，我们在此表列中只有9行，其值从1到9。

如果您对上述B + Tree的构建方式感兴趣，请参阅我的另一篇文章：如何在数据库中构建B + Tree索引？

它是如何工作的？

> Photo by Maria Krasnova on Unsplash

B + tree可以帮助大多数数据库查询方案，这也是其有用的原因。

均等测试查询

假设我们的SQL查询是在条件为"等于"的情况下检索的，例如：

SELECT *FROM TABLEWHERE ID = 3

为了找到等于3的ID，按如下方式使用B +树。

· 从树的顶层开始，3小于5，因此我们需要使用数字5左侧的指针

· 在下一级别，3在2到4之间，因此我们需要在中间使用指针

· 我们在叶子节点上有块，这里有3个

查询比较

如果我们的SQL查询正在范围内搜索怎么办？ 例如，这是SQL查询：

SELECT *FROM TABLEWHERE ID BETWEEN 3 AND 7

这是该过程的演示。

· 从树的顶层开始，3小于5，因此我们需要使用数字5左侧的指针

· 在下一级别，3在2到4之间，因此我们需要在中间使用指针

· 我们在叶子节点上有块，这里有3个

· 由于我们要查询比较数据，因此光标将继续在该代码块中获取，因此我们可以得到数字4

· 我们还没有到7，所以光标将继续转到下一个（右）叶子节点块

· 我们到达了下一个区块，所以我们得到了数字5和6。但是它尚未完成，与上一步类似的机制将用于到达下一个区块。

· 我们到达了包含数字7的下一个块

· 我们已经达到范围的上限，因此查询完成

B +树特征

> Photo by Cristina Gottardi on Unsplash

B + Tree索引的最重要特征是它由树的叶节点级别和搜索关键字级别组成。

· 该索引列的所有值都出现在叶节点中。

· 非叶节点仅用于搜索目的，因此仅存在指向较低级别的指针。 换句话说，它们不能导致实际的数据输入。

· 叶子节点中的每个键都有一个指向数据条目的额外指针，因此它可以导致光标查找/获取数据行。

B + Tree如何提高性能？

> Photo by Anders Jildén on Unsplash

如以上示例所示，B + Tree适用于"相等"条件和比较条件。

非叶水平

可以看出，查询仅需要通过非叶子节点上的搜索键来找到期望值。 因此，当在创建B + Tree索引的列上检索SQL查询时，仅需要经过几个级别的非叶节点。

您必须考虑到非叶节点一定是一种开销，并且当有很多数据行时，它会变慢，因为可能有许多非叶级别。

部分正确。 是的，需要扫描非叶节点以获得期望值。 实际上，扫描次数完全等于非叶级别的数目。 但是，实际上，我们硬盘上的块将比上述示例大得多。 通常，具有1000万个条目的表可以放在只有3个非叶级别的B + Tree中。 即使表非常大，例如数十亿规模，通常B + Tree的非叶级别数通常为4或5。

因此，使用B + Tree索引可以大大减少SQL查询中扫描的硬盘块的数量。

为什么要扫描的块数很重要？

我想本文的读者可能没有计算机科学背景，所以我想对"块"进行简单的解释对于更好地理解问题可能是必要的。

在我们的硬盘中，数据并不总是按顺序存储。 单个文件可能会拆分并存储到不同的块中。 因此，当我们读取文件/数据集/表时，为了扫描整个文件，有必要在不同的块之间跳转。

通常，对于机械硬盘驱动器，有一个只能上下移动的磁头。 当需要从其他位置读取数据时，整个硬盘驱动器会将该位置旋转到磁头所在的位置，以便磁头可以读取数据。

想象一下，我们正在扫描1000个块。 最坏的情况是磁盘将需要旋转1000次。 如果我们使用索引，则此数字将减少为4-5次。 因此，索引可以提高效果。

摘要

> Photo by Aaron Burden on Unsplash

在本文中，我分享了B + tree的外观以及它的工作方式和如何促进SQL查询（通常在相等和比较的条件下）。

事实证明，B + Tree不再是最高级的数据库索引，但我相信它可能是仍在大多数RDBMS中广泛使用的最经典的索引，它仍然是证明为什么我们需要数据库索引的最佳示例 表及其工作方式。 希望这对您足够有趣。

(本文翻译自Christopher Tao的文章《Why We Need Indexes for Database Tables》，参考：
https://towardsdatascience.com/why-we-need-indexes-for-database-tables-25198145a8ca)