File organisation — serial, sequential, random; file access methods; hashing

File organisation determines how records are physically stored on the storage medium. The choice affects access speed, storage efficiency, and ease of maintenance.

• Records written in the order they arrive
• No sorting by key
• Access: Sequential only (must read from start)
• Insertion: Append at end (fast)
• Deletion: Mark as deleted; periodic reorganisation needed
• Update: Read entire file, modify in memory, rewrite (slow)

Example: A transaction log where each entry is appended with a timestamp.

• Records stored in ascending/descending order of a key field (e.g., EmployeeID)
• Access: Sequential (can stop early when key is passed)
• Insertion: Must shift subsequent records or use overflow area
• Deletion: Mark as deleted; periodic reorganisation
• Update: May require rewriting if key changes

Example: A customer master file sorted by CustomerID, processed monthly for statements.

• Record address calculated from key using a hashing algorithm
• Access: Direct (O(1) average) — go straight to calculated address
• Insertion: Hash key -> address; if occupied, use collision resolution
• Deletion: Mark slot as deleted; may need special handling for collision chains
• Update: Direct access to record; fast if key unchanged

Example: A student record system where StudentID hashes to a disk address for instant lookup.

Sequential access — read records one after another from the beginning.

• Used with: serial files, sequential files
• Required for: serial files; optional for sequential/random

Direct (random) access — jump straight to a specific record by address.

• Used with: random files (essential); also possible with sequential files if index exists
• Requires: ability to calculate or look up record address

Choosing access method:

• Process all records in order → sequential access
• Need specific record by key → direct access (requires random organisation or index)
• Mixed workload → random organisation with direct access

A hash function maps a key (e.g., StudentID) to a storage address (block/record number).

Desirable properties:

• Uniform distribution (minimise collisions)
• Fast to compute
• Deterministic (same key always gives same address)

Common hash functions:

1. Division method: address = key MOD tableSize
   • tableSize should be a prime number for better distribution
2. Mid-square method: Square the key, take middle digits
3. Folding method: Split key into parts, add them, take MOD tableSize
4. Multiplication method: address = floor(tableSize * frac(key * A)) where 0 < A < 1

Example (division method):

• Table size = 13 (prime)
• Key = 12345
• Address = 12345 MOD 13 = 8

Collision resolution:

• Linear probing: If address occupied, try (address + 1) MOD size, then +2, etc.
• Chaining: Each address holds a linked list of records with that hash
• Rehashing: Apply a second hash function