How Does a Primary Index Speed Up DBMS Search?

TL;DR

A primary index applies when the stored data file is ordered and its search key contains unique values. It is generally sparse, keeping one anchor entry and pointer per disk block, which reduces pointer management while still locating the correct block efficiently. Binary search on the sorted index gives a stated search cost of log2 N plus one block access.

Transcript

Welcome to Gate Smashers Topic is Primary Index Primary index is only applied on data when if it follow 2 situations First condition is Data file that you're entering in hard disk because we want to store data permanent So when we store data permanently what option do we have storing in hard disk means storing in secondary memory So in secondary me... Read More

Key Insights

• A primary index is applicable when the data file is ordered and the chosen key values are unique. The physical file may be sorted in ascending or descending order, but both ordering and uniqueness must be present for the stated primary-index conditions.
• A primary key can cause a primary index to be applied automatically in the database examples discussed. Roll numbers and registration numbers are suitable search keys because each identifies one student rather than producing multiple possible matches.
• An index entry consists of a key value and a pointer. The key determines how a record is searched, while the pointer directs the search toward the data containing details such as a student's name, age, address, and family information.
• Unique numeric identifiers reduce ambiguity during retrieval. A train name such as Shatabdi or Rajdhani Express can correspond to multiple routes, while a train number identifies one entry, just as a student's roll number or registration number identifies one student.
• A primary index is generally sparse even though it can be made dense. A dense version would create as many index entries as data records, increasing the number of pointers that must be managed and therefore increasing management complexity.
• A sparse primary index stores one entry for each hard-disk data block. If blocks begin with keys 1, 5, 9, and 13, those values serve as anchor records whose pointers lead to their corresponding blocks.
• Anchor records define the ranges used to locate missing index keys. A search for 3 selects the block anchored by 1 because 3 lies between 1 and 5, while a search for 8 selects the block anchored by 5.
• Primary-index search uses binary search because the index data is sorted. The stated cost is log2 N plus 1, where N is the number of blocks in the index table, and the additional access retrieves full record details from the hard-disk block.

Questions & Answers

Q: What conditions are required for a primary index?

A primary index requires the permanently stored data file to satisfy two stated conditions. First, the file must be ordered, either in ascending or descending order. Second, the indexed field must contain unique key values. When the data is both ordered and unique, a primary index can be used to organize searches through keys and pointers.

Q: What information does a primary index entry contain?

A primary index entry contains two elements: a key value and a pointer. The key value is the identifier used during a search, such as a student roll number or registration number. The pointer directs the search to the relevant stored data, where details such as name, age, address, father name, or mother name can be retrieved.

Q: Why are unique identifiers useful for database searches?

Unique identifiers return one specific entry and avoid the ambiguity created by repeated names. The lecture compares searching for a train by name with searching by train number. Names such as Shatabdi or Rajdhani Express can produce several route options, while a train number identifies one entry. Student roll numbers and registration numbers serve the same purpose.

Q: Is a primary index dense or sparse?

A primary index can be created as either dense or sparse, but it is generally made sparse. A dense index would contain the same number of entries as the data file, requiring many pointers to be maintained. A sparse index reduces that complexity by recording one anchor key and one pointer for each hard-disk data block.

Q: How many entries does a sparse primary index contain?

The number of entries in a sparse primary index equals the number of data blocks on the hard disk. Each data block contributes one anchor record to the index table, along with a pointer to that block. This arrangement uses fewer index entries and pointers than a dense index, which would represent every individual data record.

Q: What is an anchor record in a primary index?

An anchor record is the first indexed key associated with a data block, and it acts as that block's representative or leader. In the example, blocks begin with values 1, 5, 9, and 13, so those values become anchors. Each anchor has a pointer leading from the index table to its corresponding hard-disk block.

Q: How does a sparse primary index find a missing key?

A sparse index finds the range containing the requested key, even when that exact key is absent from the index table. For example, 3 is greater than anchor 1 and less than anchor 5, so it is searched in the block beginning with 1. Likewise, 8 lies between 5 and 9, so its block begins with 5.

Q: What is the search time for a primary index?

The lecture states the search cost as log2 N plus 1, or asymptotically as order log N, where N is the number of blocks in the index table. Binary search applies because the index is sorted. The additional one represents accessing the selected hard-disk block after the index pointer identifies where the full record details are stored.

Summary & Key Takeaways

• A primary index is used for a data file stored permanently in secondary memory when two conditions hold: the file is ordered, either ascending or descending, and the indexed search key is unique. Roll numbers, registration numbers, and train numbers illustrate identifiers that can return one specific record.

• Each index entry contains a key value and a pointer to stored data. Although a primary index can be dense, it is generally sparse to avoid maintaining an entry and pointer for every record. A sparse index instead stores one anchor key for each physical data block on the hard disk.

• Searching a sparse primary index first identifies the interval containing the target key. For example, a value between anchor keys 1 and 5 belongs to the block beginning with 1. Because index data is sorted, binary search can be applied, followed by one access to the selected disk block.