Problem 6 - Olympiad

The SQL statement SELECT * FROM T WHERE a=5 ORDER BY b LIMIT 10 can use either (a) a clustered B+-tree on (a,b) or (b) a hash index on a plus an in-memory sort. Table T occupies 50 k pages and 100 tuples match a=5. Which index yields the fewest page I/Os and what is that number?

Correct: N/A

The B+-tree is clustered on (a,b) so the 100 matching rows are adjacent. With 100 tuples and typical 100-tuples-per-page density we read at most 2 leaf pages plus 9 internal pages = 11 pages. The hash index would require fetching 100 random pages plus 1 for sorting = 101 pages.