- Other access methods can be built on top of a direct-access method.
- These methods generally involve the construction of an index for the file.
- To find a record in the file, we first search the index to learn exactly which block contains the desired record
- and then use the pointer to access the file directly and to find the desired record.
- This structure allows us to search a large file doing little I/O. But, with large files, the index file itself may become too large to be kept in memory.
- One solution is to create an index for the index file.
- The primary index file would contain pointers to secondary index files, which would point to the actual data items.
- For example, IBM's indexed sequential-access method (ISAM) uses a small master index that points to disk blocks of a secondary index. The file is kept sorted on a defined key.
- To find a particular item, we first make a binary search of the master index, which provides the block number of the secondary index.
- The secondary index blocks point to the actual file blocks. This block is read in, and again a binary search is used to find the block containing the desired
- Finally, this block is searched sequentially.
- In this way any record can be located from its key by at most two direct-access reads (see Fig. 10.9)
Example of index and relative files.