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.

When traversing through Clustered index in Sql Server, the engine will start from Root page and traverse over non leaf nodes until it reaches leaf level page (data page). Every data page has row offset array where every slot is ordered by clustered key (physical order of data may not be ordered). Slots only have 2byte offset of the row (doesn't contain key value). My question is: If I have say table with two int columns (8 byte) i would have around 1000 entries per data page. How does engine locate exact row with index 500 (if that page contains rows with indexes from 1 to 1000). Does it traverse through slot sequentially examining every row or is there any more efficient algorithm which sql server use?

share|improve this question

migrated from stackoverflow.com Sep 27 '12 at 4:07

This question came from our site for professional and enthusiast programmers.

1  
Searching through 1000 locations in a page that has already been loaded in memory is substantially faster than the higher level index operations that were required to locate this page on disk and load it. –  Damien_The_Unbeliever Sep 24 '12 at 8:55
    
@Damien_The_Unbeliever True, but once this page is in memory (together with non leaf pages) cost of finding exact row in the page will be more expansive than finding the correct page. Especially if there is only few intermediate non leaf pages. –  user1659786 Sep 24 '12 at 8:59

1 Answer 1

up vote 2 down vote accepted

The specifics of how SQL Server does it is not public.

But I recommend you read the vast research material on the subject which is public. Modern B-Tree Techniques is a good start. Many more papers from Goetz Graefe talk about this area, he is well known in the industry.

Interpolation search is a well known technique in B-Trees and there is plenty of material detailing possible approaches (bear in mind that none of the papers describe explicitly how SQL Server does it and there are many ways to skin a cat).

share|improve this answer
    
Thank you very much. These are excellent resources. –  user1659786 Sep 24 '12 at 9:18
    
BTW, if you are asked in an interview "how to find the slot of value X in an sorted array" and you answer "linear search", is unlikely to get a good feedback... Binary search is taught in CS101. –  Remus Rusanu Sep 24 '12 at 10:35
    
I was just curious. It's not about job :) –  user1659786 Sep 24 '12 at 11:14
    
@user1659786 - An interesting post on the subject –  Martin Smith Sep 24 '12 at 11:31
    
@Martin Smith Thanks Martin. It's just what I needed. –  user1659786 Sep 24 '12 at 11:40

Your Answer

 
discard

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