Index Scans

Equality on Key

• to retrieve a single record that satisfy equality predicate \(\theta\)
• \(\omega = h_i * (t_t + t_s) + t_s + t_t\)
• all blocks of the index table are loaded into the memory, then a seek is done to fetch the one matching the index.

Equality on Non-Key

• to retrieve \(n\) records that match general predicate \(\theta\)
• \(\omega = h_i * (t_T + t_S) + t_S + t_T * n\)
• assuming seek has to be done only once because blocks are adjacent

Secondary Index - Single Key

• \(\omega = (h_i+1)*(t_T+t_S)\)
• cost to load the index table into the memory, then to seek and fetch the desired element.

Secondary Index - Non-Key

• \(\omega = (h_i + n)*(t_T + t_S)\)
• this scenario is assuming that each of the non-key records is in a different block. in this scenario, it can be quite expensive.