File Organization

File Organization

The database is stored as a collection of files where each file is a sequence of records. A record can be said as a sequence of fields. There are mainly two types of records and they are given below:

• Fixed-Length Records
• Variable-Length Records

Fixed-Length Records

First of all, let us assume that the record size is fixed. Each file has records of one particular type only. The different files are used for different relations. This case is easiest to implement. Store the records i starting from byte n * (i - 1), where n is the size of each record. Record access is simple but records may cross blocks.

Two problems:

• Difficult to delete a record from the structure: The deleted space must be filled by another record or marking deleted records so that they can be ignored.
• Block size must be a multiple of n (file size). Some records may cross the boundaries so it requires two block access for a record.

Approaches for deletion:

• Move records i + 1,......., n to i,........, n - 1 (Requires more access to move the record)
• Do not move records but link all free records on a free list.
• Store the address of the first deleted a record in the file header.
• This first record to store the address of the second deleted the record and so on.

We can think of these stored addresses as pointers since they "point" to the location of a record. Fixed-length records can be considered as the more space efficient representation as it reuses space for normal attributes of free records to store pointers. On new insertion of the record, we use the record pointed by the file header and change the header pointer to point the next available record. If there is no space available then add a new record at the end of the file.

Variable-Length Records

Variable-length records arise in database systems in several ways:

• Storage of multiple records types in a file.
• Record type that allows variable lengths for one or more fields.
• Record types that allow repeating fields (used in some older data models).

Mainly two approaches

• Byte-String Representation
• Fixed-length Representation

Byte-String Representation

Byte-string representation attaches a special end_of_file( ⊥) symbol to the end of the record. Disadvantages are:

• Not easy to reuse space occupied by deleted record.
• No space for records to grow longer. If the records become longer then it must be moved.

The modified form of byte-string representation is called slotted page structure. Slotted page header contains:

• Number of record entries
• End of free space in the block
• Location and size of each record

Records can be moved around within a page to keep them contiguous with no empty space between them and entry in the header must be updated. Pointers should not point directly to record instead they should point to the entry for the record in the header.

Fixed-Length Representation

Fixed-length representation uses one or more fixed length records:

• Reserved space: It can use fixed-length records of a known maximum length where unused space in shorter records are filled with a null.
• List Representation: It can use fixed-length records of a known maximum length where unused space in shorter records are filled with a null.

The disadvantage to pointer structure is that space is wasted in all records except the first in a chain. Solution is to allow two kinds of block in file:

• Anchor block: It contains the first records of the chain.
• Overflow block: It contains records other than those that are the first records of chains.

References:

1. H.F.Korth and A. Silberschatz,"Database system concepts",McGraw Hill,2010
2. A.K.Majumdar and p, Bhatt acharya,"Database Management Systems",Tata McGraw Hill,India,2004
3. F.Korth, Henry. Database System Concepts. 6th edition.