Q7Data Base Management System

(a) Hash file organization and hash index

In hash file organization, records of a file are physically distributed among a fixed number of buckets, where each bucket typically corresponds to one or more disk blocks. The bucket in which a given record is stored (and later retrieved) is determined by applying a hash function h to the record's key field(s); the hash function typically computes an integer in the range 0 to (number of buckets - 1) and the record is placed in the bucket with that number. Because the address of a record's bucket can be computed directly from its key without any sequential search, hash file organization provides average-case O(1) direct access for equality lookups, insertions, and deletions, in contrast with the O(log n) or O(n) access typical of ordered or unordered files.

For example, suppose EmpID values are hashed using h(EmpID) = EmpID mod 10, giving 10 buckets numbered 0 to 9. An employee with EmpID 253 hashes to bucket 3 (253 mod 10 = 3), and is stored in that bucket; to retrieve the record later, the DBMS simply recomputes h(253) = 3 and reads bucket 3 directly, without scanning the rest of the file. If two different keys hash to the same bucket (a collision), the extra records are typically stored using an overflow chain of additional blocks linked to that bucket.

A good hash function is essential to the performance of hash file organization: it should distribute keys as uniformly as possible across all available buckets, so that no single bucket becomes overloaded while others remain empty, and it should be inexpensive to compute since it is evaluated on every insert, delete, and lookup. Simple modulo-based functions like key mod M work well when key values themselves are reasonably uniform, but for non-numeric or skewed keys, a folding or digit-extraction technique is often applied first to spread the key's bits more evenly before taking the modulo. Hash file organization is best suited to workloads dominated by exact-match (equality) lookups, since the hash function gives no useful information about the relative order of keys; queries requiring a range of values (such as all EmpIDs between 100 and 200) cannot exploit the hash structure at all and would require a full file scan, which is the key limitation of hashing compared to ordered/indexed file organizations for range queries.

A hash index is an index structure - distinct from hash file organization of the data records themselves - that uses a hash function to map key values to the addresses of buckets containing pointers to the actual records, rather than storing the full records in hash buckets directly. A hash index is an auxiliary access structure built on top of any file organization (heap, sorted, or otherwise): given a search key value, the hash function is applied to compute the bucket number, and that bucket holds (key, record-pointer) entries for all records whose key hashes to it, allowing quick lookup of the pointer, followed by a direct read of the actual record from wherever it is stored.

(b) Primary index vs secondary index

A primary index is built on the ordering key field of a file whose records are physically stored in sorted order by that same field (a sequential/sorted file). Because the data file is already sorted on this field, the index does not need an entry for every single record - instead it is a sparse index, typically containing one index entry per block of the data file (the entry holding the smallest or first key value in that block, together with the block's address). To find a record, the DBMS performs a binary search of the sparse index to locate the correct block, and then scans within that one block for the exact record.

A secondary index is built on a non-ordering field - that is, a field on which the data file is not physically sorted. Since the data file is not ordered by this field, records having nearby index-key values may be scattered across many different, non-contiguous blocks; consequently the index must be dense, containing one index entry for every single record in the file (mapping that record's key value directly to the record's exact address), rather than one entry per block. Secondary indexes are essential for supporting efficient lookups on fields other than the primary ordering field, but they require more storage and maintenance overhead than primary indexes because of their density and because every insert/delete/update on the indexed field must update the corresponding index entry precisely.

• Primary index: built on the ordering (sort) field; sparse (one entry per block); requires the data file to be sequentially ordered on that field.
• Secondary index: built on a non-ordering field; dense (one entry per record); required because the data file is not physically sorted on this field, so no other cheap way to jump to matching records exists.
• A file can have at most one primary index (since it can be physically sorted in only one order) but can have several secondary indexes on different fields.

It is also worth relating both index types to the broader concept of a clustering index, which shares some properties with a primary index but applies to a different situation. A clustering index is built on a non-key ordering field - that is, the data file is physically sorted on this field, but unlike a primary key, this field is not required to have unique values (many records can share the same value, e.g. sorting an Employee file by DeptID rather than by a unique EmpID). Like a primary index, a clustering index can be sparse, since the file is physically ordered on the indexed field, but it needs one entry per distinct field value rather than one entry per record, pointing to the first record in the file having that value; records with the same DeptID are then read sequentially in the following blocks. This sits conceptually between the primary index (unique, ordering key) and the secondary index (dense, non-ordering key).

Multilevel indexes extend both primary and secondary indexing further by treating the first-level index itself as an ordered file and building a second-level (sparse) index on top of it, and so on recursively, until the top level fits in a single block; this reduces the number of block accesses required for a binary search of a large index, and is the structural principle underlying B-tree and B+-tree indexes widely used in real DBMS engines for both primary and secondary access paths.