File organisation and access

A file of records can be arranged on backing store in different ways, and the arrangement decides how quickly a particular record can be found. File organisation is how the records are placed in the file; file access is how a program gets to them. Paper 3 asks you to describe serial, sequential and random organisation, to choose the right one for a scenario, and to calculate where a record goes using a hashing algorithm; Paper 4 asks you to write the code that reads and writes such files.

Records, fields and keys

A data file is a collection of records, each made up of fields. In a file of students, each record is one student; LastName, YearGroup and StudentID are fields. The records usually all have the same user-defined type.

Choosing a good key matters. A surname is a bad key (two students can share it); a generated ID is a good one.

The three methods of file organisation

Serial files

In a serial file, records are stored one after another in the order in which they were added, with each new record appended at the end. There is no ordering by key.

Serial files are the simplest possible arrangement. Writing is fast (always append). Finding a record is slow: there is no way to know where it is, so the file must be read from the start until it is found, or to the end if it is absent.

Typical uses: a log of transactions as they happen during the day, a file of readings from a sensor, a temporary file that will be sorted later, an audit trail. These are all files that are written in time order and later processed from beginning to end.

Sequential files

In a sequential file, records are stored in order of a key field, for example in ascending order of StudentID.

Because the order is known, a search can stop as soon as it reaches a key greater than the one wanted, and two sorted files can be merged efficiently. Adding or deleting a record is harder: to keep the order, the whole file must be copied to a new file, with the new record written in the right place (or the deleted record skipped).

Typical uses: a master file that is processed in full as a batch, such as a payroll file processed once a month or a utility company's customer file used to produce bills. Almost every record is read every time, so reading in order costs nothing extra.

Random files

In a random file (also called a direct-access or hashed file), the position of each record is calculated from its key by a hashing algorithm. The records are not in key order and not in time order; they are wherever the hash puts them.

To read a record, the program hashes the key to get the address and goes straight there. That makes access to an individual record very fast regardless of the size of the file.

Typical uses: any system that must find one record quickly in response to a request, such as a supermarket's product file used at the checkout, a bank's account file used at a cash machine, or a seat-booking system.

Methods of file access

Organisation and access are different things. Organisation is the layout; access is how a program reaches records.

A sequential file with an index is called an indexed sequential file. The index stores, for groups of keys, the address where that part of the file begins. To find a record, the program looks up the key in the index, jumps to the right part of the file, and reads forward a short distance. The same file can therefore be processed in batch (sequential access, in key order) and queried for single records (direct access via the index).

Choosing an organisation: hit rate and response time

Two ideas decide most exam answers.

• The hit rate is the proportion of records that are accessed in one run of a program. Producing monthly bills for every customer is a 100% hit rate; a sequential file read from start to end is ideal. Looking up one customer when they phone is a tiny hit rate; direct access is needed.
• The response time needed. If a person is waiting (at a checkout, on a phone call), direct access is required. If the job runs overnight, sequential processing is fine.

Volatility (how often records are added and deleted) matters too: a sequential file is costly to change, a random file is cheap to change, and a serial file is cheapest to add to but costly to search.

Hashing algorithms

A hashing algorithm (hash function) takes a record's key and calculates an address in the file. The same key always gives the same address, so the record can be written there and found there again later.

The most common algorithm divides by the number of available positions and takes the remainder:

Other algorithms you should be able to describe and use:

• Folding: split the key into equal parts, add the parts, then (if necessary) take the result MOD the file size. Key 34567812 split into pairs gives $34 + 56 + 78 + 12 = 180$; with 97 positions, $180 \bmod 97 = 83$.
• Digit extraction: use selected digits of the key, for example the last three digits of 2041763 give address 763 in a 1000-record file.
• Character keys: convert each character to its character code (ASCII or Unicode), add (or combine) the codes, and take MOD the file size. "CAT" gives $67 + 65 + 84 = 216$.

A good hashing algorithm is quick to calculate, always produces a valid address, and spreads keys evenly across the file so that few keys share an address.

Collisions

A collision occurs when two different keys hash to the same address. It is unavoidable when there are more possible keys than addresses. There are two standard ways to deal with it.

Collisions cost time: a record that has been displaced takes extra reads to find. As the file fills up, collisions become more frequent, which is why random files are created with more positions than the expected number of records.

Step 4 of the read is why deleting from an open-hashed file needs care: if you simply empty a position, a search for a record that was displaced past it will stop too early. Deleted positions are therefore marked as "deleted" rather than "empty", so searches continue past them while inserts can reuse them.

Random files in pseudocode

Cambridge pseudocode opens a random file with OPENFILE ... FOR RANDOM, moves the file pointer with SEEK, and reads and writes whole records with GETRECORD and PUTRECORD. The address in SEEK is a record number counted from the start of the file.

TYPE Product
   DECLARE ProductCode : INTEGER     // 0 means the position is empty
   DECLARE Description : STRING
   DECLARE Price : REAL
ENDTYPE

CONSTANT FileSize = 11

// writes NewItem to ProductFile.dat using linear probing
PROCEDURE AddProduct(NewItem : Product)
   DECLARE Address, Start : INTEGER
   DECLARE Current : Product
   DECLARE Placed : BOOLEAN
   Address ← NewItem.ProductCode MOD FileSize
   Start ← Address
   Placed ← FALSE
   OPENFILE "ProductFile.dat" FOR RANDOM
   REPEAT
      SEEK "ProductFile.dat", Address
      GETRECORD "ProductFile.dat", Current
      IF Current.ProductCode = 0 THEN
         SEEK "ProductFile.dat", Address
         PUTRECORD "ProductFile.dat", NewItem
         Placed ← TRUE
      ELSE
         Address ← (Address + 1) MOD FileSize
      ENDIF
   UNTIL Placed = TRUE OR Address = Start
   CLOSEFILE "ProductFile.dat"
   IF Placed = FALSE THEN
      OUTPUT "File is full"
   ENDIF
ENDPROCEDURE

The second SEEK before PUTRECORD is good practice: it makes clear the record is written at the position just examined rather than wherever the pointer moved after the read.

Random files in Python

Python has no record type and no GETRECORD, but genuine direct access is possible with fixed-length records. The struct module packs a record into a fixed number of bytes, so record number $p$ starts at byte $p \times \text{record size}$ and seek can jump straight to it.

import struct

FILE_SIZE = 11                       # record positions 0 to 10
RECORD = struct.Struct("<i20sd")     # int code, 20-byte description, float price
FILENAME = "ProductFile.dat"

def create_file():
    with open(FILENAME, "wb") as f:
        for _ in range(FILE_SIZE):
            f.write(RECORD.pack(0, b"", 0.0))   # code 0 marks an empty position

def read_record(f, address):
    f.seek(address * RECORD.size)
    code, desc, price = RECORD.unpack(f.read(RECORD.size))
    return code, desc.rstrip(b"\0").decode(), price

def write_record(f, address, code, desc, price):
    f.seek(address * RECORD.size)
    f.write(RECORD.pack(code, desc.encode(), price))

def add_product(code, desc, price):
    with open(FILENAME, "r+b") as f:
        address = start = code % FILE_SIZE
        while True:
            if read_record(f, address)[0] == 0:
                write_record(f, address, code, desc, price)
                return address
            address = (address + 1) % FILE_SIZE
            if address == start:
                raise IOError("File is full")

def find_product(code):
    with open(FILENAME, "rb") as f:
        address = start = code % FILE_SIZE
        reads = 0
        while True:
            record = read_record(f, address)
            reads += 1
            if record[0] == code:
                return address, record, reads
            if record[0] == 0:
                return None, None, reads          # empty slot: not in file
            address = (address + 1) % FILE_SIZE
            if address == start:
                return None, None, reads

create_file()
for code, desc in [(1045, "Kettle"), (2391, "Toaster"), (4412, "Lamp"),
                   (7735, "Fan"), (1001, "Iron"), (3335, "Mixer")]:
    print(code, "stored at", add_product(code, desc, 9.99))

print(find_product(3335))
print(find_product(9999))

Output:

1045 stored at 0
2391 stored at 4
4412 stored at 1
7735 stored at 2
1001 stored at 3
3335 stored at 5
(5, (3335, 'Mixer', 9.99), 4)
(None, None, 7)

Updating a sequential file

Because a sequential file must stay in key order, records cannot simply be inserted. Instead, the changes (the transaction file) are sorted into the same key order and merged with the old master file to produce a new master file. The old master is kept as a backup (the "grandfather–father–son" idea).

# merging two lists of records already sorted by key (key, name)
old_master = [(101, "Ahmed"), (104, "Bella"), (110, "Chen"), (115, "Dara")]
new_records = [(102, "Eve"), (112, "Femi"), (120, "Gita")]

new_master = []
i = j = 0
while i < len(old_master) and j < len(new_records):
    if old_master[i][0] < new_records[j][0]:
        new_master.append(old_master[i]); i += 1
    else:
        new_master.append(new_records[j]); j += 1
new_master.extend(old_master[i:])      # copy whatever is left
new_master.extend(new_records[j:])

print(new_master)

Output: [(101, 'Ahmed'), (102, 'Eve'), (104, 'Bella'), (110, 'Chen'), (112, 'Femi'), (115, 'Dara'), (120, 'Gita')].

Worked examples

FUNCTION FindProduct(Code : INTEGER) RETURNS INTEGER
   DECLARE Address, Start, Result : INTEGER
   DECLARE Current : Product
   DECLARE Finished : BOOLEAN
   Address ← Code MOD 11
   Start ← Address
   Result ← -1
   Finished ← FALSE
   OPENFILE "ProductFile.dat" FOR RANDOM
   REPEAT
      SEEK "ProductFile.dat", Address
      GETRECORD "ProductFile.dat", Current
      IF Current.ProductCode = Code THEN
         Result ← Address
         Finished ← TRUE
      ELSE
         IF Current.ProductCode = 0 THEN
            Finished ← TRUE                 // empty position: not present
         ELSE
            Address ← (Address + 1) MOD 11
            IF Address = Start THEN
               Finished ← TRUE              // whole file searched
            ENDIF
         ENDIF
      ENDIF
   UNTIL Finished = TRUE
   CLOSEFILE "ProductFile.dat"
   RETURN Result
ENDFUNCTION

Practice questions

```pseudocode

DECLARE Address : INTEGER
DECLARE Current : Product
OPENFILE "ProductFile.dat" FOR RANDOM
FOR Address ← 0 TO 10
   SEEK "ProductFile.dat", Address
   GETRECORD "ProductFile.dat", Current
   IF Current.ProductCode <> 0 THEN
      OUTPUT Current.ProductCode, " ", Current.Description, " ", Current.Price
   ENDIF
NEXT Address
CLOSEFILE "ProductFile.dat"
```

```python
def hash_name(name, size):
    total = 0
    for ch in name:
        total += ord(ch)
    return total % size

print(hash_name("STOP", 50), hash_name("POTS", 50))   # 26 26: collision

def hash_name_weighted(name, size):
    total = 0
    for position, ch in enumerate(name, start=1):
        total += position * ord(ch)      # weight each code by its position
    return total % size

print(hash_name_weighted("STOP", 50), hash_name_weighted("POTS", 50))   # 8 22
```

`S`, `T`, `O`, `P` have codes 83, 84, 79, 80. Both words total $83 + 84 + 79 + 80 = 326$, and $326 \bmod 50 = 26$, so they collide. Weighting each code by its position gives $1(83) + 2(84) + 3(79) + 4(80) = 808$ for `"STOP"` (address 8) and $1(80) + 2(79) + 3(84) + 4(83) = 822$ for `"POTS"` (address 22), so the anagrams no longer collide.