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.
|