File Organization and Access Methods

Definition

File organization is the method used to arrange records in a file on secondary storage so that they can be stored and retrieved efficiently.

Access method is the technique used to read, search, insert, update, or delete records from a file.

Together, file organization and access methods determine:

how records are physically placed on storage,
how quickly records can be found,
how efficiently data can be modified,
and how suitable the file structure is for a particular application.

Main Content

1. File Organization

File organization refers to the layout or arrangement of records within a file. A file is a collection of related records, and each record contains fields that represent data about one entity.

The organization of a file is important because it influences storage cost, retrieval time, and update operations. Different applications need different arrangements. For instance, payroll systems often access employee records by employee ID, while banking systems may require both fast lookup and frequent updates.

Common types of file organization:

Heap organization

Records are stored in no particular order.
New records are placed wherever space is available.
It is simple and fast for insertion.
Searching can be slow because records must often be scanned sequentially.

Sequential organization

Records are stored in sorted order based on a key field.
Good for batch processing and range queries.
Searching can be efficient if the file is sorted, but insertion and deletion are more costly because order must be maintained.

Indexed organization

An index is created to point to the actual location of records.
The index acts like a table of contents.
It improves search speed significantly.

Indexed-sequential organization

Combines sequential storage with an index.
Records are stored in sorted order, and an index is used for direct access.
This method supports both sequential processing and faster retrieval.

Direct or hashed organization

A hash function computes the storage location of a record from its key.
It is very fast for exact-match queries.
It is not ideal for range searches.

Example:

Suppose student records are stored by roll number:

In sequential organization, records may be arranged as 101, 102, 103, 104.
In heap organization, records may appear in any order depending on insertion time.
In hashed organization, roll number 103 may be stored at a location computed by a hash rule rather than its numerical order.

Why file organization matters:

It reduces disk I/O operations.
It improves retrieval performance.
It supports efficient file maintenance.
It helps match storage design to application needs.

2. Access Methods

Access methods describe how a record is located and retrieved from a file. Even if the file is well organized, the system still needs a method to access data efficiently.

The choice of access method depends on whether the system needs:

simple sequential reading,
fast random lookup,
frequent updates,
or support for both search and scanning.

Major access methods:

Sequential access

Records are accessed one after another in order.
The system starts from the beginning and processes each record until the desired one is found.
Suitable for applications like payroll processing, report generation, and reading log files.

Direct access

Records are accessed directly using a key or physical address.
The system calculates where the record is likely stored and reads it immediately.
Useful for interactive systems requiring quick lookup, such as bank account retrieval.

Indexed access

An index is searched first to find the location of the actual record.
After locating the pointer, the record is read from the file.
Efficient for large files and mixed workloads.

Relative access

Records are accessed by relative record number or offset.
The system identifies a record based on its position in the file.
Common in systems where records are fixed-size and stored in a predictable structure.

Example:

If a program wants to find employee ID 5005:

With sequential access, it checks employee 5001, 5002, 5003, and so on until it reaches 5005.
With indexed access, it uses the index to jump near the correct record location.
With direct access, it may compute the storage location immediately from the employee ID.

Access pattern selection:

Use sequential access when records must be processed in order.
Use direct access when fast retrieval of individual records is required.
Use indexed access when both search and range queries are important.
Use relative access when records are fixed and position-based retrieval is needed.

3. File Structure and Record Placement

File structure is the internal format of the file and how records are physically arranged on storage media. Record placement affects the performance of access methods and file maintenance operations.

A record may contain:

key field,
descriptive fields,
data fields,
and sometimes pointers or control information.

Important ideas in record placement:

Fixed-length records

Each record has the same size.
Easier to calculate position during direct or relative access.
Efficient for systems needing uniform storage.

Variable-length records

Records differ in size.
Useful when data items are not uniform, such as different address lengths or optional fields.
More complex to manage because record positions are not predictable.

Blocking

Multiple records may be stored in one disk block to reduce I/O overhead.
Improves disk efficiency because fewer physical reads and writes are needed.

Pointers and links

Some file organizations use pointers to connect records.
This helps in overflow handling and maintaining logical order even when physical order changes.

Simple illustration of record placement:

File
+---------+---------+---------+---------+
| R1      | R2      | R3      | R4      |
+---------+---------+---------+---------+

Indexed file:
Index -> [Key 10 -> Block A]
      -> [Key 20 -> Block D]
      -> [Key 30 -> Block B]

Practical importance:

Better placement reduces disk head movement.
Good structure improves response time.
Poor placement can cause fragmentation and slow retrieval.
Efficient structure helps in large-scale data systems.

Working / Process

1. Store the records in a chosen file organization

Decide whether the file will be heap, sequential, indexed, indexed-sequential, or hashed.
Insert records according to the rules of that organization.
Example: In sequential organization, sort employee records by employee number before storing.

2. Select the access method

Choose how the system will retrieve records: sequential, direct, indexed, or relative.
The choice depends on the application’s needs, such as speed, order, or update frequency.
Example: A bank may use direct or indexed access for quick account lookup.

3. Retrieve or modify the record

The system searches, reads, updates, inserts, or deletes the record according to the chosen method.
If indexed access is used, the index is searched first.
If hashed access is used, the key is transformed into a storage location.

4. Handle updates and maintenance

When records are inserted or deleted, the file organization may need adjustments.
Indexes may need updates, overflow areas may need management, and deleted slots may need reuse.
This ensures the file remains efficient over time.

5. Maintain performance

Periodically reorganize files if fragmentation or overflow becomes excessive.
Rebuilding indexes or rehashing data can restore efficiency.
This is especially important in high-transaction systems.

Advantages / Applications

Improves data retrieval speed

Proper organization reduces the time needed to locate records.
Indexed and direct access methods are especially useful for large files.

Supports different application needs

Sequential files suit batch processing.
Direct files suit transaction processing.
Indexed files support both searching and ordered traversal.

Reduces storage and processing overhead

Efficient organization minimizes unnecessary disk operations.
Blocking and indexing can significantly improve performance.

Used in many real systems

Banking systems for account records
Library systems for book catalogs
Airline reservation systems for ticket records
Payroll and personnel systems for employee data
Database management systems for table storage and retrieval

Summary

File organization decides how records are arranged in storage.
Access methods decide how records are found and used.
The right combination makes data handling fast and efficient.
Important terms to remember: file organization, access method, sequential access, direct access, indexed access, hashed organization.