trees and external storage time to read the actual record from the fileonce its block number has been found in the index howeverthis is only one disk access of (say milliseconds insertion to insert new item in an indexed filetwo steps are necessary we first insert the item' full record into the main filethen we insert an entryconsisting of the key and the block number where the new record is storedinto the index because the index is in sequential orderto insert new itemwe need to move half the index entrieson the average figuring microseconds to move byte in memorywe have , times times or about seconds to insert new entry this compares with minutes for the unindexed sequential file (note that we don' need to move any records in the main filewe simply append the new record at the end of the file of courseyou can use more sophisticated approach to storing the index in memory you could store it as binary treetreeor red-black treefor example any of these would significantly reduce insertion and deletion times in any case the index-in-memory approach is much faster than the sequential-file approach in some cases it will also be faster than -tree the only actual disk accesses necessary for an insertion into an indexed file involve the new record itself usuallythe last block in the file is read into memorythe new record is appendedand the block is written back out this process involves only two file accesses 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 anothertelephone numbersin anotheraddresses 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 file because 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 storing the index itself as -tree may then be profitable 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 inserting the index entry for the new record is also quick because the index is tree the result is very fast searching and insertion for large files