recall from the last that disk file is divided into blocks containing many recordsand that the time to access block is much larger than any internal processing on data in main memory for these reasons the overriding consideration in devising an external storage strategy is minimizing the number of block accesses on the other handexternal storage is not expensive per byteso it may be acceptable to use large amounts of itmore than is strictly required to hold the dataif by so doing we can speed up access time this is possible using hash tables table of file pointers the central feature in external hashing is hash table containing block numberswhich refer to blocks in external storage the hash table is sometimes called an index (in the sense of book' indexit can be stored in main memoryorif it is too largestored externally on diskwith only part of it being read into main memory at time even if it fits entirely in main memorya copy will probably be maintained on the diskand read into memory when the file is opened non-full blocks let' reuse the example from the last in which the block size is , bytesand record is bytes thus block can hold records every entry in the hash table points to one of these blocks let' say there are blocks in particular file the index (hash tablein main memory holds pointers to the file blockswhich start at at the beginning of the file and run up to in external hashing it' important that blocks don' become full thus we might store an average of records per block some blocks would have more recordsand some fewer there would be about records in the file this arrangement is shown in figure figure external hashing all records with keys that hash to the same value are located in the same block to find record with particular keythe search algorithm hashes the keyuses the hash value as an index to the hash tablegets the block number at that indexand reads the block this is an efficient process because only one block access is necessary to locate given item the downside is that considerable disk space is wasted because the blocks areby