Q8Data Base Management System

(a) Static hashing vs dynamic hashing

In static hashing, the number of buckets M is fixed at the time the file is created, and a hash function such as h(k) = k mod M maps every key permanently into one of these M buckets. This scheme is simple and gives fast direct access as long as the actual number of records stays reasonably close to what was originally planned for. However, as the file grows well beyond its original design capacity, more and more records collide into the same fixed set of buckets, causing bucket overflow: extra records must be chained into overflow blocks linked to the primary bucket, and performance progressively degrades toward that of a linear search as overflow chains grow longer. Shrinking the file similarly leaves buckets mostly empty, wasting space. Static hashing therefore works well only when the eventual file size is known in advance and relatively stable.

Dynamic hashing schemes, such as extendible hashing and linear hashing, address this limitation by allowing the hash structure to grow (or shrink) incrementally as the actual number of records changes, avoiding the overflow problems of static hashing. In extendible hashing, a directory of pointers to buckets is maintained, and each directory entry is selected using only the first d bits of a key's hash value, where d (the global depth) can increase over time. When a bucket becomes full, only that bucket is split, and if necessary the directory doubles in size (global depth increases by 1) so that finer-grained bits of the hash value can distinguish between the now-larger number of buckets - crucially, only the overflowing bucket's data is reorganized, not the entire file. Linear hashing achieves similar incremental growth without needing a directory at all, splitting buckets in a fixed, predetermined order as the load factor crosses a threshold. In both schemes, the structure expands smoothly in proportion to the actual data volume, avoiding both the overflow-chain degradation of an under-sized static hash file and the wasted space of an over-sized one.

Each bucket in an extendible hashing scheme also maintains its own local depth, which is the number of leading bits of the hash value that are actually used to distinguish records stored in that specific bucket; the local depth of a bucket is always less than or equal to the current global depth of the directory. When a bucket's local depth equals the global depth and that bucket overflows, the directory itself must double, since there are not yet enough directory entries pointing at distinct bucket slots to allow a fresh split; when a bucket's local depth is still less than the global depth, its overflow can be handled by simply splitting the bucket into two and updating only the relevant directory pointers, without needing to double the whole directory. This local-versus-global depth bookkeeping is what allows extendible hashing to grow the structure gracefully - most insertions require no reorganization at all, occasional insertions require splitting one bucket, and only occasionally does the entire directory need to double, so that growth cost is amortized very cheaply over the life of the file compared to reorganizing an entire static hash file.

(b) Inverted file and multi-list structure

An inverted file (or inverted index) is an index structure, common in information-retrieval and multi-attribute search systems, that maintains, for every distinct value of an indexed field, a list of the identifiers (or pointers) of all records that contain that value. Rather than indexing one ordering field the way a conventional primary/secondary index does, an inverted file can be built independently for several different fields, each producing its own mapping from value to a posting list of matching record IDs. For example, an inverted file on the field Branch might map 'EE' to the list of record IDs {12, 47, 88}, and 'CS' to {5, 19, 63}; a query for all records with Branch = 'EE' simply retrieves the posting list for 'EE' directly. Queries combining conditions on multiple indexed fields (e.g. Branch = 'EE' AND Year = 3) can be answered efficiently by intersecting the posting lists of the two fields.

A multi-list structure organizes access to records by linking them together via multiple separate linked lists, one for each indexed field, rather than via a separate value-to-list index table. For a given field, all records sharing the same value for that field are chained together using pointers embedded directly in the records themselves, forming one linked list per distinct value; a directory typically stores, for each value of that field, a pointer to the first record in its corresponding chain. Since each record can participate in several such linked lists simultaneously (one per indexed field it belongs to), the same data file supports multiple independent access paths, letting the DBMS traverse records field by field without needing a fully separate index structure for every attribute, at the cost of extra pointer fields embedded in every record and additional maintenance overhead when records are inserted or deleted.

Both structures serve the same broad purpose - supporting efficient retrieval on multiple fields of the same file without physically reordering the data file itself for each field - but they make different space and traversal trade-offs. The inverted file keeps a separate directory of posting lists external to the data records, so the records themselves need not carry any extra pointer fields, but the directory structure (essentially a set of secondary indexes, one per field) must be stored and kept synchronized whenever records are inserted, updated, or deleted. The multi-list structure instead embeds the linkage directly inside the records as pointer fields, avoiding a separate large directory for the posting lists themselves (only a small directory of first-record pointers per field value is needed), but it enlarges every record by one pointer field for each indexed attribute it participates in, and following a chain of pointers scattered across the file can require more scattered disk I/O than reading one contiguous posting list from an inverted index.

In practice, inverted files are the dominant technique in modern information-retrieval and full-text search systems (such as search-engine indexes), since posting lists compress well and can be combined efficiently using set intersection/union algorithms for multi-term queries, whereas multi-list structures are more commonly seen in older or specialized database systems designed explicitly to support multiple simultaneous access paths through embedded chains, illustrating two different historical solutions to the same underlying multi-key retrieval problem.