[prev] 17 [next]

Multi-level Indexes

Above Sec.Index used two index files to speed up search
  • by keeping the initial index search relatively quick
  • Ix1 small (depends on number of unique key values)
  • Ix2 larger (depends on amount of repetition of keys)
  • typically, bIx1 ≪ bIx2
Could improve further by
  • making Ix1 sparse, since Ix2 is guaranteed to be ordered
  • in this case, bIx1 = ceil( bIx2 / ci )
  • if Ix1 becomes too large, add Ix3 and make Ix2 sparse
  • if data file ordered on key, could make Ix3 sparse

Ultimately, reduce top-level of index hierarchy to one page.