B＋树索引搜索（Index Seek）与索引扫描（Index Scan）

在本文中，我探讨了数据库中索引搜索（Index Seek）和索引扫描（Index Scan）的性能影响。虽然这些术语主要与 SQL Server 相关，但它们对于在数据库管理系统（DBMS）平台中搜索 B+树非常重要。

搜索还是扫描

索引搜索通过从根节点开始遍历 B+树，查找叶节点页中的单个值。这至少需要 2 次I/O操作，具体取决于 B+树的深度。而索引扫描通过扫描已经排序和链接的 B+树叶节点页来进行操作。

索引扫描更适用于范围查询或接近的大值，而索引搜索适用于返回非常少的结果或者更具选择性的查询。

为了更好地说明这一点，我们以学生表为例，其中包含了 ID 整数字段等。我们特别关注 ID 字段上的 B+树索引。

假设一个页面大小可以容纳多达 2000 个元素（键值对），那么结构可能如下所示。

让我们看一些例子。

索引搜索示例

考虑针对学生表的以下查询：

对于 ID 字段上的索引，该查询需要执行 3 次索引搜索，针对值分别为 1、5003 和 9000。每个值都位于不同的页面上，这意味着没有缓存命中。

当然，一旦我们获得了键值元素对，值将是指向表中所有字段的行 ID。这在数据库系统之间有所不同，取决于 ID 是否是主索引以及是否是聚集索引。

注意：如果过滤条件中包含 ID = 2，那么该条件将与存储在同一页上的值 1 满足条件，因此我们已经获取了它。缓存命中是关键。

索引扫描示例

在同一张表上，让我们执行以下查询：

根据具体实现，该查询可能会在范围中的最低元素（1000）上执行搜索，以找到最低页，并沿着链接的叶子页面遍历，直到达到具有条目9000的页为止，此时索引扫描停止。

这是可能的，因为叶子页面中的条目是有序的，并且彼此链接。

每个叶子页面都指向下一个页面，这是 B+Tree 的一个特性。

为什么需要搜索和扫描？

对于在1000到9000之间的每个值都进行搜索会导致更多的I/O，并且减慢查询速度。而在第一个示例中，从具有值1的页面到具有9000的页面进行扫描，寻找1、5003和9000是一种IO浪费。数据库最终会获取不需要的页面。

问题所在

在某些情况下，搜索或扫描是显而易见的，我上面提供的示例就是如此。但并非所有情况都如此简单。

有些情况下，查询优化器可能会根据内部查询结果的结果选择不同的计划。

以查找分数高于90分的学生的完整学生行为例，这些成绩存储在单独的表 STUDENTS_GRADES 中。

内部查询可能返回单个值，也可能返回散布在各处的数千个 ID。根据输出结果，查询优化器可能会选择扫描或搜索。

内部查询结果集越大，使用索引的效率就越低。分散的 ID 将分布在许多页面中，导致过多的 I/O 操作。在某些情况下，为了避免不必要的 I/O 操作，查询优化器可能会完全跳过索引而进行全表扫描。

坦率地说，我不喜欢结果不可预测的查询，这只会让人感到困扰。我会尽量消除不可预测性，即使需要进行模式更改。

总结

你如何知道哪个更好？扫描还是搜索？查询优化器会尽力而为，但到最后可能会错过并选择错误的计划。因此，如果可能的话，我们需要以可预测的方式编写查询。我知道这并不总是可能的，但了解背后发生的事情是第一步。