7.1.4
Partially-indexed file organization

Bigger blocks would be used in practice

Record 4 is unnocupied or has been deleted.

Block 2 is full - there are a number of solutions to this problem, eg:

The index can be held in an array or a linked list during program execution.

If it is a large index held in an array, it can be binary searched

In this type of file there is a main file which is sequential (ordered on a key field).  There is another file which contains the index, this gives the first entry in each block of records.  

In the above example, the block size is 5 (not very realistic but will serve for illustration).  To find a name like brambell for example, we first search the index to find which block it will be in.  Since brambell comes after block 0 but before block 3 ( callendar ) we know the target record (if it exists) is in block 2, this block is then searched to locate the required  record.  If the block is searched and the record is not found in the block - it is not in the file.

To search for brambell sequentially in the main file would take 9 comparisons, to find it using the index it takes only 4. 

Partial indexing is especially useful with very large files, say a file of 250,000 entries with an index of 1000 entries, each block containing 250 entries.  To find a name in the middle of this file would take 125,000 comparisons using sequential search.  Using the index, searching half the index takes 500 comparisons, then searching half the block 125 comparisons for a total of 625 - a considerable saving in time. 

If the files become very large (millions of entries, say) multi-level indexes can be used, the main index can itself be indexed.

Java examples - ok, ok, give us a bit more time...

related: [ Topic 7 home | previous: basics | next: fully-indexed files ]

Files

Questions or problems related to this web site should be addressed to Richard Jones who asserts his right to be identified as the author and owner of these materials - unless otherwise indicated. Please feel free to use the material presented here and to create links to it for non-commercial purposes; an acknowledgement of the source is required by the Creative Commons licence. Use of materials from this site is conditional upon your having read the additional terms of use on the about page and the Creative Commons Licence. View privacy policy.