Multi-level Indexes
Above Secondary 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.
|