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?
Best Answer
The default algorithm to locate a particular record in an index is a binary search using the row offset array:
Enterprise Edition may also use interpolation based on linear regression information:
I wrote about the details and the performance implications in SQL Server, Seeks, and Binary Search.