[prev] 17 [next]

Selection in Sorted Files (cont)

For range queries on unique sort key (e.g. primary key):
  • use binary search to find lower bound
  • read sequentially until reach upper bound
Costrange  =  Costone + (bq-1).(1+Ov)

If secondary key, similar method to pmr.

[Diagram:Pics/file-struct/sfile-range.png]