chap searching when frequency distribution follows the / rulethe average search looks at about one tenth of the records in table ordered by frequency in most applicationswe have no means of knowing in advance the frequencies of access for the data records to complicate matters furthercertain records might be accessed frequently for brief period of timeand then rarely thereafter thusthe probability of access for records might change over time (in most database systemsthis is to be expectedself-organizing lists seek to solve both of these problems self-organizing lists modify the order of records within the list based on the actual pattern of record access self-organizing lists use heuristic for deciding how to to reorder the list these heuristics are similar to the rules for managing buffer pools (see section in facta buffer pool is form of self-organizing list ordering the buffer pool by expected frequency of access is good strategybecause typically we must search the contents of the buffers to determine if the desired information is already in main memory when ordered by frequency of accessthe buffer at the end of the list will be the one most appropriate for reuse when new page of information must be read below are three traditional heuristics for managing self-organizing lists the most obvious way to keep list ordered by frequency would be to store count of accesses to each record and always maintain records in this order this method will be referred to as count count is similar to the least frequently used buffer replacement strategy whenever record is accessedit might move toward the front of the list if its number of accesses becomes greater than record preceding it thuscount will store the records in the order of frequency that has actually occurred so far besides requiring space for the access countscount does not react well to changing frequency of access over time once record has been accessed large number of times under the frequency count systemit will remain near the front of the list regardless of further access history bring record to the front of the list when it is foundpushing all the other records back one position this is analogous to the least recently used buffer replacement strategy and is called move-to-front this heuristic is easy to implement if the records are stored using linked list when records are stored in an arraybringing record forward from near the end of the array will result in large number of records changing position move-to-front' cost is bounded in the sense that it requires at most twice the number of accesses required by the optimal static ordering for records when at least