Indexes: Dense versus Sparse, Primary and Secondary Indexes, Indexes using Composite Search Keys

Back to: DATA PROCESSING SS 3

 

Welcome to class! 

In today’s class, we will be talking about indexes: dense versus sparse, primary and secondary indexes, indexes using composite search keys. Enjoy the class!

Dense Versus Sparse 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:

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

Sparse index

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

 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:

The primary index is an index defined on a primary key column(s) of relation with a unique constraint which guarantees 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. A primary index contains records that are usually clustered. A primary index is created for the primary key of a table.

Secondary index:

The 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 the non-clustered index.

For example, in the 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 a secondary index on that column.

A secondary index is an index that is not a primary index i.e. it does not include a primary key. A secondary index can be created on a 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 the dense index and sparse index
2. Explain primary and secondary index

Index using the composite search key

Composite search keys or concatenated keys are when the search key for an index contains 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 Keys or Concatenated Keys.

Range Query is 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?.

Reading assignment

Understanding Data Processing for Senior Secondary Schools by Dinehin Victoria, Page 254.

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 a composite search key?

 

In our next class, we will be talking about Maintenance of Computer: Computer Hardware, Process Of Maintaining Hardware.  We hope you enjoyed the class.

Should you have any further question, feel free to ask in the comment section below and trust us to respond as soon as possible.

Get more class notes, videos, homework help, exam practice on Android [DOWNLOAD]

Get more class notes, videos, homework help, exam practice on iPhone [DOWNLOAD]