File system
The first requirement is that each record have a specific key field on which to
match when searching. You then create an index file which holds the keys
for each record in the data file, together with the position in the data file to
which you can seek to retrieve a record. If the index file is maintained in
sorted order, searching for a record may be optimized. i.e. - If reading the
indexes sequentially, you can tell if a record doesn't exist as soon as an
index of greater value is encountered without getting a match. Also, a sorted
index can be searched using a binary search method to reduce key comparisons
to a minimum. If the index file is not maintained in sorted order on disc, it can
be read entirely into memory and sorted there before using.
Beyond a simple index, you can have a linked index which includes pointers
to the next and previous index items a la a doubly linked list. The data file itself
may also have such forward/backward pointers in each record. Such a structure
obviates the need for sorting the data, as it may be retrieved sequentially
even though the records are written randomly.
Consider and investigate ISAM - Indexed Sequential Access Method..
CodeMillenium
|
