Week 07 Lecture (19)

Select with ML.Index

For one query on indexed key field:

I = top level index page
for level = 1 to d {
    read index page I
    search index page for J'th entry
        where index[J].key <= K < index[J+1].key
    if J=0 { return NotFound }
    I = index[J].page
}
-- I is now address of data page
search page I and its overflow pages

Read d index blocks and 1+Ov data blocks.

Thus, Cost_one,mli = (d + 1 + Ov)_r

(Note that d = ceil( log_{c_i} r ) and c_i is large because index entries are small)