Heap File with Unclustered Tree Index

Heap File with Unclustered Tree Index

Scan:

To  do  a  full scan of  the file  of employee records,  we  can scan the  leaf level of the index and  for  each  data  entry,  fetch  the  corresponding  data  record  from  the underlying  file, obtaining data records in the sort order (age, sal).

We can read all data entries at a cost of O.15B(D + 6.7RC) l/Os.

Search with Equality Selection:

We assume that the equality selection matches the sort order (age, sal).

We can  locate the  first  page  containing  the desired data entry  or entries by  fetching  all pages from the root to the appropriate leaf.

Each step requires a disk I/O and two comparisons.

Once  the page  is known,  the  first qualifying data  entry  can again  be located by a binary search of the page at a cost of Clog6.7R.2

The first qualifying data record can be fetched  from  the  employee file with another I/O.

The  cost  is  DlogO.15B  +  Clag6.7R  +  D,  which  is  a  significant  improvement  over searching sorted files.

Search with Range Selection:

Data  entries  are sequentially  retrieved  until  a data  entry  is  found  that  does  not satisfy the range selection.

  

For  each  qualifying  data  entry,  we  incur  one  I/O  to  fetch  the  corresponding  employee records.

The cost  can quickly become  prohibitive as  the number of records that satisfy the range selection increases.

As a  rule of  thumb,  if  10 percent of  data records satisfy  the  selection  condition, we  are better  off  retrieving  all  employee  records,  sorting  them,  and  then  retaining  those  that satisfy the selection.

Insert:

We must first insert the record in the employee heap file, at a cost of 2D + C.

In addition, we must insert the corresponding data entry in the index.

Cost      S + 2

Delete:

We need to locate the data record in the employee  file and the data entry in the index.

We need to write out the modified pages in the index and the data file .

Cost      S + 2

.