Saturday, 20 April 2013

Dense, Sparse and Multilevel Indices

Dense indices:
Think that we have a database file. That file has an index and a record. The index is A, B, C and the record is A, B, B, C. In the record (A, B, B, C) , the index file has every value (A, B, C). If a index file has all search key value we call it Dense index. See the example below

Dense index must have all key but in sparse index has only some key values.
Sparse index:
Sparse index contains only some search key value. It applicable when records are sequentially ordered on search key. To search the key C, at first we search largest value in index file by comparing this <=C. So the value is B. Then we search sequentially starting at the record to which the index record points.
Multilevel Index:
Even if we use a sparse index, the index itself may become too large for efficient processing when the database has thousands of rows. Indices with two or more levels are called multilevel indices. Multilevel indexing are closely related to tree structure.
A typical dictionary is an example of a multilevel index in the non database  world.

No comments:

Post a Comment