Heap Files

Heap Files

Scan:

The  cost  is B(D  +RC)
because  we  must  retrieve  each  of  B  pages  taking  time  D  per page, and for each page, process R records taking time C  per record.

Search with Equality Selection:

Suppose that  we know in  advance  that  exactly one record  matches the required selection, i,e. the selection is specified on a candidate key.
On average, we must scan half the file, assuming that the record exists  in the first half, if the record exists in second half then it is the entire scan we did.

The cost is O.5B(D + RC)

If the  selection  is  not  on  a candidate  key  field  (e .g.,  "Find employees  aged 18"),we  always  have  to scan  the  entire  file  because  records  with  age  =  18  could  be dispersed all over the file, and we have no idea how many such records exist.

Search with Range Selection:

The  entire  file  must  be  scanned  because  qualifying  records  could  appear anywhere in the file, and we do not know how many qualifying records exist.

The cost is B(D + RC).

Insert:

We assume that records are always inse rted at the end of the file.
We must fetch the last page in the file, add the record, and write the page back.
The cost is 2D +C

Delete:

We  must  find  the  record,  remove  the  record  from  the  page,  and  write  the modified page back.
We assume that no attempt is made to compact the file to reclaim the free space created by deletions, for simplicity.
The cost is the cost of searching plus C + D

.