📚 INDEXING STRUCTURES FOR FILES

📚 INDEXING STRUCTURES FOR FILES

Primary Index • Secondary Index • Clustering Index

📘 What is Indexing?

An index is an additional data structure used by a DBMS to locate records more efficiently. Instead of examining every record in a file, the DBMS can use the index to find the approximate location of the required record.

SEARCH KEY ↓ INDEX ↓ RECORD / BLOCK LOCATION ↓ DATA

Simple Example:

Suppose a student file contains 10,000 records. Without an index:
Search → Examine many records

With an index:
Search → Index → Required block → Record

📚 Indexing Structures

An indexing structure provides an efficient access path to records stored in a database file. The main structures covered here are:

1. Primary Index
2. Secondary Index
3. Clustering Index

DATABASE FILE ↓ INDEX ↓ BLOCK / RECORD LOCATION

Main objective: Reduce the amount of data that must be examined to locate the required records.

🔑 Primary Index

A primary index is an index built on an ordered data file whose ordering field is the primary key. The data records are stored according to the primary key order.

Example

Student_ID	Name	Marks
101	Rahul	85
105	Anita	91
110	Suman	88
115	Arjun	79

The file is ordered by Student_ID.

Primary Index

101 → Block 1
110 → Block 2

A primary index is commonly implemented as a sparse index, where an index entry may point to a block rather than every individual record.

🔎 Secondary Index

A secondary index is an additional index created on a field that is not the ordering field of the data file. It provides an alternative access path.

Example

Suppose the file is ordered by Student_ID:

101 → 105 → 110 → 115

Now we want to search students using Name.

Rahul → Record 101
Anita → Record 105
Suman → Record 110
Arjun → Record 115

The Name index provides another way to locate records, even though the actual file is ordered by Student_ID.

🗂️ Clustering Index

A clustering index is an index built on an ordering field that is not necessarily a unique key, where records having the same value are grouped together. The ordering field is called the clustering field.

Example

Suppose student records are physically grouped according to Department.

BCA → BCA → BCA ↓ BBA → BBA ↓ BSC → BSC → BSC

A clustering index can point to the first block containing records for each distinct department value.

Clustering is especially useful when records with the same field value are frequently accessed together.

📋 Primary Index Example

Data File

Block	Student_ID	Name
Block 1	101, 103	Rahul, Anita
Block 2	105, 108	Suman, Arjun
Block 3	110, 115	Riya, Karan

Primary Index

Search Key	Pointer
101	Block 1
105	Block 2
110	Block 3

The index points to blocks containing ranges of Student_ID values.

📋 Secondary Index Example

Suppose the actual file is ordered by Student_ID.

101 → 103 → 105 → 108 → 110

Now create an index on Department.

Department	Record / Pointer
BCA	101, 105, 110
BBA	103
BSC	108

Because the file is not physically ordered by Department, the Department index is a secondary access path.

📋 Clustering Index Example

Suppose records are physically arranged by Department.

Block	Department	Students
Block 1	BCA	101, 102, 103
Block 2	BCA	104, 105
Block 3	BBA	201, 202
Block 4	BSC	301, 302, 303

Clustering Index

Department	Starting Block
BCA	Block 1
BBA	Block 3
BSC	Block 4

The index directs the DBMS to the beginning of each cluster of records.

🔍 How Index Searching Works

The basic idea is: Search key → Index → Pointer → Data Block → Record

Example: Search Student_ID = 110

1

DBMS receives Student_ID = 110.

2

DBMS searches the primary index.

3

The index indicates Block 3.

4

DBMS reads Block 3.

5

The required record is located.

110 ↓ PRIMARY INDEX ↓ BLOCK 3 ↓ RECORD 110

The index reduces unnecessary examination of the entire file.

🎯 Primary Index — Step-by-Step

1

The data file is ordered according to the primary key.

2

The DBMS creates index entries based on the ordered file.

3

Each index entry contains a search-key value and a pointer.

4

The pointer identifies the relevant block.

5

The DBMS accesses the block and finds the required record.

PRIMARY KEY ↓ PRIMARY INDEX ↓ DATA BLOCK ↓ RECORD

🎯 Secondary Index — Step-by-Step

1

The data file already has an ordering based on another field.

2

A different field is selected for additional searching.

3

An index is created for that field.

4

The index stores pointers to matching records or blocks.

5

The DBMS uses this index when queries use that field.

SECONDARY FIELD ↓ SECONDARY INDEX ↓ POINTER ↓ RECORD

🎯 Clustering Index — Step-by-Step

1

Select a clustering field.

2

Physically arrange records according to that field.

3

Records with the same value form a cluster.

4

Create an index entry for each distinct clustering value.

5

Store a pointer to the beginning of the corresponding cluster.

BCA → Block 1
BBA → Block 3
BSC → Block 4

When the DBMS searches for BCA records, it can jump directly to the beginning of the BCA cluster.

⭐ Advantages of Indexing

✔ Faster record retrieval

✔ Reduces the amount of data that must be scanned

✔ Provides multiple access paths

✔ Useful for large database files

✔ Helps improve query performance

✔ Can efficiently support different search requirements

Specific Advantages

Index	Main Advantage
Primary Index	Efficient access using primary ordering key
Secondary Index	Provides an additional search path
Clustering Index	Efficient access to groups of related records

⚠️ Disadvantages of Indexing

❌ Indexes require additional storage.

❌ Indexes must be maintained when data changes.

❌ INSERT operations can require index updates.

❌ DELETE operations can require index updates.

❌ UPDATE operations may require index maintenance.

❌ Too many indexes can increase maintenance overhead.

MORE INDEXES ↓ MORE SEARCH OPTIONS BUT ↓ MORE STORAGE + MORE MAINTENANCE

⚖️ Primary vs Secondary vs Clustering Index

Feature	Primary Index	Secondary Index	Clustering Index
Based On	Primary key / ordering key	Non-ordering search field	Ordering field that groups records
Data File Ordering	Ordered by index key	Not necessarily ordered by index field	Ordered by clustering field
Key Unique?	Usually primary key is unique	May be unique or non-unique	Usually non-unique
Purpose	Fast primary-key access	Alternative access path	Access groups of related records
Typical Structure	Often sparse	Often dense	Often one entry per distinct value
Example	Student_ID	Name	Department

🏫 Complete Example

Student Database

Student_ID	Name	Department	Marks
101	Rahul	BCA	85
102	Anita	BCA	91
103	Suman	BBA	78
104	Arjun	BCA	88
105	Riya	BSC	92

🔑 Primary Index

Student_ID ↓ 101 → Block 1 102 → Block 1 103 → Block 2 104 → Block 2 105 → Block 3

🔎 Secondary Index

Name ↓ Anita → Record 102 Arjun → Record 104 Rahul → Record 101 Riya → Record 105 Suman → Record 103

🗂️ Clustering Index

BCA → Records 101, 102, 104
BBA → Record 103
BSC → Record 105

Remember:

Primary Index → Primary ordering key

Secondary Index → Additional search field

Clustering Index → Grouped records based on an ordering field

❓ Important Questions & Answers

Q1. What is indexing in DBMS?

Indexing is a technique that creates an additional access structure to help the DBMS locate records more efficiently.

Q2. What is a primary index?

A primary index is an index on an ordered data file whose ordering field is the primary key.

Q3. What is a secondary index?

A secondary index is an additional index that provides an alternative access path on a field that is not the ordering field of the data file.

Q4. What is a clustering index?

A clustering index is built on an ordering field that groups records having the same value together.

Q5. Is a clustering field necessarily unique?

No. A clustering field commonly contains duplicate values. Records with the same value are grouped into clusters.

Q6. Why is a secondary index required?

It provides an alternative way to locate records using a field other than the field used for physical ordering.

Q7. Give an example of a primary index.

If a student file is ordered by Student_ID and Student_ID is the primary key, an index on Student_ID is a primary index.

Q8. Give an example of a secondary index.

If a student file is ordered by Student_ID but an additional index is created on Name, the Name index is a secondary index.

Q9. Give an example of a clustering index.

If student records are physically grouped according to Department, an index on Department can be a clustering index.

Q10. What is the main disadvantage of indexing?

Indexes require extra storage and must be maintained when records are inserted, deleted or updated.

Q11. Which index provides an alternative access path?

A secondary index provides an additional or alternative access path to the data.

Q12. Which index is useful for accessing groups of records?

A clustering index is useful when records having the same clustering-field value are stored together.

B.K. PAUL

Bhairab Ganguly College

DBMS • File Indexing • Primary Index • Secondary Index • Clustering Index

Interactive Learning Module