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.