SQL 索引解释，Pt。 2

已发表: 2022-03-11

在SQL Indexes Explained的第一课中，我们学习了使用排序来加速数据检索。 虽然在对行进行排序后我们的查询执行速度更快，但排序涉及至少读取每一行一次并移动它们。 这使得该方法比简单地按顺序读取整个表更慢且效率更低。

合乎逻辑的结论似乎是我们应该维护给定表的排序副本——我们将正式称之为 SQL索引，前缀为IX_ 。 第一篇文章中的检索算法将适用，我们不需要在开始之前对表进行排序。

索引作为表的排序副本

让我们再次使用 Google 表格来看看这个想法的实际实现。 我们的预订电子表格变成了包含相同数据的五张表格的集合。 每个工作表都根据不同的列集进行排序。

此处的练习旨在比上一篇 SQL 索引教程文章中的练习更简单——它们可以通过感觉来完成，而不是通过计时器和行数来完成。 一些练习看起来非常相似，但这一次，我们正在探索：

  1. 使用单独的索引而不是排序的主表时如何更有效地检索数据
  2. 修改数据时如何保持每个索引和表的顺序

前面的教程侧重于读取，但在许多常见的现实世界数据动态中——包括我们的酒店预订——我们必须考虑索引对写入性能的影响，无论是插入新数据还是更新现有数据。

初步练习：取消预订

要了解使用排序表策略的 SQL 索引性能，您的任务是从 2020 年 8 月 22 日在酒店 4 中删除客户端 12 的预订。请记住，您必须从所有副本中删除一行表并保持正确的排序。

完毕？ 应该清楚的是，保留表的多个排序副本的想法并不像看起来那么好。 如果您仍有任何疑问，您也可以尝试重新插入刚刚删除的预订或更改现有预订的日期。

虽然表的排序副本允许更快的检索，但正如我们刚刚了解到的，数据修改是一场噩梦。 每当我们需要添加、删除或更新现有行时，我们都必须检索表的所有副本，找到一行和/或应该添加或移动它的位置，最后移动数据块。

使用行地址的 SQL 索引

此电子表格包含使用不同方法的索引。 索引行仍然根据特定标准进行排序，但我们不会将所有其他信息保留在索引行中。 相反，我们只保留“行地址”，即“预订”表中的行地址——代表表本身——在 H 列中。

所有 RDBMS 实现都使用操作系统级别的功能来使用物理地址快速找到磁盘上的块。 行地址通常由块地址加上行在块中的位置组成。

让我们做一些练习来了解这个索引设计是如何工作的。

练习 1：客户的所有预订

与第一篇文章一样，您将模拟以下 SQL 查询的执行：

 SELECT * FROM Reservations WHERE ClientID = 12;

同样，有两种合理的方法。 第一个是简单地从 Reservations 表中读取所有行并仅获取符合条件的行：

 For each row from Reservations If Reservations.ClientID = 12 then write down Reservations.*

第二种方法涉及从 IX_ClientID 表中读取数据，对于任何符合条件的项目，根据 rowAddress 值在 Reservation 表中查找一行：

 Get first row from IX_ClientID where ClientID = 12 While IX_ClientID.ClientID = 12 Fetch Reservations.* where rowAddress = IX_ClientID.rowAddress Write down Reservations.* Get next row from IX_ClientID

在这里，表达式Get first row from由类似于上一篇文章中的循环实现：

 Repeat Fetch next row from IX_ClientID Until ClientID >= 12

您可以通过向下滑动直到找到一行来找到具有给定 rowAddress 的行，或者在 rowAddress 列上使用过滤器。

如果只返回少数保留，使用索引的方法会更好。 但是，由于要返回数百（有时甚至只是数十）行，直接使用 Reservations 表会更快。

读取量取决于 ClientID 的值。 对于最大值，您必须读取整个索引，而对于最小值，它位于索引的开头。 平均值是行数的一半。

我们稍后会回到那部分并提出一个有效的解决方案。 现在，让我们关注找到符合我们条件的第一行之后的部分。

练习 2：从给定日期开始的预订数量

任务是使用新的索引设计计算 2020 年 8 月 16 日的签到次数。

 SELECT COUNT (*) FROM Reservations WHERE DateFrom = TO_DATE('2020-08-16','YYYY-MM-DD');

无论涉及多少行，使用适当索引进行计数的方法都优于表扫描。 原因是我们根本不需要访问 Reservations 表——我们在索引本身中有我们需要的所有信息：

 Count := 0 Get first row from IX_DateFrom where DateFrom >= '2020-08-16' While found and DateFrom < '2020-08-17' Count := Count + 1 Get next row from IX_DateFrom Write down Count

该算法与使用排序表的算法基本相同。 但是，索引行比表行短得多，因此我们的 RDBMS 必须从磁盘读取更少的数据块。

练习 3：刑事调查（给定酒店和日期范围的客人名单）

让我们准备一份 2020 年 8 月 13 日至 14 日抵达酒店 3 的客人名单。

 SELECT ClientID FROM Reservations WHERE DateFrom BETWEEN ( TO_DATE('2020-08-13','YYYY-MM-DD') AND TO_DATE('2020-08-14','YYYY-MM-DD') ) AND HotelID = 3;

我们可以从 Reservations 表中读取所有行或使用可用的索引之一。 在对根据特定标准排序的表进行相同的练习后，我们发现索引IX_HotelID_DateFrom是最有效的。

 Get first row from IX_HotelID_DateFrom where HotelID = 3 and DateFrom between '2020-08-13' and '2020-08-14' While found and DateFrom < '2020-08-15' and IX_HotelID_DateFrom.HotelID = 3 Fetch Reservations.* where rowAddress = IX_HotelID_DateFrom.rowAddress Write down Reservations.ClientID Get next row from IX_HotelID_DateFrom

我们可以设计一个更有效的索引吗？

我们访问该表是因为ClientID值，这是我们报告的客人列表所需的唯一信息。 如果我们在 SQL 索引中包含该值，我们根本不必访问该表。 尝试仅从此类索引IX_HotelID_DateFrom_ClientID中准备一个读取列表：

 Get first row from IX_HotelID_DateFrom_ClientID where HotelID = 3 and DateFrom between '2020-08-13' and '2020-08-14' While found and HotelID = 3 and DateFrom < '2020-08-15' Write down ClientID Get next row from IX_HotelID_DateFrom_ClientID

当索引包含查询执行所需的所有信息时，我们说索引覆盖了查询。

练习 4：客人姓名而不是 ID 的列表

客人 ID 列表对于调查犯罪的警官来说毫无用处。 我们需要提供名称：

 SELECT c.ClientName FROM Reservations r JOIN Clients c ON r.ClientID = c.ClientID WHERE r.DateFrom BETWEEN ( TO_DATE('2020-08-13', 'YYYY-MM-DD') AND TO_DATE('2020-08-14', 'YYYY-MM-DD') ) AND r.HotelID = 3;

为了提供一个列表，除了Reservations表中的数据，我们还需要一个包含客人信息的Clients表，可以在这个 Google 表格中找到。

这个练习与前一个练习类似，方法也是如此。

 Get first row from IX_HotelID_DateFrom_ClientID where HotelID = 3 and DateFrom between '2020-08-13' and '2020-08-14' While found and HotelID = 3 and DateFrom < '2020-08-15' Fetch Clients.* where ClientID = IX_HotelID_DateFrom_ClientID.ClientID Write down Clients.ClientName Get next row from IX_HotelID_DateFrom_ClientID

表达式Fetch Clients.* where ClientID = IX_HotelID_DateFrom_ClientID.ClientID可以通过表扫描或使用我们的索引来实现。 如果我们使用表扫描，对于While循环中的每个ClientID ，我们必须平均读取Clients表中的一半行：

 -- Get row from Clients using table scan Repeat Fetch next row from Clients Until ClientID = IX_HotelID_DateFrom_ClientID.ClientID or not found If found Write down ClientName

到目前为止我们所考虑的索引实现——让我们称之为“平面”索引实现——不会有太大帮助。 我们必须从索引中读取相同数量的行（尽管行更小），然后使用RowAddress跳转到Clients中的行：

 -- Get row from Clients using flat index Repeat Fetch next row from Clients_PK_Flat Until ClientID >= IX_HotelID_DateFrom_ClientID.ClientID If found Fetch Clients.* where rowAddress = Clients_PK_Flat.rowAddress Write down ClientName

注意：这里， PK指的是“主键”，我们将在本系列的后面探讨这个术语。

有没有办法在不必读取这么多行的情况下实现这一点？ 是的——这正是 B 树索引的用途。

平衡树 (B-tree) 索引

让我们将Clients_PK_Flat中的行分成四行块，并创建一个列表，其中包含块中最后一个ClientID的值和块开始的地址（列IndexRowAddress ）。 生成的数据库索引数据结构——您可以在 Clients_PK_2Levels 表中找到。 试试新结构如何帮助您找到ClientID为 28 的客户端。算法应如下所示：

 Fetch Level2.* Loop Leaf_address := Level3Address Exit when ClientID >= 28 Fetch next row from Level2 Fetch Level3.* where Level3Address = Leaf_address -- 3-21 Loop Client_address := RowAddress Exit when ClientID >= 28 Fetch next row from Level 3 Fetch Clients.* where rowAddress = Client_address -- 42 Write down Clients.*

您可能发现我们可以添加另一个级别。 级别 1 由四行组成，您可以在 IX_Clients_PK 选项卡中看到。 要找到 ClientID 为 28 的来宾名称，您必须从主键结构中读取三个数据块（节点）（每层一个），最后跳转到地址为 42 的 Clients 行。

这种 SQL 索引的结构称为平衡树。 当从根节点到每个叶级节点的路径具有相同的长度时，树是平衡的，即所谓的 B 树深度。 在我们的例子中，深度是三。

基于电子表格中 IX_Clients_PK 选项卡的 B 树示例，显示了上述算法的查找路径。

从现在开始，我们将认为每个索引都具有 B 树结构，即使我们的电子表格仅包含叶级条目。 关于 B-tree 最重要的事实是：

  • B树索引结构是市场上所有主要RDBMS最常用的索引。
  • 平衡树的所有级别都按关键列值排序。
  • 数据以块为单位从磁盘中读取。
  • 一个 B 树节点包含一个或多个块。
  • 影响查询性能的最重要因素是从磁盘读取的块数。
  • 每个新 B 树级别中的项目数，从根开始，到叶级别结束，呈指数增长。

练习 5：刑事调查，第二部分

现在，巡视员正在从 A 市的所有酒店中查找相应客人的姓名、到达日期和酒店名称的列表。

 SELECT h.HotelName, r.DateFrom as CheckInDate, c.ClientName FROM Reservations r JOIN Clients c ON r.ClientID = c.ClientID JOIN Hotels h ON r.HotelID = h.HotelID WHERE r.DateFrom BETWEEN ( TO_DATE('2020-08-13', 'YYYY-MM-DD') AND TO_DATE('2020-08-14', 'YYYY-MM-DD') ) AND h.City = 'A';

方法一

如果我们使用索引IX_DateFrom_HotelID_ClientID ，那么对于日期范围内的每一行，我们都必须访问 Hotels 表并检查酒店是否来自城市 A。如果是，我们也必须访问 Clients 表，以读客户的名字。

 For each row from IX_DateFrom_HotelID_ClientID where DateFrom between '2020-08-13' and '2020-08-14' For each row from Hotels where HotelID = IX_DateFrom_HotelID_ClientID.HotelID If Hotels.City = 'A' then Fetch Clients.* where ClientID = IX_HotelID_DateFrom_ClientID.ClientID Write down Hotels.HotelName, IX_HotelID_DateFrom_ClientID.DateFrom, Clients.ClientName

方法二

使用IX_HotelID_DateFrom_ClientID为我们提供了更有效的执行计划。

 For each row from Hotels where City = 'A' For each row from IX_HotelID_DateFrom_ClientID where HotelID = Hotels.HotelID and DateFrom between '2020-08-13' and '2020-08-14' Fetch Clients.* where ClientID = IX_HotelID_DateFrom_ClientID.ClientID Write down Hotels.HotelName, IX_HotelID_DateFrom_ClientID.DateFrom, Clients.ClientName

从Hotels表中，我们找到了城市 A 的所有酒店。知道了这些酒店的 ID，我们可以从IX_HotelID_DateFrom_ClientID索引中读取后续项目。 这样，在找到每个酒店和日期的 B 树叶级别的第一行之后，我们就不会读取 A 市以外的酒店的预订信息。

将短 Hotels 表与 IX_HotelID_DateFrom_ClientID 索引结合使用。该表显示在左侧，突出显示了两行酒店，对应于城市 A 中的酒店。然后通过 B-tree 过程对这些酒店中的每一个进行快速查找，从而使它们直接指向索引中的块在右侧，所有抢​​手的数据都是连续的。

在这里，我们可以看到，当我们拥有适合我们目标的数据库索引时，额外的连接实际上可以使查询更快。

当我解释分区的动机及其影响时，将更详细地讨论 B 树结构以及在插入、更新或删除行时如何更新它。 关键是我们可以在使用索引时快速考虑这个操作。

SQL 中的索引查询：细节决定一切

当涉及到索引和数据库时，在 SQL 语言级别工作在一定程度上隐藏了实现细节。 这些练习旨在帮助您了解使用不同 SQL 索引时执行计划的工作方式。 阅读本文后，我希望您能够根据可用索引和设计索引猜测最佳执行计划，以使查询尽可能快速和高效。

在本系列的下一部分中，我们将使用和扩展新获得的技能来调查和了解在 SQL 中使用索引的最常见的最佳实践和反模式。 我有一个好的和最佳实践列表，我想在下一部分中讨论，但是为了使下一篇文章更符合您的需求和经验，请随时发布您自己希望看到回答的问题。

在SQL 索引解释的最后一部分，我们还将了解表和索引分区、使用它的正确和错误动机，以及它对查询性能和数据库维护的影响。