FO

File Organization and Access

Understanding methods of file organization, access, and hashing algorithms

Learning Objectives

By the end of this lesson, you will be able to:

  • Understand and differentiate between different methods of file organization
  • Select appropriate methods of file organization and access for given problems
  • Explain the differences between text files and binary files
  • Understand and describe serial, sequential, and random file organization
  • Compare sequential and direct file access methods
  • Describe and use different hashing algorithms
  • Understand and handle address collisions in hashing

Key Terms

  • Text File - Contains data stored according to character code. Human-readable and uses ASCII encoding.
  • Binary File - Stores data in internal representation. Not human-readable, designed for computer programs.
  • Serial File Organization - Stores records in the order they were added, with new records appended to the end.
  • Sequential File Organization - Stores records in a given order based on a key field.
  • Random File Organization - Stores records in any available position using a hashing algorithm.
  • Sequential Access - Searches for records one after another from the start of the file.
  • Direct Access - Finds records without reading other records, using indexes or hashing.
  • Hashing Algorithm - Performs calculations on a key field to determine storage address.
  • Address Collision - Occurs when different key values produce the same storage address.

What Are File Organization and Access?

In everyday computer usage, we encounter a wide variety of file types such as graphic files, word-processing files, and spreadsheet files. Regardless of the file type, content is stored using specific binary codes that allow the file to be used as intended.

Text Files

Contains data stored according to character code. Text files are human-readable and use ASCII encoding where each character is represented by one byte (8 bits).

Organization of Text Files
  • Number of data items per line must be known
  • Number of characters per item must be known
  • Uses item separator characters if structure not known
  • Has repeating lines defined by end-of-line character
  • Examples: .txt, .csv files

Binary Files

Stores data in its internal representation. Binary files are not human-readable and can only be opened by programs that understand the binary format.

Organization of Binary Files
  • Based on concept of records
  • File contains records, each record contains fields
  • Number of fields per record must be known
  • String lengths must be known if present
  • No need for field separator or end-of-record characters
  • Examples: .exe, .jpg files

File Organization Methods

File organization refers to how data is physically stored in a file. Different organization methods are suitable for different applications.

Serial Organization

Physically stores records one after another in the order they were added. New records are appended to the end of the file.

Record 1
Record 2
Record 3
Record 4
Record 5
Record 6

Records stored in order of arrival

Typical Use: Temporary files storing transactions (e.g., customer meter readings before billing)

Sequential Organization

Stores records in a given order based on a key field (unique identifier). Records are sorted in ascending key field order.

Cust 1
Cust 2
Cust 3
Cust 4
Cust 7
Cust 8

Records sorted by key field (Customer ID)

Typical Use: Customer records for billing systems, payroll systems

Random Organization

Stores records in any available position. Location is found using a hashing algorithm on the key field.

Cust 8
Cust 2
Cust 4
Cust 7
Cust 3
Cust 1

Records stored in positions determined by hashing

Typical Use: Databases where quick access to individual records is needed

Activity 13A: File Organization Selection

Difficulty: Medium • Estimated time: 10 minutes

For each of the following scenarios, select the most appropriate file organization method and justify your choice:

  1. A log file that records all user actions on a system in chronological order.
  2. A customer database where records need to be accessed frequently by customer ID.
  3. A file storing temperature readings from sensors that are processed once daily.
  1. Serial Organization - Log files record events in chronological order as they occur, which matches the serial organization method where records are appended in order of arrival.
  2. Random Organization - When records need to be accessed frequently by a key field (customer ID), random organization with direct access provides the fastest retrieval times.
  3. Serial or Sequential Organization - Temperature readings that are processed in batch once daily don't require random access. Serial is sufficient if processing order doesn't matter; sequential if sorting by time or sensor ID is needed.

File Access Methods

File access methods determine how records are physically located within a file. The choice of access method affects performance and efficiency.

Sequential Access

Searches for records one after another from the physical start of the file until the required record is found.

PROCEDURE SequentialSearch(targetKey)
  OPEN file FOR READ
  WHILE NOT EOF(file) DO
    currentRecord ← READ(file)
    IF currentRecord.key = targetKey THEN
      RETURN currentRecord
    ENDIF
  ENDWHILE
  RETURN "Record not found"
ENDPROCEDURE

Best For: Files with high hit rates where most records are processed (e.g., monthly billing, payroll)

Direct Access

Finds records without reading other records, using indexes or hashing algorithms to calculate record location.

PROCEDURE DirectAccess(targetKey)
  // Calculate address using hash function
  address ← HashFunction(targetKey)
  SEEK file, address
  record ← READ(file)
  IF record.key = targetKey THEN
    RETURN record
  ELSE
    RETURN "Record not found"
  ENDIF
ENDPROCEDURE

Best For: Files with low hit rates where individual records need to be accessed (e.g., customer updates, database queries)

Activity 13B: Access Method Analysis

Difficulty: Medium • Estimated time: 8 minutes

Explain how sequential access is used in:

  1. A serial file to find a required record
  2. A sequential file to find a required record
1. Sequential Access in Serial Files:

For a serial file, if a particular record is being searched for, every record needs to be checked until that record is found or the whole file has been searched and that record has not been found. Any new records are appended to the end of the file.

2. Sequential Access in Sequential Files:

For a sequential file, if a particular record is being searched for, every record needs to be checked until the record is found or the key field of the current record being checked is greater than the key field of the record being searched for. The rest of the file does not need to be searched as the records are sorted on ascending key field values. Any new records to be stored are inserted in the correct place in the file.

Example: If searching for Customer 6 in a file containing Customer 1, 2, 3, 4, 7, 8... The search would stop at Customer 7 since key fields are in ascending order and Customer 6 would come before Customer 7 if it existed.

Check Your Understanding: File Access Methods

  • Sequential access reads records one after another from the start
  • Direct access calculates or looks up the exact location of a record
  • Sequential is slower for individual record retrieval
  • Direct access is faster but requires additional structures (indexes/hashing)
  • When processing all or most records in a file (high hit rate)
  • For batch processing operations
  • When file is small or accessed infrequently
  • When simplicity is more important than speed
  • Examples: Monthly billing, payroll processing
  • An index of all key fields is maintained separately
  • The index maps key values to physical file locations
  • To find a record, the index is searched (usually faster than searching the file)
  • Once location is found, the record can be read directly
  • For large files, searching the index is more efficient than sequential file search

Hashing Algorithms

Hashing algorithms perform calculations on the key field of a record to determine where it should be stored in a file. The result of the calculation gives the address where the record should be found.

Hashing for Numeric Key Fields

Choose a suitable number (preferably a prime) and divide the key field value by this number. The remainder identifies the storage address.

FUNCTION HashNumeric(key : INTEGER) : INTEGER
  CONSTANT divisor = 1000 // Prime number similar to expected file size
  address ← key MOD divisor
  RETURN address
ENDFUNCTION
Examples:
  • 0045 MOD 1000 = 45 → Address 45
  • 2005 MOD 1000 = 5 → Address 5
  • 3005 MOD 1000 = 5 → Address 5 (Collision!)

Hashing for Non-Numeric Key Fields

Convert characters to ASCII codes, sum them, then use the sum in the same way as numeric keys.

FUNCTION HashString(key : STRING) : INTEGER
  sum ← 0
  FOR i ← 1 TO LENGTH(key) DO
    asciiValue ← ASC(key[i])
    sum ← sum + asciiValue
  ENDFOR
  RETURN sum MOD 1000
ENDFUNCTION
Example:

"AB" → ASCII(A)=65, ASCII(B)=66 → Sum=131 → 131 MOD 1000 = 131

Address Collisions

A collision occurs when different key field values produce the same storage address. This is a common issue with hashing algorithms that needs to be addressed.

1. Sequential Search

Look for the next vacant address following the calculated one. Continue searching sequentially until an empty slot is found.

2. Overflow Areas

Maintain overflow addresses at the end of the file. When a collision occurs, store the record in the overflow area.

3. Linked Lists

Have a linked list accessible from each address. Colliding records are stored in the linked list associated with that address.

Activity 13C: Hashing Algorithm Practice

Difficulty: Hard • Estimated time: 12 minutes

Using a divisor of 11, calculate the storage addresses for the following customer IDs using a hashing algorithm:

  1. Customer ID: 45
  2. Customer ID: 127
  3. Customer ID: 89
  4. Customer ID: 312
  5. Which of these would result in a collision if we also had Customer ID: 34?
  1. 45 MOD 11 = 1 → Address 1
  2. 127 MOD 11 = 6 → Address 6
  3. 89 MOD 11 = 1 → Address 1 (Collision with Customer 45!)
  4. 312 MOD 11 = 4 → Address 4
  5. 34 MOD 11 = 1 → Address 1. This would collide with Customer 45 and Customer 89.

Note: When collisions occur, we need to use collision resolution techniques like sequential search for the next available slot, overflow areas, or linked lists.

Key Takeaways

  • Text files are human-readable and use character encoding; binary files store data in internal representation
  • Serial organization stores records in order of arrival; sequential organizes by key field; random uses hashing
  • Sequential access reads records one after another; direct access finds records using indexes or hashing
  • Hashing algorithms convert key fields to storage addresses using division or ASCII summation
  • Address collisions occur when different keys produce the same address, resolved through various techniques
  • Choose file organization based on access patterns: serial for temporary data, sequential for batch processing, random for frequent individual access
  • Select access method based on hit rate: sequential for high hit rates, direct for low hit rates
  • Prime numbers work best as divisors in hashing algorithms to minimize collisions

Question Bank

Marking Scheme

a) [2 marks] Record, field.

b) [3 marks] A text file contains character data, formatted into lines, there are end-of-line and end-of-file characters. A binary file has data in internal representation, contains records with a defined format. There is no need for field separator characters or for an end-of-record character.

Additional Notes for Slow Learners
  • Think of a binary file like a custom-made storage box with specific compartments for specific items
  • A text file is like a notepad where you write things in sentences that anyone can read
  • Binary files need a "manual" (program) to understand them, while text files can be read directly
Marking Scheme

a) [4 marks] No defined order for serial, searching a serial file requires reading complete records until the data is found. Defined order for sequential, direct-access file has a position for a record which is computed using an algorithm, a sequential or direct-access file has a key field used when searching for data.

b) [3 marks] A serial file is typically used to store data temporarily as it becomes available with the intention of processing every single record at some future time. Examples are: any commercial or business transaction file, a file recording the ongoing progress of a sporting contest to be used later to create statistics.

c) [3 marks] Typical use is for long-term storage of data when the contents will be continuously changing and individual data items will needed to be looked up. Example: customer database where individual customer records need to be accessed frequently.

Additional Notes for Slow Learners
  • Serial file = Inbox where papers arrive and stay in arrival order
  • Sequential file = Filing cabinet with folders in alphabetical order
  • Direct access = Library with a computer that tells you exactly which shelf has your book
  • Serial is good for logs; sequential for reports; direct for databases
Marking Scheme

[4 marks] Sequential access starts reading from the beginning of the file. Each record is checked until either the target record is found, or a record with a key field greater than the target key is encountered. Since records are sorted in ascending key order, if a greater key is found, the target cannot exist later in the file, so the search stops.

Marking Scheme

[2 marks] A hashing algorithm performs a calculation on the key field of a record to determine its storage address in a file.

[3 marks] For numeric keys: Choose a suitable divisor (preferably prime). Divide the key by this divisor. The remainder gives the storage address. Example: key = 45, divisor = 11, address = 45 MOD 11 = 1.

Marking Scheme

[2 marks] An address collision occurs when different key field values produce the same storage address from a hashing algorithm.

[4 marks] Two handling methods:

  • Sequential search: Look for the next available address following the calculated one
  • Overflow areas: Maintain separate areas at the end of the file for colliding records
  • Linked lists: Store colliding records in a linked list associated with that address

Marking Scheme

[5 marks]

  • Similarities: Both store records one after another; both can use sequential access
  • Differences: Serial has no defined order (chronological arrival); sequential is ordered by key field. Serial appends new records at end; sequential inserts in correct position. Searching serial requires checking all records; sequential search can stop early when a greater key is found.

Marking Scheme

[3 marks] Prime numbers help distribute addresses more evenly across the available range, reducing the likelihood of collisions. When a prime is used as a divisor, remainders tend to be more uniformly distributed compared to non-prime divisors, especially when keys have patterns or regularities.

Marking Scheme

[4 marks] Convert each character to its ASCII code value. Sum all the ASCII values to get a numeric total. Use this total as input to the hashing algorithm (e.g., take the remainder after division by a prime number). Example: "AB" → A=65, B=66 → Sum=131 → 131 MOD prime = address.

Marking Scheme

[4 marks] Direct access is recommended when the file has a low hit rate (only a few records need to be accessed at a time) and quick access to individual records is important. Example: A customer database where individual customer records need to be looked up or updated frequently, such as when a customer calls to change their phone number.

Marking Scheme

[5 marks]

  • 34 MOD 13 = 8 → Address 8
  • 78 MOD 13 = 0 → Address 0
  • 123 MOD 13 = 6 → Address 6
  • 256 MOD 13 = 9 → Address 9
  • No collisions in this set as all addresses are unique.