multiple indexes an advantage of the indexed approach is that multiple indexeseach with different keycan be created for the same file in one index the keys can be last namesin another telephone numbersin another addresses because the indexes are small compared with the filethis doesn' increase the total data storage very much of courseit does present more of challenge when items are deleted from the filebecause entries must be deleted from all the indexesbut we won' get into that here index too large for memory if the index is too large to fit in memoryit must be broken into blocks and stored on the disk for large files it may then be profitable to store the index itself as -tree in the main file the records are stored in any convenient order this arrangement can be very efficient appending records to the end of the main file is fast operationand the index entry for the new record is also quick to insert because the index is tree the result is very fast searching and insertion for large files note that when an index is arranged as -treeeach node contains number of child pointers and one fewer data items the child pointers are the block numbers of other nodes in the index the data items consist of key value and pointer to block in the main file don' confuse these two kinds of block pointers complex search criteria in complex searches the only practical approach may be to read every block in file sequentially suppose in our phone book example we wanted list of all entries in the phone book with first name frankwho lived in springfieldand who had phone number with three " digits in it (these were perhaps clues found scrawled on scrap of paper clutched in the hand of victim of foul play file organized by last names would be no help at all even if there were index files ordered by first names and citiesthere would be no convenient way to find which files contained both frank and springfield in such cases (which are quite common in many kinds of databasesthe fastest approach is probably to read the file sequentiallyblock by blockchecking each record to see if it meets the criteria sorting external files mergesort is the preferred algorithm for sorting external data this is becausemore so than most sorting techniquesdisk accesses tend to occur in adjacent records rather than random parts of the file recall from "recursion,that mergesort works recursively by calling itself to sort smaller and smaller sequences once two of the smallest sequences (one byte each in the internal-memory versionhave been sortedthey are then merged into sorted sequence twice as long larger and larger sequences are mergeduntil eventually the entire file is sorted the approach for external storage is similar howeverthe smallest sequence that can be read from the disk is block of records thusa two-stage process is necessary in the first phasea block is readits records are sorted internallyand the resulting sorted block is written back to disk the next block is similarly sorted and written back to disk this continues until all the blocks are internally sorted