existing pagesfor exampleusing special pointers or "locators if is implemented with sorted sequence based on linked listthen the overhead for each page request and page replacement is ( when we insert page in or update its keythe page is assigned the highest key in and is placed at the end of the listwhich can also be done in ( time even though the lru strategy has constanttime overheadusing the implementation abovethe constant factors involvedin terms of the additional time overhead and the extra space for the priority queue qmake this policy less attractive from practical point of view since these different page replacement policies have different trade offs between implementation difficulty and the degree to which they seem to take advantage of localitiesit is natural for us to ask for some kind of comparative analysis of these methods to see which oneif anyis the best from worst-case point of viewthe fifo and lru strategies have fairly unattractive competitive behavior for examplesuppose we have cache containing pagesand consider the fifo and lru methods for performing page replacement for program that has loop that repeatedly requests pages in cyclic order both the fifo and lru policies perform badly on such sequence of page requestsbecause they perform page replacement on every page request thusfrom worst-case point of viewthese policies are almost the worst we can imagine--they require page replacement on every page request this worst-case analysis is little too pessimistichoweverfor it focuses on each protocol' behavior for one bad sequence of page requests an ideal analysis would be to compare these methods over all possible page-request sequences of coursethis is impossible to do exhaustivelybut there have been great number of experimental simulations done on page-request sequences derived from real programs based on these experimental comparisonsthe lru strategy has been shown to be usually superior to the fifo strategywhich is usually better than the random strategy external searching and -trees consider the problem of implementing dictionary for large collection of items that do not fit in main memory since one of the main uses of large dictionaries is in databaseswe refer to the secondary-memory blocks as disk blocks likewisewe refer to the transfer of block between secondary memory and primary memory as disk transfer recalling the great time difference that exists between main memory accesses and disk accessesthe main goal of maintaining dictionary in external memory is to minimize the number of disk transfers needed to perform query or update in factthe difference in speed between disk and internal memory is so great that we should be willing to perform considerable number of internalmemory accesses if they allow us to avoid few disk transfers let usthereforeanalyze the performance of dictionary implementations by counting the number of disk transfers