[prev] 22 [next]

Selection via Scanning (cont)

Overview of scan process: 

for each page P in relation Employee {
    for each tuple t in page P {
        if (t.id == 762288) return t
}   }

Cost analysis for one searching in unordered file

  • best case: read one page, find tuple
  • worst case: read all b pages, find in last (or don't find)
  • average case: read half of the pages (b/2)
Page Costs:   Costavg = b/2    Costmin = 1    Costmax = b