# DENSE VERSUS SPARSE INDEXES

DENSE INDEX This is said to be dense if it contains (at least) one data entry for every search key value that appears in a record in the indexed file. In a dense index, index record appears for every search key value in the file or table. That is every search key in the index […]

## DENSE INDEX

This is said to be dense if it contains (at least) one data entry for every search key value that appears in a record in the indexed file. In a dense index, index record appears for every search key value in the file or table. That is every search key in the index column has a particular record it will point to in the table or file.

For example,

 10101 12121 15151 22222 32343
 10101 OJO Maths 90000 12121 ANYAOGU DP 75000 15151 ROBERT ICT 65000 22222 ADEREMU Computer 60000 32343 TUNDE Music 50000

From the figure above, we can see that each search key in the index has a particular record that it point to in the base table

## SPARSE INDEX

In a sparse index, each search key does not have a corresponding record it point to but may point to a group of records in the base table. For example:

 10101 22222 32343
 10101 OJO Maths 90000 12121 ANYAOGU DP 75000 15151 ROBERT ICT 65000 22222 ADEREMU Computer 60000 32343 TUNDE Music 50000

From the figure above, search keys such as 12121, 15151 do not have corresponding records in the index but you can search for them through 10101 key to retrieve their records in the base table.

A Sparse Index contains one entry for each page of records in the data file. The index record contains the search key and a pointer to the first data record with that search key value. A Sparse index must be clustered and it is smaller than a dense index.

## PRIMARY AND SECONDARY INDEX

### PRIMARY INDEX

Primary index is an index defined on a primary key column(s) of a relation with unique constraint which guarantee that the field will not contain duplicate values and determine the order of how the records are physically stored on the disk. Note that this is also called clustered index.

This is an index on a set of fields that includes the primary key. Primary index contains records that are usually clustered. A primary index is created for the primary key of a table.

### SECONDARY INDEX

Secondary index is an index defined on a non-key field which may contain duplicate values and as such does not determine the order of how the records are physically stored on a disk. It is also called non-clustered index.

For example, in student database, student ID is used to look up for a student as the key, however, one might want to look up for a student using LastName by creating secondary index on that column.

Secondary index is an index that is not a primary index i.e. it does not include primary key. Secondary index can be created on non- key attribute. It contains duplicate data entries. A Unique index is an index in which the search key contains some candidate key.

### EVALUATION

1. Distinguish between dense index and sparse index
2. Explain primary and secondary index

## INDEXES USING COMPOSITE SEARCH KEYS

Composite search keys or concatenated keys are when the search key for an index contain several fields. For example, considering a collection of employee records with field name, age and salary stored in sorted order by name. if the search key is composite, an equality query is one in which each field in the search key is bound to a constant. For example, we can ask to retrieve all data entries with age = 20 and sal = 10, the hashed file organization supports only equality queries since a hash function identifies the bucket containing desired records only if a value is specified for each field in the search key.

The search key for an index can contain several fields, such keys are called Composite Search Keysor Concatenated Keys.

Range Queryis the one in which not all fields in the search key are bound to constants. For example, we can ask to retrieve all data entries with age = 20; this query implies that any value is acceptable for the sal _eld. Another example of a range query is when ask to retrieve all data entries with age < 30 and sal> 40

## GENERAL EVALUATION

1. Differentiate between a unique index and a range query.
2. What is the difference between primary and secondary indexes?.

## WEEKEND ASSIGNMENT

1. ………. is an index in which the search key contains some candidate key. a) Unique index  b) An index  c) composite  d) sparse index
2. …… can be created on a non- key attribute.  a) primary index b) dense index   c) secondary index  d) sparse index
3. A sparse index contains one entry for each ……of records in the data file. a) page b) table c) row  d) column
4. ………is the one in which not all fields in the Search key are bound to constant. a) dense index b) composite search key c) secondary index d) range query
5. ……. is when the search key for an index contain several fields. a) primary index b) composite search key c) secondary index d) unique index

## THEORY

1. Create a student table with the following fields: name, age, and scores of 5 records. Create an index using a composite keys name and age. (show the table and SQL statements)
2. Discuss the different types of indexing.
3. Differentiate between a unique index and a range query.
4. What is composite search key?

INDEXES

SS 3 Data Processing Revision

APPLICATION SOFTWARE

ART OF INFORMATION PROCESSING

COMPUTER HARDWARE & SOFTWARE