How to choose indexing or hashing technique?

How to choose indexing or hashing technique? / Points to consider in choosing an index for your application / Evaluation of different structures / When to go for indexing or hashing?

How to choose an indexing or hashing technique?

No one index is best for indexing in database. It may vary for different database applications. Hence, choosing a technique is purely based on the database application in question that is going to use the said index. These indexing techniques can be evaluated for the required application on the basis of the following points;

• Access type – it is the types of access that are supported by the index. Some applications may need to find the records with a particular search key value, or a range of values. You may choose the index based on your requirement.

• Access time – it is the time to find items by a certain type of index. The time to search and find the record in question may differ for different applications for different indexes. 
• For example, if your application requires finding a single record with the primary key value as the search key, then ordered index would be a best choice for you.

• Insertion time – the time consumed to insert a record in a data file and also the time required to update the index file. 
• For example, let us assume that you insert a new record into your table and the search key value of your record does not exist in the index table. Then the time to insert a record would be,

• The time to insert a record into your data file + the time to insert an appropriate index entry.

• Deletion time – Same as above. The time to delete a record entry from the data file as well as the index file (if necessary). Unlike insertion, it needs to consider the time to locate (search) the record that is to be deleted as an extra time.

• Space overhead – Additional space required to handle index. 
• For example, if you like to use the index to locate your records easily, you have to load the index file into your memory first. It occupies some amount of space based on the size of the index file. Also, in some cases we may need to load more than one index file based on the application requirement.

Primary index sparse index

Primary index - Sparse index - Define sparse index - Give an example for sparse index - How to search for values using sparse primary index?

Sparse index

Index entry appears only for some of the records in the record file (data file). In other words, “One entry in the index file for each block of the data file”.

For example, you can observe from the given image that primary index consists of few entries as compared to dense index. [In the later case you will find entries for all the search key values that are part of the data file].

In sparse index, the index contains few entries, for example the first entry for each data block. Once if you are able to locate the first entry of that block, other entries are stored contiguously (continuously).

Sparse Index - Primary index - Example

Consider the following SQL query for searching certain register number;

SELECT * FROM students WHERE regno = ‘14MT59’;

To search for the record, we do not have any entries in index table for the value ‘14MT59’. To locate the record, we need to find the largest entry that is lesser than the search key value '14MT59'. We have such an entry with the value '14MS29' which is the largest but less than '14MT59'. Hence we take the pointer (address) of ‘14MS59’ and reach the first record in that block, then continue with sequential scan to find the actual record with the value ‘14MT59’.

Points to remember about sparse indexes

• Sparse indexes are used when the data file is too large and index entries are too large.

• Sparse index uses less space when compared to dense index.

• It takes more time to locate records (not always) than dense index.

• Records must be clustered for sparse index.

Go back

Primary index dense index

Primary index - Dense index / What is dense index? / Define Dense index / Dense index example

Dense Index

Index entry appears for every search key value in the record file (data file). In other words, “one entry in the index file for every record that is stored in the data file”.

For example, consider the figure (primary index) given below. You may find all the register numbers that are part of the data file as search key entries in the index file. This type of primary index is called as dense index. 

Primary index - Dense index

Points to remember about dense indexes:

• Every value of the key attribute of the data file has a representative entry in the appropriate dense index file. Hence the number of entries in the index file is equal to the number of records in the data file.

• The index maintains the key values in the same order as in the data file.

• It supports point queries, and range queries (if the look up attribute is the indexed attribute).

 






Go back

Secondary index

Secondary index / Secondary indexing / Non-clustering index / Non-clustered index

Secondary index

An index whose order of entries is different from the order of the data file is called as secondary index.

Another definition

A non-clustering, non-clustered, or secondary index specifies an order that is different from the file/table/relation’s sequential order.

Example

In this example, the left side table is the index table, and the right side is the Students table (Data file). The search key or the ordering key field in the index table is the Name of the students, which is neither primary key nor unique attribute of the students table. Name attribute is just an attribute in the students table. In our example, index is sorted on Name attribute, and Data file is sorted on regno attribute.

Secondary index - example

Points to know about secondary index:

• Secondary index must be a dense index

• Order of the search key values in the index file and the order of the actual records that are related to the index entries are in different order.

• Secondary Indexes facilitate query-answering on attributes other than primary keys – or, more generally, on non-ordering attributes.

• A file can have several secondary indexes.

 

Go back