File organization: how fast can you find one record?

The problem

On exam day, 500 students look for their seats. One hall lists names in the order forms arrived: you read down until you find yours. Another hall seats you by roll number: roll 457 walks straight to seat 457.

Files on a disk face the same choice. How records are placed decides how much work it takes to find one of them.

From the storage point of view there are three organizations. Sequential files are stored one after another and take the most processing time. Direct or random files sit at an address calculated from the key field. Indexed sequential files keep a separate index of keys and addresses: sequential or random access, but more space.

Key terms

Sequential file

Records are stored one after another in the order they are entered. Finding one record means reading the ones before it, so it needs more processing time.

Direct or random file

Each record is placed at an address calculated from the value of its key field, so the program can go straight to it.

Synonym

Sometimes the same address is calculated for two different keys. The two keys are then called synonyms.

Indexed sequential file

The key fields are stored separately with each record's address. The file can be processed in sequence or randomly, needs more space, and is as fast as a direct file.

Short questions with model answers

1. Q1. A record's address is key mod 50. Find the addresses of keys 0342 and 0288.

   • 342 = 6 × 50 + 42 → address 42
   • 288 = 5 × 50 + 38 → address 38

   42, 38

2. Q2. With the same rule, show that keys 0157 and 0457 are synonyms.

   • 157 = 3 × 50 + 7 → 7; 457 = 9 × 50 + 7 → 7
   • Keys with the same calculated address are synonyms

   Both map to address 7: synonyms

3. Q3. A college prints all 1,200 result cards once a year, and also answers single-student queries at the counter. Which organization suits both jobs?

   • Printing all cards → sequential processing
   • One student at the counter → direct access

   Indexed sequential

Common mistakes

• ✗ Saying records in a random file are stored in no particular place.

  ✓ Each record sits at an address calculated from its key field. Random means it can be reached directly, in any order.

• ✗ Defining a synonym as two records with the same key.

  ✓ Synonyms have different keys that produce the same calculated address, like 0157 and 0457 giving 7.

• ✗ Thinking indexed sequential files are better in every way.

  ✓ They pay for speed with space: the index of keys and addresses needs relatively more storage.

MCQs

1. 1. Which type of file requires the largest processing time?

   1. (a) sequential file
   2. (b) random file
   3. (c) indexed sequential file
   4. (d) direct access file
   Show answer

   (a) Records must be read one after another until the wanted one is reached.

2. 2. In a direct file, a record's location is calculated from:

   1. (a) its entry time
   2. (b) its key field value
   3. (c) its file extension
   4. (d) the index size
   Show answer

   (b) The address is calculated against the value of the key field.

3. 3. With address = key mod 50, which key is a synonym of 0203?

   1. (a) 0204
   2. (b) 0253
   3. (c) 0230
   4. (d) 0302
   Show answer

   (b) 203 mod 50 = 3 and 253 mod 50 = 3: same address, different keys.

4. 4. Which files can be processed both sequentially and randomly?

   1. (a) sequential files
   2. (b) direct files
   3. (c) indexed sequential files
   4. (d) backup files
   Show answer

   (c) The separate index gives direct access, and the records can still be read in sequence.

5. 5. The drawback of indexed sequential files is that they:

   1. (a) are slowest
   2. (b) need more storage space
   3. (c) cannot be read in order
   4. (d) have synonyms
   Show answer

   (b) Storing the index needs relatively more space, though processing is as fast as random files.

Quick revision

• Sequential files store records in entry order and take the most processing time to search.
• Direct files place each record at an address calculated from its key; different keys with the same address are synonyms.
• Indexed sequential files keep a key-and-address index: sequential or random access, fast, but more space.