从磁盘检索索引页后，数据库记录访问是否按顺序进行？

Question

这个问题发布在 Stack Overflow 上，但没有得到解答，我希望也许在这里我能找到答案。

我对数据库的理解是，如果在磁盘页面中找到查询或请求的记录，则整个页面将加载到主内存中。

例如，如果表的内容存储在磁盘页面中，如下所示：

+-------+------------+----------+-----------+--------+
| rowid | EmployeeId | Lastname | Firstname | Salary |
+-------+------------+----------+-----------+--------+
|   001 |         10 | Smith    | Joe       |  40000 |
|   002 |         12 | Jones    | Mary      |  50000 |
|   003 |         11 | Johnson  | Cathy     |   4000 |
|   004 |         22 | Jones    | Bob       |  55000 |
+-------+------------+----------+-----------+--------+

假设索引是在 上完成的EmployeeId。

在主内存中加载页面后，如何搜索记录？（顺序或其他方法）

我想知道这是如何在 Oracle 以及其他一些（例如 Microsoft SQL Server）中执行的。

Answer 1

在SQL Server 中，对于常规索引（即不是列存储或 Hekaton），存储引擎可以选择两种方法之一来查找搜索的起点或终点。第一个选项是使用页面末尾的偏移数组进行二分搜索。第二种选择是使用线性插值。

在找到搜索开始/结束点之后，搜索的任何范围扫描部分本质上都是连续的。更具体地说，引擎会保存一个“cookie”来记住搜索位置。

当执行引擎需要下一行时，存储引擎验证 cookie 仍然有效（即并发更改未影响物理结构）并继续使用偏移表从该点查找下一个匹配记录和上一页/下一页链接，根据需要向前或向后搜索。如果 cookie 无效，引擎会有效地重新寻找正确的当前位置。

一个预读机制来帮助确保范围扫描存在于内存由执行引擎所需要的页面之前需要的网页。