p. 231

4 - 3 File Organization Formats

A file organization format defines the order of records to be recorded in a file and the structure. The user must consider specifically how the file is to be used and consider which organization format is appropriate.

4-3-1 Sequential Organization

Sequential organization file has a dedicated organization format for sequential access, which writes records sequentially on storage media. Its usage of storage media is efficient because the records are written sequentially, but it cannot insert records in the middle of a file. Since records are always processed in order, it is effective to read records in advance by using a buffer. This organization can be implemented on all storage media including DASD (Direct Access Storage Devices). However, on magnetic tape, only sequential organization can be implemented.

4-3-2 Relative Organization

Relative organization file has a format that writes records in order as in a sequential organization file, and then assigns a relative number (i.e., relative address) to each record from the top of records. Since the records are written sequentially, it uses storage media efficiently, and direct access with the relative number of a record is also possible.

4-3-3 Indexed Sequential Organization

An indexed sequential organization file (or indexed sequential file) is composed of two areas: an area for data, and an area in which information (i.e., index) for direct access to a specific record is stored. Its usage of storage media is efficient, and it can create large files.

p. 232

4-3-4 Partitioned Organization

In a partitioned organization file, a file is divided into multiple units called members to store it. The information from each member is managed with a directory. Members are subfiles into which a sequential organization is divided, and update management can be performed in units of members. However, deletion of members only removes the members from the directory and the corresponding members in the memory area remain as is. As a result, the number of waste areas in which unused members are stored increases, and storage efficiency decreases, so it is necessary to periodically reorganize memory areas. Partitioned organization files are generally used as a program library. · 1 question

4-3-5 Direct Organization

A direct organization file has a dedicated format for direct access that enables access to a specific record by the specification of an address. The location of records is not sequential, so it does not use storage media efficiently. It can only be implemented on DASD (Direct Access Storage Devices) such as hard disks. In order to specify a specific record, direct addressing and indirect addressing are available as methods to calculate the address by using the key item of a record.

(1) Direct addressing

Direct addressing uses the value of a record key as the record address. No processing is required to calculate the address, but depending on the record key, there may be many variations of addresses, so it is not practical.

p. 233

There are also methods that use a correspondence table for record keys and record addresses. However this requires a large number of elements equal to the records to be stored, so its usage is limited to a small number of records.

(2) Indirect addressing

Indirect addressing changes the value of a record key in accordance with a rule and calculates the record address. This conversion is called hashing, and the used rule (i.e., function) is called a hash function. Therefore, a direct organization file that uses indirect addressing is sometimes called a hash organization file. · 1 question

p. 234

With indirect addressing, different keys may be converted to the same record address and this phenomenon is called the occurrence of a synonym. When this happens, the record that can be used with the converted address is called the home record, and the one that cannot be used is called the synonym record.

There are two methods to deal with a synonym. These are described below. In both methods, the subject record cannot be accessed with a record address calculated from the key, so the access efficiency is reduced; in other words, access time increases. Therefore, it is preferable that there be no bias in the distribution of key values, and that the record addresses calculated from key values be close to uniform distribution (i.e., a distribution in which the occurrence of a phenomenon has equal probability).

4-3-6 VSAM Organization

VSAM organization files can be used with an OS that uses a virtual memory system. This can also be described as a way of implementing conventional file organization format virtually. In VSAM organization, a file is called a data set. The table and diagram below show the correspondence between data sets and file organizations, and data set structure, respectively.

p. 235