File Organization

File Organization

• A file organization is a method of arranging records in a file when the file is stored on disk.

• A file is organized logically as a sequence of records.

• Record is a sequence of fields.

• There are two types of records used in file organization (1) Fixed Length Record (2) Variable Length Record.

(1) Fixed length record

• A file where each records is of the same length is said to have fixed length records.

• Some fields are always the same length (e.g. Phone Number is always 10 characters).

• Some fields may need to be 'padded out' so they are the correct length.

• For example -

type Employee = record

EmpNo varchar(4)

Ename varchar(10)

Salary integer(5)

Phone varchar(10)

End

For instance the first record of example file can be stored as

Thus total 29 bytes are required to store.

Advantage:

• Access is fast because the computer knows where each record starts.

Disadvantage:

(1) Due to fixed size, some larger sized record may cross the block boundaries. That of means part of record will be stored in one block and other part of the record may be stored in some another block. Thus we may require two block access for each read or write.

(2) It is difficult to delete the record from this structure. If some intermediate record is deleted from the file then the vacant space must be occupied by next subsequent records.

• When a record is deleted,we could move the record that came after it into the space formerly occupied by the deleted record. But this may require moving of multiple records to occupy the vacant space. This is an undesirable solution to fill up vacant space of deleted records.

• Another approach is to use a file header. At the beginning of the file, we allocate a certain number of bytes as a file header. The header will contain information such as address of the first record whose contents are deleted. We use this first record to store the address of the second available record and so on. Thus the stored record addresses are referred as pointer while the deleted records thus form a linked list which is called as free list.

For example - Consider the employee record in a file is-

The representation of records maintaining free list after deletion of record 1,3 and 5

• On insertion of a new record, we use the record pointed to by the header. We change the header pointer to point to the next available record. If no space is available, we add the new record to the end of the file.

(2) Variable length record

• Variable-length records arise in a database in several ways:

(i) Storage of multiple record types in a file.

(ii) Record types that allow variable lengths for one or more fields.

(iii) Record types that allow repeating fields such as arrays or multisets.

• The representation of a record with variable-length attributes typically has two parts:

a) an initial part with fixed length attributes. This initial part of the record is represented by a pair (offset, length). The offset denotes the starting address of the record while the length represents the actual length of the length.

b) followed by data for variable length attributes.

• For example - Consider the employee records stored in a file as

• The variable length representation of first record is,

• The figure also illustrates the use of a null bitmap, which indicates which attributes of the record have a null value.

• The variable length record can be stored in blocks. A specialized structure called slotted page structure is commonly used for organizing the records within a block. This structure is as shown by following Fig. 4.2.1.

• This structure can be described as follows -

   • At the beginning of each block there is a block header which contains -

    i.Total number of entries (i.e. records).

    ii.Pointer to end of free list.

    iii.Followed by an array of entries that contain size and location of each record.

  • The actual records are stored in contiguous block. Similarly the free list is also maintained as continuous block.

  • When a new record is inserted then the space is allocated from the block of free list.

  • Records can be moved around within a page to keep them contiguous with no empty space between them; entry in the header must be updated.

Review Question

1. Describe different types of file organization. Explain using a sketch of each of the, with their advantages and disadvantages.   AU: Dec.-08, Marks 10