RdbmsUnit2.2

Unit-I		Unit-II	Unit-III	Unit-IV	Unit-V
Part-I	Part-II	Part-I	Part-I	Part-I	Total
Part-III	Part-IV	Part-II	Part-II	Part-II
Part-V		Part-III

 

FILE ORGANISATION AND ITS TYPES

1.     Explain File Organisation and its types?

Ans:

Just as arrays, lists, trees and other data structures are used to implement data Organisation in main memory, a number of strategies are used to support the Organisation of data in secondary memory.

A file organisation is a technique to organise data in the secondary memory. File Organisation is a way of arranging the records in a file when the file is stored on the disk.

Selection of File Organisations is dependant on two factors as shown below:

• Typical DBMS applications need a small subset of the DB at any given time.

• When a portion of the data is needed it must be located on disk, copied to memory for processing and rewritten to disk if the data was modified.

The important task of the DBA is to choose a good Organisation for each file, based on its type of use.

Figure1 illustrates different file organisations based on an access key.

Let us discuss some of these techniques in more detail:

Heap files (unordered file)

Basically these files are unordered files.

It is the simplest and most basic type.

The records will have no particular order.

The operations we can perform on the records are insert, retrieve and delete.

The features of the heap file or the pile file Organisation are:

• New records can be inserted in any empty space that can accommodate them.

• When old records are deleted, the occupied space becomes empty and available for any new insertion.

• If updated records grow; they may need to be relocated (moved) to a new empty space. This needs to keep a list of empty space. 

Advantages of heap files

1. This is a simple file Organisation method.

2. Insertion is somehow efficient.

3. Good for bulk-loading data into a table.

4. Best if file scans are common or insertions are frequent.

Disadvantages of heap files

1. Retrieval requires a linear search and is inefficient.

2. Deletion can result in unused space/need for reorganisation. 

Sequential File Organisation

•   The most basic way to organise the collection of records in a file is to use sequential Organisation.
• Records of the file are stored in sequence by the primary key field values.
•  They are accessible only in the order stored, i.e., in the primary key order.
•   This kind of file Organisation works well for tasks which need to access nearly every record in a file, e.g., payroll.
•   A sequential file maintains the records in the logical sequence of its primary key values. 

• They are accessible only in the order stored, i.e., in the primary key order.
•  This kind of file Organisation works well for tasks which need to access nearly every record in a file, e.g., payroll.
•   A sequential file maintains the records in the logical sequence of its primary key values.
•   Sequential files are inefficient for random access, however, are suitable for sequential access.
•  On an average, to search a record in a sequential file would require to look into half of the records of the file.
• A sequential file can be stored on devices like magnetic tape that allow sequential access. 
•  If a sequential file is stored on a disk (remember disks support direct access of its blocks) with keyword stored separately from the rest of record, then only those disk blocks need to be read that contains the desired record or records.
•  This type of storage allows binary search on sequential file blocks, thus, enhancing the speed of access.
• Updating a sequential file usually creates a new file so that the record sequence on primary key is maintained. The update operation first copies the records till the record after which update is required into the new file and then the updated record is put followed by the remainder of records. Thus method of updating a sequential file automatically creates a backup copy.
•  Additions in the sequential files are also handled in a similar manner to update. Adding a record requires shifting of all records from the point of insertion to the end of file to create space for the new record.
•   On the other hand deletion of a record requires a compression of the file space.

Advantages of sequential file  organisation

·        In the sequential processing, as next record is easily accessible despite the absence of any data structure.

·        It is fast and efficient when dealing with large volumes of data that need to be processed periodically (batch system).

Disadvantages of sequential File Organisation

• Requires that all new transactions be sorted into the proper sequence for sequential access processing.

• Locating, storing, modifying, deleting, or adding records in the file require rearranging the file.

• This method is too slow to handle applications requiring immediate updating or responses.

Indexed (Indexed Sequential) File Organisation

It organises the file like a large dictionary, i.e., records are stored in order of the key but an index is kept which also permits a type of direct access. The records are stored sequentially by primary key values and there is an index built over the primary key field.

The retrieval of a record from a sequential file, on average, requires access to half the records in the file, making such inquiries not only inefficient but very time consuming for large files. To improve the query response time of a sequential file, a type of indexing technique can be added. 

•      An index is a set of index value, address pairs.
•     Thus, an index is a mechanism for faster search.
•     An index can be small enough to be read into the main memory.
•     A sequential (or sorted on primary keys) file that is indexed on its primary key is called an index sequential file.
•     The index allows for random access to records, while the sequential storage of the records of the file provides easy access to the sequential records.
•     An additional feature of this file system is the over flow area. The overflow area provides additional space for record addition without the need to create. 

Hashed File Organisation

• Hashing is the most common form of purely random access to a file or database.
• It is also used to access columns .
• Hash functions calculate the address of the page in which the record is to be stored based on one or more fields in the record.
• The records in a hash file appear randomly distributed across the available space.
• It requires some hashing algorithm and the technique. Hashing Algorithm converts a primary key value into a record address.
• The most popular form of hashing is division hashing with chained overflow. 

Advantages of Hashed file Organisation

1. Insertion or search on hash-key is fast.

2. Best if equality search is needed on hash-key.

Disadvantages of Hashed file Organisation

1. It is a complex file Organisation method.

2. Search is slow.

3. It suffers from disk space overhead.

4. Unbalanced buckets degrade performance.

5. Range search is slow.