[prev] 16 [next]

Selection in Sorted Files (cont)

For pmr query, on non-unique attribute k
  • assume file is sorted on k
  • tuples containing k may appear in several pages

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

Begin by locating a page p containing k=val   (as for one query).

Scan backwards and forwards from p to find matches.

Thus, Costpmr  =  Costone + (bq-1).(1+Ov)