Advanced Database Management System - Tutorials and Notes: Primary index sparse index

Search Engine

Please visit, subscribe and share 10 Minutes Lectures in Computer Science

Saturday, 21 November 2015

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


No comments:

Post a comment

Featured Content

Multiple choice questions in Natural Language Processing Home

MCQ in Natural Language Processing, Quiz questions with answers in NLP, Top interview questions in NLP with answers Multiple Choice Que...

All time most popular contents