[prev] 7 [next]

Selection with Prim.Index

For one queries: 

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

Worst case:   read log2i index pages  +  read 1+Ov data pages.

Thus, Costone,prim  =  log2 i + 1 + Ov

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