Ordered Indices

Ordered Indices

Primary and Clustered Indices

Primary index :

• An index on a set of fields that includes the primary key is called a primary index. The primary index file should be always in sorted order.

• The primary indexing is always done when the data file is arranged in sorted order and primary indexing contains the primary key as its search key.

• Consider following scenario in which the primary index consists of few entries as compared to actual data file.

• Once if you are able to locate the first entry of the record containing block, other entries are stored continuously. For example if we want to search a record for Reg No 11AS32 we need not have to search for the entire data file. With the help of primary index structure we come to know the location of the record containing the RegNo 11AS30, now when the first entry of block 30 is located, then we can easily no rig locate the entry for 11AS32.

• We can apply binary search technique. Suppose there are n = 300 blocks in a main data file then the number of accesses required to search the data file will be log₂n+ 1 = (log₂ 300) + 1≈9

• If we use primary index file which contains at the most n = 3 blocks then using binary search technique, the number of accesses required to search using the primary index file will be log₂ n+1= (log₂ 3)+1=3

• This shows that using primary index the access time can be deduced to great extent.

Clustered index:

• In some cases, the index is created on non-primary key columns which may not be unique for each record. In such cases, in order to identify the records faster, we will group two or more columns together to get the unique values and create index out of them. This method is known as clustering index.

• When a file is organized so that the ordering of data records is the same as the ordering of data entries in some index then say that index is clustered, otherwise it is an unclustered index.

• Note that, the data file need to be in sorted order.

• Basically, records with similar characteristics are grouped together and indexes are created for these groups.

• For example, students studying in each semester are grouped together. i.e.; 1st semester students, 2nd semester students, 3rd semester students etc. are grouped.

Dense and Sparse Indices

There are two types of ordered indices :

1) Dense index:

• An index record appears for every search key value in file.

• This record contains search key value and a pointer to the actual record.

• For example:

2) Sparse index:

• Index records are created only for some of the records.

• To locate a record, we find the index record with the largest search key value less than or equal to the search key value we are looking for.

• We start at that record pointed to by the index record, and proceed along the pointers in the file (that is, sequentially) until we find the desired record.

• For example -

Single and Multilevel Indices

Single level indexing:

• A single-level index is an auxiliary file that makes it more efficient to search for a record in the data file.

• The index is usually specified on one field of the file (although it could be specified on several fields).

• Each index can be in the following form.

• The index file usually occupies considerably less disk blocks than the data file because its entries are much smaller.

• A binary search on the index yields a pointer to the file record.

• The types of single level indexing can be primary indexing, clustering index or secondary indexing.

• Example: Following Fig. 4.7.5 represents the single level indexing -

Multilevel indexing:

• There is an immense need to keep the index records in the main memory so as to speed up the search operations. If single-level index is used, then a large size index cannot be kept in memory which leads to multiple disk accesses.

• Multi-level Index helps in breaking down the index into several smaller indices in order to make the outermost level so small that it can be saved in a single disk block, which can easily be accommodated anywhere in the main memory.

• The multilevel indexing can be represented by following Fig. 4.7.6.

Secondary Indices

• In this technique two levels of indexing are used in order to reduce the mapping size of the first level and in general.

• Initially, for the first level, a large range of numbers is selected so that the mapping size is small. Further, each range is divided into further sub ranges.

• It is used to optimize the query. processing and access records in a database with some information other than the usual search key.

For example -

Review Questions

1 Illustrate indexing and hashing techniques with suitable examples.  AU: Dec.-15, Marks 8

2. What is the use of an index structure and explain the concept of ordered indices.  AU: Dec 04, Marks 8

3. What is the difference between primary index and secondary index?  AU: May 06, Marks 8

4. Explain the index schemas used in database systems.