Primary index in sequential order file organisation is also known as ______.

Question

Prepp Team · Accepted Answer

Understanding Primary Indexes in Sequential File Organization

In database systems, files containing data records are organized in various ways. One common method is sequential order file organization, where records are stored one after another based on the value of a primary key. To efficiently retrieve records from such a file, indexes are used. A primary index is a special type of index built on the primary key of the file.

Primary Index in Sequential Files

When a primary index is used with a file that is sequentially ordered on the primary key, the index does not need an entry for every single record in the data file. This is because the data records are already sorted according to the primary key.

Instead of pointing to every record, a primary index typically contains entries for blocks of records in the data file. Each index entry points to the first record in a specific data block. This structure helps in quickly locating the block containing the desired record, and then the system can sequentially scan that block to find the exact record.

Why it's called a Sparse Index

An index that does not have an entry for every search key value or every record in the data file is known as a sparse index. Since the primary index in a sequentially ordered file typically only has entries for blocks (or some other non-every-record granularity), it fits the definition of a sparse index. It is 'sparse' because there are fewer index entries than data records.

In contrast, a dense index has an index entry for every search key value (or every record). This is common for secondary indexes or primary indexes on files that are not sequentially ordered on the primary key, but it is not the standard structure for a primary index on a sequential file.

Comparing Sparse and Dense Indexes

Let's look at the key differences:

Feature	Sparse Index	Dense Index
Entries per Record	Fewer entries than data records (e.g., one entry per block)	Entry for every search key value/record
Size	Smaller	Larger
Lookup Speed	Requires sequential scan within a block after finding the block	Can often point directly to the record or block containing the record
เหมาะสมกับการใช้งาน	Primary index on sequential files	Secondary indexes, primary index on non-sequential files

Other Index Types (Briefly)

Clustering Index: An index where the order of records in the data file is the same as the order of the search key values in the index. A primary index on a sequentially ordered file is a type of clustering index because the data file is physically ordered by the primary key.
Non-Clustering Index: An index where the order of records in the data file is different from the order of search key values in the index. Secondary indexes are typically non-clustering.

While a primary index on a sequential file is also a clustering index, the term that describes its structure (specifically, the number of entries relative to records) is 'sparse'. Therefore, in the context of its structure in sequential file organization, it is known as a sparse index.

Conclusion

The primary index used in sequential order file organization is characterized by having fewer index entries than data records, typically one entry per data block. This structural property defines it as a sparse index.

Revision Table: Key Concepts

Concept	Description
Primary Index	Index built on the primary key of a file.
Sequential File Organization	Data records ordered physically by the primary key.
Sparse Index	Index with fewer entries than records, typically pointing to blocks.
Dense Index	Index with an entry for every record or search key value.

Additional Information: Indexing Techniques

Indexing is crucial for improving the performance of database queries. Different types of indexes and their implementation strategies are used depending on the file organization and query patterns.

Single-Level Index: The index file is a single level. Both dense and sparse indexes can be single-level.
Multi-Level Index: When the index file itself becomes too large, a hierarchical index structure can be created on top of the primary index. This forms a tree-like structure (like B+ trees), which are very common in modern database systems.
Secondary Indexes: Indexes built on attributes other than the primary key. These are almost always dense indexes.

Understanding the relationship between file organization and index structure, like why a primary index in a sequential file is sparse, is fundamental to understanding database performance.