In a file that uses hash-based organization, overflow chains degrade…

2026

In a file that uses hash-based organization, overflow chains degrade performance mainly due to which of the following?

Answer: A. Increased seek timeConcept: In hash-based file organization, a hash function maps each record's key to a bucket (a fixed-size disk block). When a bucket's capacity is exceeded,…

  1. A.

    Increased seek time

  2. B.

    Bucket alignment issues

  3. C.

    Loss of alphabetical ordering

  4. D.

    Increased rotational latency

Attempted by 84 students.

Show answer & explanation

Correct answer: A

Concept: In hash-based file organization, a hash function maps each record's key to a bucket (a fixed-size disk block). When a bucket's capacity is exceeded, the surplus records cannot fit in the primary bucket, so they are placed in a separate overflow block that is chained to the primary bucket with a pointer — this technique is called overflow chaining. On the standard rotating-disk model used throughout file-organization theory, each block access costs seek time (repositioning the head to the target track) plus rotational latency (waiting for the target sector to arrive) plus transfer time — and across this standard model, seek time is consistently the largest of the three, since repositioning the head to an arbitrary, non-adjacent track takes several times longer than waiting out a partial platter rotation.

Application: To answer a lookup once a bucket has overflowed, the system has to walk the chain:

  1. Read the primary bucket block and scan its records for the key.

  2. If not found and an overflow pointer exists, fetch the linked overflow block from wherever it happens to be allocated on disk.

  3. Repeat step 2 for every further overflow block in the chain until the key is found or the chain ends.

Because overflow blocks are typically allocated at whatever free location is available rather than physically next to their primary bucket, each hop to a new overflow block is effectively a fresh, unpredictable access: it forces the disk head to be repositioned to a different track before that block can be read. To isolate what chaining specifically adds, compare a chained lookup (k block reads) against a non-overflowed lookup (1 block read): both incur one seek and one rotational wait per block visited under the standard model above, so chaining specifically adds (k − 1) extra seeks and (k − 1) extra rotational waits. Since seek time is the larger of the two components on that standard model (commonly several times a rotational wait), these (k − 1) extra seeks contribute far more added latency than the (k − 1) extra rotational waits do. As chains grow longer, it is this larger, repeated seek cost across scattered, non-contiguous blocks — i.e. increased seek time — that dominates the performance penalty specifically caused by overflow chaining.

Cross-check — why the other options are not the mechanism at work here:

  • Bucket alignment issues describe whether a bucket's boundaries coincide with the underlying disk block boundaries — a property fixed by the hashing scheme's design, not something that changes as a chain lengthens.

  • Loss of alphabetical ordering cannot be caused by overflow chaining, because hash-based organization never preserves key order to begin with — that property belongs to ordered/sequential file organization.

  • Rotational latency (waiting for the target sector to spin under the head) also recurs once per extra block access in the chain, exactly like seek does — so it is not absent from the picture. What it lacks is dominance: on the standard model, its per-access magnitude is markedly smaller than the per-access seek cost, so its accumulated contribution across the chain's extra accesses is smaller than the growth in seek time is.

So the correct answer is: increased seek time.

Explore the full course: Niacl Ao It Specialist

Loading lesson…