Access Methods

So record 51 spans two blocks and costs two accesses, and so does every 51st record after it. That is the reason a system may pad records to divide the block evenly, wasting 16 bytes in each block to save the second access.

Demonstrated on the lab machine

$ for i in $(seq 0 99); do printf 'record %03d %-68s\n' "$i" "of a file of fixed length records"; done > records.dat
$ echo "$(stat -c %s records.dat) bytes for 100 records, so $(( $(stat -c %s records.dat) / 100 )) bytes each"
8000 bytes for 100 records, so 80 bytes each
$ dd if=records.dat bs=80 skip=42 count=1 status=none
record 042 of a file of fixed length records
$ echo "record 42 begins at byte $(( 42 * 80 ))"
record 42 begins at byte 3360
$ dd if=records.dat bs=1 skip=3360 count=10 status=none; echo
record 042

Record 42 was read without reading records 0 to 41, twice over: once by asking for the 42nd block of 80 bytes, and once by asking for byte 3,360 directly. 3,360 is 42 × 80, which is the formula above doing the work.

Indexed access

Keep an index: a table of keys, each with the record number the key is at. Search the index, then use direct access.

The index is itself a file, and if it is large it gets an index of its own: a multi level index. The scheme a question names is ISAM, indexed sequential access method, where a small master index in memory names blocks of a secondary index on disk, which names the records.

So a lookup costs two disk accesses however large the file is, which is why the scheme was worth inventing. The cost is that the index must be kept up to date: every insertion changes it, and a file whose records are inserted often spends its time maintaining indexes.

Note that the index makes access by key possible. Direct access needs the record number, which a program using names or account codes does not have; the index is the translation.

Simulating one with another

A favourite question: which can be built on which, and at what cost.

Direct access cannot be built usefully on sequential access, and that is the whole reason the distinction exists. A tape file is sequential and nothing can be done about it; a disk file can be either.

Distinctions that carry marks

What it does not mean

Sequential access is not slow. It is the fastest way to read a whole file, because the blocks are in order.

Direct access does not need the blocks to be contiguous. It needs fixed length records; the file system finds the block.

An index is not part of the file system. In these schemes the program or the database keeps it, in a file of its own.

Indexed access is not a third kind of hardware operation. It is an index lookup followed by a direct access.

A relative record number is not an address. It is a count, and the file system turns it into a block number.

Quick revision

• Sequential: read next, write next, reset. The tape model, the commonest pattern, and the

cheapest way to read a whole file.

• Direct, or relative: read or write record n in any order. It needs fixed length records

because position = n × record length.

• Worked: 80 byte records, record 1000 starts at 1000 × 80 = 80,000, which is block 19

offset 2,176 in a 4096 byte block system, and does not span blocks.

• Record 51 is the first to span a 4096 byte block: 51 × 80 = 4080 and

4080 + 80 = 4160.

• Measured: a file of 100 records of 80 bytes, and record 42 read directly at byte 3,360,

which is 42 × 80.

• Indexed: search an index of keys for a record number, then one direct access. ISAM

keeps a master index in memory and a secondary index on disk, so a lookup is two accesses; the cost is keeping the index current.

• Sequential can be built on direct at no cost; direct on sequential costs n reads and is

not worth having.

Test yourself

1. Name the three access methods. Sequential, direct or relative, and indexed.
2. What operations does sequential access offer? Read next, write next and reset, and on some

systems skipping forward by n records.

1. Why does direct access need fixed length records? Because the position of record n is

found by multiplying n by the record length; with variable lengths it could not be calculated without reading everything before it.

1. A file has 80 byte records and 4096 byte blocks. Where does record 1000 begin? At byte

1000 × 80 = 80,000, which is block 19 at offset 2,176, and it does not cross into block 20.

1. Which is the first record to span two blocks, and why does it matter? Record 51:

51 × 80 = 4080 and it runs to 4160, past the 4096 boundary, so reading it costs two block accesses instead of one.

1. Describe indexed access and the ISAM scheme. An index of keys gives the record number,

then one direct access fetches the record; ISAM keeps a small master index in memory pointing at blocks of a secondary index on disk, so a lookup costs two disk accesses.

1. What does indexed access add that direct access lacks? Access by key rather than by record

number.

1. Can direct access be built on sequential access? Only by reading and discarding every

record before the one wanted, which costs n reads for one record, so in practice no.