Indexing and Hashing

Indexing and Hashing

AU: Dec.-11, Marks 6

• An index is a data structure that organizes data records on the disk to make the retrieval of data efficient.

• The search key for an index is collection of one or more fields of records using which we can efficiently retrieve the data that satisfy the search conditions.

• The indexes are required to speed up the search operations on file of records.

• There are two types of indices -

   • Ordered Indices: This type of indexing is based on sorted ordering values.

   • Hash Indices: This type of indexing is based on uniform distribution of values across range of buckets. The address of bucket is obtained using the hash function.

• There are several techniques of for using indexing and hashing. These techniques are evaluated based on following factors -

    • Access Types: It supports various types of access that are supported efficiently.

    • Access Time: It denotes the time it takes to find a particular data item or set items.

    • Insertion Time: It represents the time required to insert new data item.

    • Deletion Time: It represents the time required to delete the desired data item.

  • Space overhead: The space is required to occupy the index structure. But allocating such extra space is worth to achieve improved performance.

Example 4.4.1 Since indices speed query processing. Why might they not be kept on several search keys? List as many reasons as possible. AU: Dec.-11, Marks 6 

Solution: Reasons for not keeping several search indices include:

a. Every index requires additional CPU time and disk I/O overhead during inserts and deletions.

b. Indices on non-primary keys might have to be changed on updates, although an index on the primary key might not (as updates typically do not modify the primary key attributes).

c. Each extra index requires additional storage space.

d. For queries which involve conditions on several search keys, efficiency might not be bad even if only some of the keys have indices on them.

Therefore database performance is improved less by adding indices when many indices already exist.