[prev] 15 [next]

Exercise 2: Optimising Sorted-file Search

The searchBucket(f,p,k,val) function requires:
  • read the pth page from data file
  • scan it to find a match and min/max k values in page
  • while no match, repeat the above for each overflow page
  • if we find a match in any page, return it
  • otherwise, remember min/max over all pages in bucket
Suggest an optimisation that would improve searchBucket() performance for most buckets.