Indexed sequential

Inded sequential files are sequential files. That means they will search, append and insert the exact same way. They will be ordered by the key field of the record. The biggest difference is that they will also have a index added to the start of the file (held in the meta-data).

This index will be a key/address pair. So each records key will be followed by the start address of where it can be found in the file. Consider the following data with the following record structure -

  1. zed angry, 12
  2. fred flintstone, 22
  3. P free, 87
  4. bob smith, 30
Name Type Size
Surname Text 30
Name Text 20
age INT 4

Surname is the key field. So our index will look like this -

Key Address
angry 0
flintstone 54
free 108
smith 162

The address is the starting position of the record. As P free is the third record we can find him at position 108. This is calcualted by -

Address = (record number - 1)* record size
Address = (3 -1) * 54
Address = 2 * 54
Address = 108

Why bother with an index? Well it will speed up access to the data during a serial search. As we do not have to read the whole file to find out where a record is found we reduce the amount of disk access we perform. We can consult the index then skip out a big chunk of the file. This reduces disk access and thus increases effeciency.

The index may link to a group of records rather than a single record. So for example we could link to all people starting with the letter A. If this is the case then we would have to perform a serial search after the initial index lookup which would slow things down but we will only need to do it for part of the file.

We can get really fancy and have a fixed index which will always have all letters. That way we could skip out the serial search through the index! We could also do a binary search on the index if we store the size of the index as the first part of the file.

These ideas are beyond the scope of the course but hopefully it will start giving you an idea of how combining knowledge can increase efficency. Embedded applications (like on your Iphone) will use these ideas to help squeeze as much performance out of the device as possible.