Week 06 Lectures (21)

Select with Multi-level Index

For one query on indexed key field:

xpid = top level index page
for level = 1 to d {
    read index entry xpid
    search index page for J'th entry
        where index[J].key <= K < index[J+1].key
    if (J == -1) { return NotFound }
    xpid = index[J].page
}
pid = xpid  // pid is data page index
search page pid and its overflow pages

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)