4

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?

  • 1
    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
5

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 in SQL Server, Seeks, and Binary Search.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.