Order Indices

Indexing

Indexing mechanisms are specialized to speed up access to desired data. For example author catalog in the library. Search key refers to an attribute to set of attributes used to look up records in a file. An index file consists of records which are called index entries of the form

Index files are typically much smaller than the original file. There are two basic kinds of indices and they are:

• Ordered Indices: In ordered indices, the search keys are stored in sorted order.
• Hash Indices: In hash indices, search keys are distributed uniformly across "buckets" using a "hash function".

Index Evaluation Metrics:

• Access type:The process of finding records with a specified attribute value and also the records whose attribute values fall within a specified range is called as access type.
• Access time: It is a time to find a particular value.
• Insertion time: It is a time to insert new value as well as to update the index structure.
• Deletion time: It is a time to delete data item as well as to update the index structure.
• Space overhead: It is referred to as an additional space occupied by index structure.

Ordered Indices

In an ordered index, index entries are stored sorted on the search key value. For example:- Author catalog in the library. There are two types of order index and they are:

• Primary Index
• Secondary Index

The primary index is referred to an index whose search key specifies the sequential order of the file in a sequentially ordered file. It is also called as clustering index. The search key of a primary index is usually but not necessarily the primary key. Primary index is of two types:

• Dense Index
• Sparse Index

Dense Index:

In the dense index, the index record has appeared for every search-key value in the file. The index record contains search-key value and a pointer to the first data record with that search value. Rest of the records with the same search key value would be stored sequentially after the first record.

Sparse Index:

The sparse index contains index records for only some search-key values. The sparse index is applicable when records are sequentially ordered on search-key. In order to locate a record with search-key value 'K' we:

• Find index record with largest search-key value < 'K'.
• Search file sequentially starting at the record to which the index record points.

In comparison to dense indices, sparse indices require less space and less maintenance overhead for insertions and deletions. Generally, the sparse index is slower than the dense index for locating records.

Multi-level Index:If the primary index does not fit in memory access becomes expensive. The solution for this is to treat primary index as a sequential file that is kept on a disk and constructs a sparse index on it.

• The outer index is a sparse index of a primary index.
• The inner index is the primary index file.

If even outer index is quite large to fit in main memory another level of the index can still be created and the process is repeated. Indices must be updated on insertion or deletion from the files at all levels.

Secondary Indices

A secondary index is an index whose search key specifies an order different from the sequential order of the file. It is also called as the non-clustering index. Frequently one wants to find all the records whose values in a certain field (not the search-key of the primary index) satisfy some condition.

• Example 1: In the account relation that is stored sequentially by account number, we may want to find all the accounts in a particular field.
• Example 2: Same as above but where we want to find all accounts with a specified balance or range of balances.

We may have a secondary index with an index record for each search key value. A secondary index must contain pointers to all the records. Index record points to a bucket that contains pointers to all the actual records with that particular search-key value. Secondary indices have to be dense.

References:

1. H.F.Korth and A. Silberschatz,"Database system concepts",McGraw Hill,2010
2. A.K.Majumdar and p, Bhatt acharya,"Database Management Systems",Tata McGraw Hill,India,2004
3. F.Korth, Henry. Database System Concepts. 6th edition.