Indexes in Database management

DEFINITION

An Index is a copy of database table that has been reduced to certain fields and the copy is always in sorted form. The index also contains a pointer to the corresponding record of the actual table so that the fields not contained in the index can also be read. Index contains a value and a pointer to first record that contains data value.

A Database Index is a data structure that speeds up certain operation on a file. The Operation involves a search key which is the set of record files( in most cases a single field). The elements of an index are called data entries. Data entries can be actual data record. A given file of data records can have several indexes, each with different search keys as showed in the table below.

The search engine searches for a value in table or file in two ways. The table scan which is sequential and index which is random.

Indexes are special lookup tables that the database engine uses to speed up data retrieval. An index in a database is similar to an index in the back of a book.

An index table or file consists of records called index entries. It is of the form

The search key field is used to sort the rows (in the index column) and the pointer field (in index column) indicates where the actual data in the table will be retrieved. When a table has an index it simply means the records in that table has been sorted in one way or the other.

Indexes are automatically created when primary key and unique constraints are defined on table columns.

EVALUATION

1. What is an index?

2. What are data entries?

INDEX CLASSIFICATION

Index can be classified as either clustered or unclustered.

CLUSTERED

Clustered index is an index whose sorting order determines the order of how the rows/records in a table are stored. There could be only one clustered index in a table because there could always be one way of arranging the records in a table at a given time. For example, if you are asked to arrange some tables in a room, you could arrange them in a round form, row form or packed them close together, only one way at a time. Clustered index also means that related values in a table are stored close to each other according to the order of the index.

1. CLUSTERED INDEX

A Clustered index is when a file is organized so that the ordering of data  records is the same as or closes to the ordering of data entries. A clustered index can take place only if the data records are sorted on the search key field. For example, suppose that students records are sorted by age; an index on age that stores data entries in sorted order by age is a clustered index.

Indexes that maintain data entries in sorted order by search key use a collection of index entries, organized into a tree structure to guide searches for data entries. Thus, clustered indexes are relatively expensive to maintain when the file is updated, when data entries are to be moved across pages, and if records are identified by a combination of page id and slot as is often the case, all places in the database that point to a moved record must also be updated to point to the new location.These additional updates can be time consuming.

The table below illustrate a clustered index file:

• UNCLUSTERED INDEX

This  an index whose sorting order does not determine the order of how the rows/records in a table are stored. This means that the search keys in the index column is sorted in one order while the actual records or rows are sorted in another order or are not sorted at all.

This is an index that is not clustered. A data file can contain several unclustered index. For example, supposing that students records are sorted by age; and if  additional index on gpa field is included, it is called unclustered index.

GENERAL EVALUATION

(1)Explain a database index

(2) Explain clustered index versus unclustered index.

READING ASSIGNMENT

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

WEEKEND ASSIGNMENT

1. ………. is a database table that has been reduced to certain fields.a) Table  b) An index c) Table model d) Network model
2. The copy of an index is always in  …… form.  a) duplicate b) field c) sorted  d) domain
3. The …………index can take place only if the data records are sorted on the search key field. a)unclustered b)insert c) update  d) clustered
4. A …………….. can contain several unclusterd indexes a) data file b) primary c) check d) index
5. Index contain a value and  ……. a)pointer b) sign c) update d) model

THEORY

1. Differentiate between clustered index and unclustered index.
2. State two reasons why clustered index is expensive to maintain.
3. What is an index?

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 column has a particular record it will point to in the table or file.

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?.

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