Fields, records and file organisation

Text and binary files, fixed-length records, and serial, sequential, indexed sequential and direct access files.

A3.8Data structuresA level25 min

Data in memory is lost when the program ends; data that must last is kept in files on storage. At GCSE (F7.1) you read and wrote CSV files line by line. At A level you need to know how the records in a file are laid out, and how that layout decides whether finding one record takes one step or means reading the whole file.

Fields, records and files

• A field is one item of data about something: a robot's id, its name, its best distance.
• A record is all the fields about one thing: one robot.
• A file is a collection of records, usually all with the same fields in the same order.
• A key field uniquely identifies each record, such as the id.

In a variable-length record, each field takes as many characters as it needs, as in a CSV file: 101,Ada,42.0. In a fixed-length record, every field has a set width, padded with spaces, so every record is exactly the same size. Fixed-length records waste some space, but they make it possible to work out where record number n starts: n × record length. The program can then seek straight to it instead of reading everything before it.

101,Ada   ,42.0
104,Bolt  ,41.0
105,Echo  ,36.0
107,Cog   ,45.5
110,Dot   ,47.5
112,Fizz  ,39.0
115,Gear  ,44.5
118,Hex   ,40.5

Each record in fixed.txt is 3 characters of id, a comma, 6 of name, a comma, 4 of distance and a newline: 16 characters.

RECORD = 16                              # every record is exactly 16 characters, newline included

f = open("fixed.txt")
f.seek(3 * RECORD)                       # jump straight to record number 3 (counting from 0)
print(f.read(RECORD - 1))
f.seek(0 * RECORD)
print(f.read(RECORD - 1))
f.close()

Run this in the simulator

Text files and binary files

A text file stores everything as characters, so 45.5 takes four characters and a person can read the file in any editor. A binary file stores values in their internal form: an integer as a fixed number of bytes, a real as a floating-point number. Binary files are smaller and quicker to read back, and every record is naturally the same length, but they make no sense in a text editor, and the program reading them must know the exact layout.

Python's struct module turns values into bytes and back:

import struct

record = struct.pack("<Hf", 107, 45.5)   # a 2-byte unsigned integer, then a 4-byte real
print(len(record), "bytes:", record.hex(" "))
print(struct.unpack("<Hf", record))
print(len("107,45.5"), "characters as text")

Run this in the simulator

Writing and reading a binary file uses the modes "wb" and "rb". The programs on this page keep to text files, so this is shown rather than run:

import struct
with open("robots.dat", "wb") as f:              # b: binary mode
    f.write(struct.pack("<Hf", 107, 45.5))
    f.write(struct.pack("<Hf", 110, 47.5))

with open("robots.dat", "rb") as f:
    f.seek(1 * 6)                                # each record is 6 bytes: jump to record 1
    print(struct.unpack("<Hf", f.read(6)))       # (110, 47.5)

Serial files

In a serial file records are stored one after another in the order they arrive, with no ordering by key. Adding a record is fast: append it to the end. Finding a record means reading from the start until it turns up, a linear search, and if it is not there the whole file must be read.

Serial files suit data that is collected now and processed later: a log of runs, or a transaction file of changes waiting to be applied.

Sequential files

A sequential file holds its records in order of the key field. Searching still reads from the start, but it can stop as soon as it passes the place the key would be. The cost is in changing the file: to insert, delete or change a record, the program copies the whole file to a new one, making the change at the right point as it goes.

That is how a master file (the main, up-to-date file) is updated from a transaction file in a batch. The transactions are sorted into the same key order, then both files are read together in a single pass, a merge: whichever current record has the smaller key is written first. When the keys match, the transaction is applied. The old master is kept as a backup: the grandfather, father, son system keeps the last three generations.

Indexed sequential files

An indexed sequential file is a sequential file with an index. The records are in key order and grouped into blocks, and the index holds the first key of each block and where that block starts. To find a record: search the index for the right block, jump straight to it, then read that block serially. The file can still be read in order from start to end for batch processing, so it serves both kinds of use.

New records that do not fit into their block go into an overflow area, which slows searches down over time, so the file is reorganised now and then.

RECORD = 16
index = []                               # (first key in the block, record number where the block starts)
with open("fixed.txt") as f:
    lines = f.read().splitlines()
for n in range(0, len(lines), 3):        # one index entry for every block of 3 records
    index.append((int(lines[n][:3]), n))
print("index:", index)

def find(key):
    block = index[0][1]
    for first, start in index:           # the last block whose first key is not above the key
        if first <= key:
            block = start
    f = open("fixed.txt")
    f.seek(block * RECORD)               # jump to the block
    for i in range(3):                   # then read it serially
        record = f.read(RECORD).strip()
        if record and int(record[:3]) == key:
            f.close()
            return record
    f.close()
    return None

print(find(110))
print(find(118))
print(find(111))

Run this in the simulator

Direct access files

In a direct access (or random access) file, a hashing function turns the key into the position of the record in the file, exactly as a hash table turns a key into a slot (lesson A3.5). Reading, adding or changing one record takes a single calculation and a single seek, however big the file. The records must be fixed-length, on storage that can jump to any position, such as a disk rather than a tape.

SLOTS = 11
def address(key):
    return key % SLOTS                   # the hashing function gives the record's position in the file

for key in [101, 104, 105, 107, 110, 112]:
    print(key, "is stored at record position", address(key))

Run this in the simulator

101 and 112 both hash to position 2: a collision. As in a hash table, the second record goes to the next free position or into an overflow area, and a search follows the same path. Direct access files are poor at processing every record in key order, because the hashing scatters the keys.

Task: update the master file

master.txt is a sequential master file of robots, in ascending order of id, with the header id,name,best_cm. results.txt is a transaction file with the header id,name,cm, also in ascending id order, holding at most one new run per robot. Both files are shown below. Merge them in one pass, without sorting, into a new file new_master.txt:

• The first line is the header id,name,best_cm.
• Then one line per robot, in ascending id order, in the form id,name,best_cm.
• A robot in master.txt with no result is copied unchanged.
• A robot in both files keeps the larger distance, written exactly as it appears in whichever file it came from (for example 41.0).
• A robot only in results.txt is added with its cm as its best_cm.

Finally print <improved> records improved, <added> added, where improved counts robots whose best distance went up and added counts new robots. The robot does not move.

id,name,best_cm
101,Ada,42.0
104,Bolt,38.5
107,Cog,45.5
110,Dot,40.0

id,name,cm
104,Bolt,41.0
105,Echo,36.0
107,Cog,44.0
110,Dot,47.5

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

with open("master.txt") as f:
    master = f.read().splitlines()
with open("results.txt") as f:
    results = f.read().splitlines()

Challenges

1. Change results.txt so a transaction has an id that is lower than every id in the master file. Does your merge still work?
2. Why must the transaction file be sorted before this kind of update? What would go wrong with a serial transaction file?
3. find in the indexed sequential example reads a whole block for a key that is not there. How could it stop sooner?