B+树索引搜索(Index Seek)与索引扫描(Index Scan)

原创
2023/05/21 21:59
阅读数 53

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

搜索还是扫描

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

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

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

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

让我们看一些例子。

索引搜索示例

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

SELECT *
FROM STUDENTS
WHERE ID = 1 OR ID = 5003 or ID = 9000

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

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

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

索引扫描示例

在同一张表上,让我们执行以下查询:

SELECT *
FROM STUDENTS
WHERE ID BETWEEN 1000 and 9000

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

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

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

为什么需要搜索和扫描?

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

问题所在

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

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

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

SELECT *
FROM STUDENTS
WHERE ID IN 
(SELECT ID 
FROM STUDENTS_GRADES
WHERE GRADE > 90 
)

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

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

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

总结

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

如果你喜欢我的文章,点赞,关注,转发!

展开阅读全文
加载中
点击引领话题📣 发布并加入讨论🔥
0 评论
0 收藏
0
分享
返回顶部
顶部