File organization in DBMS - Sequential file organization

Sequential File Organization / Ordered File Organization / Sorted File Organization / Advantages and Disadvantages

Sequential File Organization (Sorted file organization)

In this file organization, records are sorted on an attribute(s) values and stored physically in the disk in that sorted order. This kind of file organization will speed up the retrieval of data especially when queried on the sorting attributes.

Ex. Assume a relation Emp with schema Emp(Eno, Ename, Salary, Dept). The following query can be answered quickly (possibly) if we have arranged the Emp file using sorted file organization on Eno attribute.

SELECT * FROM Emp WHERE Eno = ‘110’;

In this file organization, records of a table are chained together using pointers in the search key order and stored in that order physically. 

How do we insert a record?

• Insert the record at the end of file.
• Find the previous record on the sorting key value and reset the pointer of that record to point to the new record, and insert the previous record’s pointer in the pointer field of new record.
• All the other records’ pointers should be altered as well.
• Reorganize all the records periodically to arrange the records in the sorting order of the ordering attribute.

Refer the example given below.

How to delete a record?

• Locate the record that is to be deleted.
• Replace the previous record’s pointer value with the pointer of the record to be deleted.
• Update all the other records' pointers (if needed).

Advantages:

• Retrieval of records become efficient if the query uses the sorting attribute as the search key.

• Sorting of records on the ordering field is fast. [No sorting is required externally]

Disadvantages:

• Insertion and deletion of records are expensive.

• Updating the sorting attribute values of the records is also expensive.

• Retrieval of records on the non-ordering attributes is not easy.