Finding exact row in Clustered index leaf page

Question

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?

Answer 1

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).

• Martin Smith: @user1659786 - An interesting post on the subject
• user1659786: @Martin Smith Thanks Martin. It's just what I needed.