[prev] 3 [next]

Indexes (cont)

Indexes themselves may be structured in several ways:

dense every tuple is referenced by an entry in the index file
sparse only some tuples are referenced by index file entries
single-level tuples are accessed directly from the index file
multi-level may need to access several index pages to reach tuple

Index file has total i pages   (where typically i ≪ b)

Index file has blocking factor ci   (where typically ci ≫ c)

Dense index:  i = ceil( r/ci )     Sparse index:  i = ceil( b/ci )