Week 06 Lectures (12)

Selection with Primary Index

For one queries:

ix = binary search index for entry with key K
if nothing found { return NotFound }
b = getPage(pageOf(ix.tid))
t = getTuple(b,offsetOf(ix.tid))
   -- may require reading overflow pages
return t

Worst case: read log₂i index pages + read 1+Ov data pages.

Thus, Cost_one,prim = log₂ i + 1 + Ov

Assume: index pages are same size as data pages ⇒ same reading cost