Show understanding of methods of file organization: serial, sequential (using a key field), random (using a record key)
Select an appropriate method of file organization and file access for a given problem
Show understanding of methods of file access: sequential access for serial and sequential files, direct access for sequential and random files
Show understanding of hashing algorithms
Describe and use different hashing algorithms to read from and write data to a random/sequential file
Understand collision handling strategies
📖 Prior Knowledge Required
Understanding of files and file types (text files and binary files)
Knowledge of records and fields in data storage
Basic understanding of primary and secondary storage
Understanding of key fields and unique identifiers
Knowledge of file operations (create, read, write, append)
🌟 Did You Know?
Computers are used to access vast amounts of data and to present it as useful information. Millions of people expect to be able to retrieve the information they need in a useful form when they ask for it. This information is all stored as data in files, everything from bank statements to movie collections. In order to be able to find data efficiently, it needs to be organized.
1. File Types
In everyday computer usage, a wide variety of file types is encountered. Examples are graphic files, word-processing files, spreadsheet files and so on. Whatever the file type, content is stored using a specific binary code that allows the file to be used as intended. There are only two defined file types.
1.1 Text Files
📖 Definition: Text File
A text file contains data stored according to a character code of type. It is possible, by using a text editor, to create a text file to be used as input to a program.
Text files are stored as a sequence of characters
Each character is represented by one byte (8 bits)
Most common character encoding is ASCII
Text files can be easily read and written by humans
Examples: .txt files, .csv files
📝 Organization of Text Files
Number of data items per line must be known
Number of characters per item must be known
If these are not known, item separator characters must be used
File has repeating lines defined by an end-of-line character
1.2 Binary Files
📖 Definition: Binary File
A binary file is designed for storing data to be used by a computer program. Binary files are stored as a sequence of bytes representing any data including text, numbers, images, and sounds.
Binary files are not human-readable
Can only be opened by programs that understand the binary format
Stores data in its internal representation
Examples: .exe files, .jpg files
📝 Organization of Binary Files
Based on concept of a record
A file contains records and each record contains fields
Each field consists of a value
Number of fields per record must be known
No need for field separator characters or end-of-record character
2. File Organization Methods
The way records are arranged within a file is called the file's organization method. Choosing the right method affects how quickly data can be searched, added, updated, or deleted.
2.1 Serial File Organization
📖 Definition: Serial File Organization
A method of file organization in which records of data are physically stored in a file, one after another, in the order they were added to the file.
Records are stored in chronological order
Data is NOT necessarily organized or sorted
Records are often appended to the end in real-time
Simple to implement, but slow to search
Example: Logging sensor data at a remote weather station. As each transaction is added to the file in the order of arrival, these records will be in chronological order. Storing customer meter readings for gas or electricity before they are used to send bills to all customers.
🌟 When to Use Serial Files?
Chronological order matters - For legal or historical records where sequence is critical
Easy to append - Beneficial for log files where data is continuously added
No re-organization required - Ideal for systems with limited processing power
Small files - Suitable for cases where the dataset remains relatively small
No key fields needed - Simplifies the structure of the data storage
2.2 Sequential File Organization
📖 Definition: Sequential File Organization
A method of file organization in which records of data are physically stored in a file, one after another, in a given order. The order is usually based on the key field of the records as this is a unique identifier.
Records are stored in a predetermined order (not necessarily chronological)
Sorted based on key field values
More efficient for searches than serial files
Searching can stop once the target is passed
Example: A file used by a supplier to store customer records for gas or electricity in order to send regular bills to each customer. All records are stored in ascending customer number order, where the customer number is the key field that uniquely identifies each record.
💡 Key Difference: Serial vs Sequential
Serial: Records in order of arrival (chronological), no sorting
Sequential: Records in sorted order based on key field
Sequential files are ideal for master files and batch processing applications such as payroll systems
2.3 Random File Organization
📖 Definition: Random File Organization
A method of file organization in which records of data are physically stored in a file in any available position. The location of any record in the file is found by using a hashing algorithm on the key field of a record.
Records stored in random order within the file
Pre-defined relationship between the key of the record and its location
Location calculated using hashing algorithm
Records can be added at any empty position
Fastest way to search through stored data
Example Use Cases: Bank account access where individual customer records need instant lookup, real-time stock updates where specific records are accessed frequently, database systems requiring fast individual record access.
Organization Type
Order
Best Use Case
Serial
Chronological (arrival)
Log files, temporary transaction files
Sequential
Sorted by key field
Payroll, billing, batch processing
Random
Calculated by hashing
Real-time systems, bank accounts
3. File Access Methods
File access is the method used to physically find a record in the file. There are two main methods of file access: sequential access and direct access.
3.1 Sequential Access
📖 Definition: Sequential Access
A method of file access in which records are searched one after another from the physical start of the file until the required record is found. This method is used for serial and sequential files.
📝 How Sequential Access Works
For Serial Files:
Every record needs to be checked until the record is found
Or the whole file has been searched without finding the record
New records are appended to the end of the file
For Sequential Files:
Records checked until found OR key field of current record is greater than search key
Rest of file does not need to be searched (records are sorted)
New records must be inserted in the correct position
Example: If searching for Customer 6 in a sequential file sorted by customer number, each record would be read until Customer 7 was reached. Then it would be assumed that Customer 6 was not stored in the file. No need to search further!
⚠️ Important: Hit Rate
Sequential access is efficient when every record in the file needs to be processed, for example, a monthly billing or payroll system. These files have a high hit rate during processing as nearly every record is used when the program is run.
3.2 Direct Access
📖 Definition: Direct Access
A method of file access that can physically find a record in a file without other records being physically read. Both sequential and random files can use direct access. This allows specific records to be found more quickly than using sequential access.
📝 How Direct Access Works
For Sequential Files:
An index of all key fields is kept
Index is used to look up the address of the file location
For large files, searching the index takes less time than searching the whole file
For Random Files:
A hashing algorithm is used on the key field
Calculates the address of the file location directly
Provides fastest access to individual records
Example: When a single customer record needs to be updated when the customer's phone number is changed. Here, the file being processed has a low hit rate as only one of the records in the file is used.
Access Method
Used With
Best For
Hit Rate
Sequential
Serial & Sequential files
Batch processing, payroll, billing
High
Direct
Sequential (with index) & Random files
Real-time systems, individual record lookup
Low
4. Hashing Algorithms
📖 Definition: Hashing Algorithm
A hashing algorithm is a mathematical formula used to perform a calculation on the key field of a record. The result of the calculation gives the address where the record should be found.
4.1 How Hashing Works
📝 Hashing Algorithm Example
If a file has space for 2000 records and the key field can take any values between 1 and 9999, the hashing algorithm could use:
Address = (Key Field MOD File Size) + Start Address
Example Calculation:
Key field value: 3024
File size: 2000 records
Start address: 0
Calculation: 3024 MOD 2000 = 1024
Record stored at address 1024
4.2 Types of Hashing Algorithms
Method
Description
Example
Modulo Division
Most common method: Key MOD TableSize
3024 MOD 2000 = 1024
Folding
Breaks the key into parts and adds them together
30 + 24 = 54
Mid-Square
Square the key and use middle digits as address
3024² = 9144576 → 445
Truncation
Use only part of the key
3024 → Use last 3 digits: 024
🌟 Properties of Good Hashing Algorithm
Quick to calculate - Efficient computation
Cover complete range - Use full address space
Even distribution - Spread records evenly
Minimize collisions - Avoid clustering at same addresses
4.3 Collision Handling
📖 Definition: Collision
A collision occurs when the same address is calculated for different key field values. This happens when different keys produce the same remainder when divided by the file size.
⚠️ Collision Example
Using the hashing algorithm: Address = Key MOD 2000
Key 3024: 3024 MOD 2000 = 1024
Key 5024: 5024 MOD 2000 = 1024 ← COLLISION!
Both keys produce the same address 1024
4.4 Collision Resolution Strategies
📝 Strategy 1: Open Hash (Linear Probing)
Store the record in the next free space
Also called linear probing
Simple to implement
When reading, check calculated address, then check subsequent addresses until match found
📝 Strategy 2: Closed Hash (Overflow Area)
An overflow area is set up
Store conflicting records in next free space in overflow area
Keeps main file organized
When reading, search overflow area if key doesn't match at calculated address
📝 Strategy 3: Chaining
Store all records with same address in a linked list
Each address has a pointer to a chain of records
Efficient for handling multiple collisions
Additional memory needed for pointers
💡 Exam Tip: Key Verification
When reading a record using direct access:
Calculate address using hashing algorithm
Read record at that address
Check key field matches the original key
If not matching, apply collision resolution (search next location or overflow area)
4.5 Hashing for Non-Numeric Keys
Hashing algorithms can also be used to calculate addresses from names and other non-numeric data.
📝 Converting Text to Address
Look up the ASCII code for each character in the name
Add all the ASCII values together
Divide the sum by the number of locations in the file
Use the remainder as the address
Example: Converting name "ABC" to an address for a file with 1000 locations:
'A' = 65, 'B' = 66, 'C' = 67
Sum = 65 + 66 + 67 = 198
198 MOD 1000 = 198
Address = 198
❌ Common Mistakes
Forgetting to verify the key field when reading a record
Not handling collisions properly
Using a file size that causes many collisions (use a prime number for better distribution)
Assuming the calculated address always contains the correct record
5. Key Takeaways
📌 Summary Points
File Organization
Serial: Records in order of arrival, chronological, no sorting needed
Sequential: Records sorted by key field, efficient for batch processing
Random: Records at calculated positions using hashing, fastest individual access
File Access
Sequential Access: Read records one by one from start, used with serial/sequential files
Direct Access: Jump to specific record using index or hash, used with sequential/random files
Hashing
Purpose: Calculate storage location from key field
Serial files are simpler to implement but slower to search
Sequential files allow early termination of search when target is passed
Sequential files require re-sorting when new records are added
2. A file stores 1000 records. The key field values range from 1 to 9999. A hashing algorithm uses MOD 1000 to calculate the address. Calculate the address for a record with key field value 7563. [2 marks]
Answer:
Address = 7563 MOD 1000
7563 ÷ 1000 = 7 remainder 563
Address = 563
3. Explain what is meant by a collision in hashing, and describe two methods for handling collisions. [6 marks]
Answer:
Collision: When two different key field values produce the same address when a hashing algorithm is applied.
Methods for handling collisions:
Open hash (Linear probing): Store the record in the next available free space. When reading, check the calculated address then subsequent addresses until match found.
Closed hash (Overflow area): Set up a separate overflow area. When collision occurs, store record in next free space in overflow area. Search overflow area if key doesn't match.
Chaining: Store all records with same calculated address in a linked list. Each address has a pointer to a chain of records.
4. Describe the difference between sequential access and direct access. When would each be appropriate? [5 marks]
Answer:
Sequential access: Records searched one after another from start of file until required record found
Direct access: Record found without reading other records; can jump directly to specific location
Sequential appropriate: High hit rate, batch processing, payroll/billing systems, reading entire file
Direct appropriate: Low hit rate, individual record lookup, real-time systems, bank account access
Sequential used with serial and sequential files; Direct used with sequential (with index) and random files
5. A binary file is to be used to store data for a program. (a) State the terms used to describe the components of such a file. (b) Explain the difference between a binary file and a text file. [5 marks]
Answer (a):
Record: A collection of related data fields representing one item
Field: A single piece of data within a record (e.g., name, ID number)
Answer (b):
Text file: Contains character data formatted into lines; has end-of-line and end-of-file characters; human-readable; uses ASCII encoding
Binary file: Data stored in internal representation; contains records with defined format; no field separator characters needed; not human-readable
Text files can be opened with text editors; binary files require specific programs
6. Exam-Style Questions (continued)
6. Explain how a hashing algorithm could be used to calculate an address from a person's name "JONES". The file has space for 500 records. [4 marks]
Answer:
Find ASCII value for each character: J=74, O=79, N=78, E=69, S=83
Add values together: 74 + 79 + 78 + 69 + 83 = 383
Divide by file size and find remainder: 383 MOD 500 = 383
Address = 383
Additional points:
Must verify the key field matches when reading back from this address
If collision occurs, apply collision resolution strategy
7. A company needs to choose a file organization method for their customer database. Customers frequently need to look up their account details individually. Which file organization and access method would be most appropriate? Justify your answer. [4 marks]
Answer:
Use random file organization with direct access
Reason: Individual customer records need to be accessed frequently (low hit rate)
Direct access allows quick lookup of specific records without searching through entire file
Hashing algorithm can calculate exact location from customer ID/account number
More efficient than sequential access for individual lookups
8. Describe three properties of a good hashing algorithm. [3 marks]
Answer:
Quick to calculate: The algorithm should be computationally efficient
Even distribution: Records should be spread evenly across the available address space
Minimize collisions: Should not generate addresses that cluster, causing frequent collisions
Cover complete range: Should use the full address space available in the file
9. A file is stored at address 500. Each record takes up 5 locations and there is space for 1000 records. The key field values range from 1 to 9999. Using the hashing algorithm: Address = Start Address + (Key MOD FileSize) × RecordSize, calculate the address for a record with key field value 9354. [3 marks]
Answer:
Remainder: 9354 MOD 1000 = 354
Offset: 354 × 5 = 1770
Address: 500 + 1770 = 2270
If collision occurs with open hash, next location would be:
Next address = 2270 + 5 = 2275
10. Compare the use of serial, sequential, and random file organization for the following scenarios. Justify each choice: (a) Recording daily rainfall readings at a remote weather station, (b) Providing annual tax statements for employees, (c) Real-time bank ATM transactions. [6 marks]
Answer:
(a) Remote weather station:
Serial - Data recorded in chronological order as it arrives
No need for sorting; data collected in real-time
Simple to append new readings; processed later in batch
(b) Annual tax statements:
Sequential - Employee records sorted by ID/key field
High hit rate - processing all employees at end of year
Efficient batch processing for generating all statements
(c) Bank ATM transactions:
Random - Individual account access required
Low hit rate - only one account accessed per transaction
Direct access using account number for fast lookup
7. Glossary
Serial File Organization → A method of file organization in which records are stored one after another in the order they were added to the file (chronological order).
Sequential File Organization → A method of file organization in which records are stored one after another in a given order, usually based on the key field.
Random File Organization → A method of file organization in which records are stored in any available position, with locations calculated using a hashing algorithm on the key field.
File Access → The method used to physically find a record in a file.
Sequential Access → A method of file access in which records are searched one after another from the start of the file until the required record is found.
Direct Access → A method of file access that can find a record without reading other records, using an index or hashing algorithm.
Hashing Algorithm → A mathematical formula used to calculate the storage address of a record from its key field.
Collision → When two different key field values produce the same address when a hashing algorithm is applied.
Open Hash (Linear Probing) → A collision resolution method where records are stored in the next available free space.
Closed Hash (Overflow Area) → A collision resolution method where a separate overflow area is used to store records that collide.
Key Field → A unique identifier field in a record used for searching and organizing data.
Hit Rate → The proportion of records accessed during a processing run. High hit rate = most records accessed; Low hit rate = few records accessed.
Text File → A file containing data stored as characters according to a character code (e.g., ASCII), human-readable.
Binary File → A file containing data in internal representation format, not human-readable, organized as records with fields.
8. Exam Success Tips
💡 Remember: Serial vs Sequential
Serial = Arrival order (like a log, chronological)
Sequential = Sorted order (by key field, like a phone book)
Serial: Easy to add, hard to search specific records
Sequential: Can stop searching early when target passed
💡 Remember: Access Methods
Sequential Access: Read from start, one by one
Direct Access: Jump directly to record using index or hash
High hit rate (batch processing) → Sequential access
Low hit rate (individual lookup) → Direct access
🧠 Memory Trick: File Organization
Serial → "S" for Simple, Straight chronological
Sequential → "S" for Sorted, Structured order
Random → "R" for Rapid access, calculated locations
💡 Hashing Formula
Most common hashing method:
Address = Key MOD FileSize
Example: 3024 MOD 2000 = 1024 (address)
❌ Common Mistakes to Avoid
Confusing serial (chronological) with sequential (sorted)
Forgetting to mention key field verification when reading hashed records
Not explaining why a particular organization is chosen
Forgetting that direct access can work with both sequential (with index) and random files
Not mentioning hit rate when justifying access method choice
8. Exam Success Tips (continued)
🧠 Collision Resolution Methods
Open Hash → Open the door to the next room (next free space)
Closed Hash → Closed off, use overflow area instead
Chaining → Chain links together (linked list)
💡 Answer Structure Tips
For "explain" questions: Give reasons WHY
For "compare" questions: Use a table and mention BOTH items for each point
For "justify" questions: Link the choice to the scenario requirements
Always use technical terms: key field, hashing algorithm, collision, hit rate
Mark allocations give hints: [4 marks] = 4 distinct points needed
⚠️ Must Mention When Asked About...
Serial files: Chronological order, no sorting, simple append
Sequential files: Key field, sorted order, early search termination
Random files: Hashing algorithm, direct access, collision handling
Hashing: Key field verification, collision resolution strategies
Access method choice: Hit rate, processing requirements
🌟 Quick Reference: Decision Tree
Need to process ALL records? → Sequential access
Need to find ONE record quickly? → Direct access
Data arrives in real-time? → Serial organization
Data needs sorting? → Sequential organization
Need instant individual access? → Random organization with hashing
📌 Final Exam Checklist
✓ Know all three file organization types and when to use each
✓ Understand both access methods and link to hit rate