[prev] 44 [next]

Selection in Heaps (cont)

The heap is scanned from the first to the last page:

[Diagram:Pics/file-struct/heapscan.png]

Costrange  =  Costpmr  =  b

If we know that only one tuple matches the query (one query),
a simple optimisation is to stop the scan once that tuple is found.

Costone :      Best = 1      Average = b/2      Worst = b