Other Access Methods

• 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 record.
  • 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. 9)

  Figure 9: Example of index and relative files.