File Structure Basics: Sequential, Indexed, Random Access

File Structures MODULE: 4( SECTION B)

Topic  Covered so far   Searching and Sorting( Section I)     Stack and Queue ( Section I)   Linked List-Part I ( Section I)   Linked List-II ( In Lab) ( Section II)   Trees and Graphs ( Section II)

  Remaining:   Hashing(Section II)   File Structures (Section II)   Array (Section I)   Introduction(Section I)

Topics   Concepts of fields   records and files    Sequential    Indexed and Relative/Random File Organization.

Field   A field is an item of stored data.    A field could be a name, a date, an address, a description, a quantity,  etc.    When a field is defined it is given a name (identifier) and a type, that  defines the type of data that will be stored in that field.    This is exactly the same as defining a variable within a program.   Examples of field definitions:    String firstName;    int quantityInStock;.

Record   A  record  is  the  collection  of  fields  that  relate  to  a  single entity.    For example, we could have a student record that includes fields  for  the student’s name, address, homeroom, date  of birth, etc.    A product record could include fields for the serial number, description, cost price, quantity in stock, etc.

Example   public class StudentRecord    {    private int idnumber;    private String lastName;    private String firstName;    private Date birthDate;    private Date startingDate;    private String homeroom;    ............................... }

File   A file is a collection of related records.     For  example,  a  student  file  might  include  all  of  the  records  of students enrolled at a school.    A  police  department  might  keep  a  file  of  criminal  records,  which includes details about all known criminals.    Files  are  stored  on  secondary  storage  devices  such  as  hard  disks, CD-ROMs etc.

  Within a file, all records usually have the same structure.    That is, every record in the file contains the same fields.    Only the data stored in the fields of different record will be different.

  A file is a collection of data stored on mass storage (e.g., disk or tape)    Why on mass storage?  ◦ too big to fit in main memory  ◦ share data between programs  ◦ backup (disks and tapes are less volatile than main memory)    The data is subdivided into records (e.g., student information).    Each record contains a number of fields (e.g., name, age, address)

    how to organize the records on the mass storage to provide  convenient access for the user?

Sequential Files   Records are conceptually organized in a sequential list and can only be accessed sequentially.    The actual storage might or might not be sequential:  ◦ On a tape, it usually is.  ◦ On a disk, it might be distributed across sectors and the operating system would use a linked list of sectors to provide the illusion of sequentially. Not a convenient organization for accessing a particular record quickly.

  Storing and sorting in contiguous block within files on tape or disk is  called as  sequential access file organization .   In sequential access file organization, all records are stored in a  sequential order. The records are arranged in the ascending or  descending order of a key field.   Sequential file search starts from the beginning of the file and the  records can be added at the end of the file.   In sequential file, it is not possible to add a record in the middle of  the file without rewriting the file.

  Advantages of sequential file It is simple to program and easy to design.   Disadvantages of sequential file Sequential file is time consuming process.   It has high data redundancy.   Random searching is not possible.

Sequential File Organization   Suitable for applications that require sequential processing of the entire file    The records in the file are ordered by a  search-key

Indexed Files   Sequential search is even slower on disk/tape than in main memory.    Try  to  improve  performance  using  more  sophisticated  data structures.    An  index  for  a  file  is  a  list  of  key  field  values  occurring  in  the  file along  with  the  address  of  the  corresponding  record  in  the  mass storage.    Typically the key field is much smaller than the entire record, so the index will fit in main memory.    The index can be organized as a list, a search tree, a hash table, etc.

To find a particular record: ◦ Search the index for the desired key.  ◦ When the search returns the index entry, extract the  record’s address on mass storage.  ◦ Access the mass storage at the given address to get the  desired record. ◦ Multiple indexes, one per key field, allow searches  based on different file

Relative/Random File Organization   Direct access file is also known as random access or relative file  organization.   In  direct  access  file,  all  records  are  stored  in  direct  access  storage  device  (DASD),  such  as  hard  disk.  The  records  are  randomly placed throughout the file.   The records does not need to be in sequence because they are  updated directly and rewritten back in the same location.   This  file  organization  is  useful  for  immediate  access  to  large  amount of information. It is used in accessing large databases.   It is also called as hashing.

  Advantages of random/relative access file organization It helps in online transaction processing system (OLTP) like online railway reservation system.  Sorting of the records are not required.   It accesses the desired records immediately.   It updates several files quickly.   It has better control over record allocation.

  Disadvantages of direct access file organization Direct access file does not provide back up facility.   It is expensive.   It has less storage space as compared to sequential file.