Suppose the indexed-sequential file contains records for a million people, and suppose that the key field,
the field that uniquely identifies each record, is a social security number (SSN) field. The records in the file are
ordered by SSN. Without indexing, finding any particular person would require, on average, reading 500,000
records (half of them).
However, now suppose that the associated indexing file has 1000 entries; each entry consists only of a SSN
and a pointer to the record in the main file with that SSN. To find a person, the system will read the indexing
122 OPERATING SYSTEMS [CHAP. 6
file to find the indexing record with a value for SSN that is largest, but still less than or equal to the SSN being
sought. Using the pointer from the indexing record, the system can now read the main file starting from a point
near the record being sought. On average, the system will make 500 reads of the indexing file followed by 500
reads of the main file (one million records divided among 1000 index values means 1000 records per index, and
on average the system must read half of them). So, indexing reduces the number of reads from 500,000 to
1000??”improvement by a factor of 500.
Files may contain information in both character form (ASCII, UNICODE, or EBCDIC) and binary form.
Pages:
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339