Indexing & Hashing : MCQs & PYQs with Explanation

Option D

An Index in a database is a special data structure that helps the system locate records quickly without scanning the entire table.
Primary Indices correspond to the sequence of the data file itself, meaning the index key and the file are ordered the same way.
Secondary Indices have a search key order that is different from the sequential order of the data file. This allows access to data organized by non-primary keys, where the actual data storage is unrelated to the index ordering.

Option B

In file organization, different methods store and manage records differently, which affects the performance of operations like insert.
A Heap File Organisation stores records in no particular order. New records are simply placed in the first available space (usually at the end of the file). 
Since no sorting or searching is required before insertion, this makes the insert operation very fast.

Option B

ISAM stands for Indexed Sequential Access Method. It is a file organization method in which records are stored sequentially according to a key field, while an index is maintained to provide faster direct access to a particular record.
ISAM combines the advantages of sequential access and indexed access. In sequential access, records can be processed in their key order, while the index allows the system to locate a required record more quickly without searching the entire file.

Option C

The statement (I) is true because, in B+ trees, to maintain balance and efficient use of space, the number of children for each internal (non-leaf) node must be at least half of the maximum allowed children, up to the maximum n.
The statement (II) is false because, a clustering index is based on the order in which data records are stored physically. The search key for the clustering index is the attribute(s) on which the file is ordered, which may or may not be the primary key.
The statement (III) is true because, secondary indices typically maintain an index record for every tuple in the data file to provide quick access regardless of the clustering. Hence, secondary indices are dense meaning an index entry exists for every search-key value.
The statement (IV) is false because, by definition, a Dense Index has an index record for every search-key value in the data file. A Sparse Index has entries for only some search-key values.

Option A

DASD stands for Direct Access Storage Device. It refers to a storage device in which data can be accessed directly at a specific location, without having to read all the preceding data first. 
This makes direct access much faster for retrieving particular records. Examples of DASD include magnetic disks and other direct-access storage devices.

Option D

B+ Trees are widely used in DBMS for indexing because they maintain data in a balanced and sorted structure, which ensures efficient searching, insertion, and deletion.

• The B+ Trees are self-balancing, meaning all leaf nodes remain at the same level.
• In B+ Trees, actual data pointers are stored only in leaf nodes, while internal nodes store only keys for navigation.
• In B+ Trees, internal nodes and leaf nodes are different in structure. Internal nodes contain only keys and child pointers, whereas leaf nodes contain keys along with data pointers and are also linked sequentially.

Option D

Indexing is a technique used in a database to make the retrieval of records faster and more efficient. DBMS uses an index to locate the required records without scanning the entire data file.

• Indexing improves database performance by minimizing the number of disc visits required to fulfill a query.
• It is a data structure technique used to locate and quickly access data in databases.
• Indexing in database is used to reduce the I/O cost. The number of blocks transferred from secondary memory to primary memory is called I/O cost.

An index generally contains a search-key value and a pointer that helps locate the corresponding record or block of records.

Ordered Index:
An ordered index is an index in which the index entries are maintained in sorted order according to the search-key values.
Ordered indexes are particularly useful when we need to perform range searches, such as finding all students whose roll numbers are between 100 and 120.
Primary Index:
A primary index is an index created on a file that is physically ordered according to its primary key or ordering key. Means,

• DB file should be physically ordered based on search key used in the index file. AND
• Search key should be Primary Key or Alternative Key for DB file.

Suppose student records are stored according to Roll_No. as 101, 105, 110, 115, 120, 125.
If the file is physically arranged according to Roll_No, an index created on Roll_No is called a Primary Index.
Note:

• In the classical DBMS definition, a Primary Index is generally a Sparse Index because the data file is already ordered. Primary Index → Ordering Key → Usually Sparse.

Clustering Index:
A clustering index is an index used when the records in a file are physically ordered according to a non-key attribute, called the clustering field.

• A non-key attribute can contain duplicate values.

For example, consider employee records arranged according to Department:

Here, Department is a non-key attribute because several employees can have the same department. A clustering index can point to the beginning of each group:

Thus, instead of identifying a single record, the index helps locate a group of records having the same clustering-field value. Clustering Index → Non-key Ordering Field.

Secondary Index:
A secondary index is an index created on a search key that does not determine the physical ordering of the data file.
Suppose a student file is physically arranged according to Roll_No as 101, 102, 103, 104, 105, ...
Now suppose we frequently search students by their Name. An index can be created on Name, even though the actual data file is not physically ordered by Name. That index is called a Secondary Index.

Note:

• A secondary index is generally Dense Index, because the search key is not the ordering field of the data file. Secondary Index → Non-ordering Search Key → Usually Dense.
• We can build more than one secondary index according to requirement.
• In multi-level indexing, except first level, all other level of index is generally sparse.

Sparse Index:
A sparse index contains index entries for only some search-key values. In the classical primary-index arrangement, there is commonly one index entry for each data block.

A sparse index requires less storage than a dense index. After locating the appropriate block through the index, the DBMS may search within that block to find the required record.

Dense Index:
A dense index contains an index entry for every search-key value or, in the common record-level case, an entry for every record.

The main advantage of a dense index is that it can provide direct and fast access to records. The disadvantage is that it requires more storage space and more maintenance when records change.

The Dense and Sparse describe the density of index entries. Primary, Clustering, and Secondary describe the relationship between the index, search key, and physical file ordering.
Hash Index:
A hash index uses a hash function to determine the location of a record or bucket. Unlike an ordered index, the entries are not maintained primarily for sequential ordering. Instead, a search-key value is passed through a hash function.

• Hash indexing is particularly efficient for exact-match.

Static Hashing:
In static hashing, the number of buckets is fixed when the hash structure is created.
Dynamic Hashing:
In dynamic hashing, the hash structure can grow or adapt as the number of records changes.
This is useful for databases where records are frequently inserted or deleted. Instead of keeping a permanently fixed number of buckets, the structure can be adjusted as required.
Two important dynamic hashing techniques are, Extendible Hashing and Linear Hashing.

Option D

In an indexed file organization, the master list stores only key values along with their corresponding record numbers. Each record in the data file is assigned a unique record number, which helps the index quickly locate the actual record.

Option B

Accessing a disk block involves three main components:
Seek Time: The time taken for the disk arm to move the read/write head to the track where the desired block is located.
Rotational Delay (Latency): The time it takes for the disk platter to rotate so that the desired sector is under the read/write head.
Transfer Time: The time required to actually read or write the data once the head is in position.
All three components combined give the total time required to access a disk block.
Total Access Time = Seek Time + Rotational Delay + Transfer Time

Option C

In file organization, different methods are used to store and access records efficiently. A Hashed File Organization uses a hash function to directly compute the location of a record based on its key value. 
This means that instead of searching sequentially or traversing a structure, the system can directly jump to the required record.
Because of this direct access mechanism, Hashed Files provide very fast access to any arbitrary record, especially when the exact key is known.