Is database record access sequential after retrieving the indexed page from disk? [closed]

Question

Closed. This question needs details or clarity. It is not currently accepting answers.

---

Want to improve this question? Add details and clarify the problem by editing this post.

Closed 6 years ago.

Improve this question

This question was posted on Stack Overflow but left unanswered, I was hoping maybe here I might find an answer.

What I understand about databases that if a queried or requested record is found in the disk page, the whole page is loaded to main memory.

For example, if the content of table stored in disk page like this:

+-------+------------+----------+-----------+--------+
| 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 |
+-------+------------+----------+-----------+--------+

Assume the indexing is done on EmployeeId.

After loading the page in main memory, how the record is searched? (sequential or some other method)

I want to know how this is carried out in Oracle and maybe some other such as Microsoft SQL Server.

Answer 1

In SQL Server, for a regular index (i.e. not columnstore or Hekaton) the storage engine can choose one of two methods to find the start or end point of a search. The first option is a binary search using the offset array at the end of the page. The second option is to use linear interpolation.

After the search start/end point is found, any range-scan portion of the search is essentially sequential. More specifically, the engine saves a 'cookie' to remember the search position.

When the next row is needed by the execution engine, the storage engine validates that the cookie is still valid (i.e. a concurrent change hasn't affected the physical structure) and proceeds to find the next matching record from that point, using the offset table and previous/next page links as necessary, searching either forward or backward. If the cookie is invalid, the engine effectively re-seeks to find the correct current position.

A read-ahead mechanism is used to help ensure pages needed by a range scan are present in memory before the page is needed by the execution engine.