Take the 2-minute tour ×
Database Administrators Stack Exchange is a question and answer site for database professionals who wish to improve their database skills and learn from others in the community. It's 100% free, no registration required.

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?

share|improve this question
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

1 Answer 1

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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