trees and external storage in practice this number is reduced somewhat because we read records at once in the beginning stages of binary searchit doesn' help to have multiple records in memory because the next access will be in distant part of the file howeverwhen we get close to the desired recordthe next record we want may already be in memory because it' part of the same block of this may reduce the number of comparisons by two or so thuswe'll need about disk accesses ( - )which at milliseconds per access requires about millisecondsor / second this is much slower than in-memory accessbut still not too bad insertion unfortunatelythe picture is much worse if we want to insert (or deletean item from sequentially ordered file because the data is orderedboth operations require moving half the records on the averageand therefore about half the blocks moving each block requires two disk accessesone read and one write when the insertion point is foundthe block containing it is read into memory buffer the last record in the block is savedand the appropriate number of records are shifted up to make room for the new onewhich is inserted then the buffer contents are written back to the disk file nextthe second block is read into the buffer its last record is savedall the other records are shifted upand the last record from the previous block is inserted at the beginning of the buffer then the buffer contents are again written back to disk this process continues until all the blocks beyond the insertion point have been rewritten assuming there are , blockswe must read and write (on the average , of themwhich at milliseconds per read and write requires more than minutes to insert single entry this won' be satisfactory if you have thousands of new names to add to the phone book another problem with the sequential ordering is that it works quickly for only one key our file is arranged by last names but suppose you wanted to search for particular phone number you can' use binary search because the data is ordered by name you would need to go through the entire fileblock by blockusing sequential access this search would require reading an average of half the blockswhich would require about minutesvery poor performance for simple search it would be nice to have more efficient way to store disk data -trees how can the records of file be arranged to provide fast searchinsertionand deletion timeswe've seen that trees are good approach to organizing in-memory data will trees work with files