Section 6.3
6 Files
6.3 Indexed Sequential Files
Records are stored in sequence with an index.
The index enables individual records to be located directly.
The index is created and stored with the file when it is first created.
Indexed sequential files require direct access storage (DAS) media.
6.3.1 Disk Packs And Hard Disks
The way in which the index works depends on how the data is written onto the
disk.
Each platter has two surfaces although the outer surfaces are not used.
Each surface is split up into a number of concentric circular tracks.
All the tracks of the same diameter together on different surfaces form a
cyclinder.
Tracks are split up into sectors.
6.3.2 Multi-Level Indexing
Indexed sequential files have more than one level of index.
A common method of indexing is:
CYCLINDER - SURFACE - SECTOR
The cyclinder (primary index) is read first. From this we can establish which
cyclider holds the data we want and the read/write heads are moved to that
cyclinder. This is known as seeking.
At the right cyclinder the surface index (the secondary index) is read. We can
now switch on the right head for the right surface. This is known as
switching.
The read/write heads are now on the right track. We now read the sector index
(the tertiary index). This gives the sector at which the record should be found.
The sector is now searched serially. If the record is not found then either:
- The record does not exist.
- The record was placed in an overflow area in the disk pack.
Advantages Of Multi-Level Indexing
- Files can be processed randomly which is usually faster than serial
processing.
- We have the flexibility to ignore the index and search the file
sequentially.
Disadvantages Of Multi-Level Indexing
- The index takes time to create, access and also consumes space.
6.3.3 Overflow
Each sector accommodates a range of key values.
The sector which should accommodate a record is called it's home sector.
If a sector is full, there are two circumstances when a record will not fit
into its home sector.
- A new record is being inserted.
- An existing variable length record becomes longer during updating.
In either case it is stored in the overflow area on the disk pack.
If this happens a tag is left in the home sector which gives the key field of
the record and the address of the sector in the overflow area where the record
is to be found.
6.3.4 Blocks
The smallest amount of data that can be transferred between main memory and
backing store is a block. A block of data occupies one sector.
The number of records stored in one block is called the blocking factor of a
file. The choice of deciding how large to make the blocking factor is called the
blocking strategy.
When deciding on the blocking strategy it should be remembered that:
- File access should be as quick as possible.
- Addition and deletion of records should be as quick as possible.
- Storage space should be used efficiently.
Two common ratios are:
Block Packing Density
|
Disk space allocated to records
|
:
|
Total space avaliable in a block
|
Cyclinder Packing Density
|
Tracks set aside for records in the cyclinder
|
:
|
Total number of tracks in the cyclinder
|
6.3.5 File Reorganisation
if a large number of records have had to be stored in overflow areas becuase
their home sectors were full then file processing would be slow.
The solution is to reorganise the file.
This involves:
- reading records in a logical sequence.
- writing them out in physical sequence to another file.
More free space is left in the home sector for additional records. The indexes
are also recreated.
