Locating row in index page

Question

In clustered index, we have root, intermediate and leaf level pages. Every page has few records where indicating range of pages from level below.

How SQL check whether some index key belong to specific range, that is, which operation it uses for that?

Is it cursor, which traverse through all rows from one page, or something else?

Have you read through the Clustered Index Structure on MSDN: msdn.microsoft.com/en-us/library/ms177443(v=sql.105).aspx — Shawn Melton, Feb 25 '13 at 8:17
OK, good reference, but not explained how SQL Server check in one index page whether key value exists or not. By example, if we have page which keep values from 1-100, and I search for 55, by which mechanism SQL get a knowledge that this value is on that page? — veljasije, Feb 25 '13 at 10:09

Paul White · Accepted Answer · 2013-02-26 04:50:46Z

The default algorithm to locate a particular record in an index is a binary search using the row offset array:

enter image description here

Enterprise Edition may also use interpolation based on linear regression information:

Linear Regression

I wrote about the details and the performance implications here.

1 Answer 1