Indexing

Posted on Updated on

What is an Index?

  • An index is a small table having only two columns. The first column contains a copy of the primary or candidate key of a table and the second column contains a set of pointers holding the address of the disk block where that particular key value can be found.
  • The advantage of using index lies in the fact is that index makes search operation perform very fast. Suppose a table has a several rows of data, each row is 20 bytes wide.
  • If you want to search for the record number 100, the management system must thoroughly read each and every row and after reading 99×20 = 1980 bytes it will find record number 100.
  • If we have an index, the management system starts to search for record number 100 not from the table, but from the index. The index, containing only two columns, may be just 4 bytes wide in each of its rows.
  • After reading only 99×4 = 396 bytes of data from the index the management system finds an entry for record number 100, reads the address of the disk block where record number 100 is stored and directly points at the record in the physical storage device. The result is a much quicker access to the record (a speed advantage of 1980:396).

Types of Index

1

Primary Index

  • In primary index, there is a one-to-one relationship between the entries in the index table and the records in the main table.
  • Primary index can be of two types:
    i) Dense primary index: the number of entries in the index table is the same as the number of entries in the main table. In other words, each and every record in the main table has an entry in the index.

2

ii) Sparse or Non-Dense Primary Index:
For large tables the Dense Primary Index itself begins to grow in size. To keep the size of the index smaller, instead of pointing to each and every record in the main table, the index points to the records in the main table in a gap. See the following example.

3

  • As you can see, the data blocks have been divided in to several blocks, each containing a fixed number of records.
  • The pointer in the index table points to the first record of each data block, which is known as the Anchor Record for its important function.
  • If you are searching for roll 14, the index is first searched to find out the highest entry which is smaller than or equal to 14. We have 11.
  • The pointer leads us to roll 11 where a short sequential search is made to find out roll 14.

Posted By-: Vissicomp Technology Pvt. Ltd.

Website -: http://www.vissicomp.com

This entry was posted in Programming in Java and tagged , , , , , , , , , , , .

Leave a comment