Java Reference
In-Depth Information
This is potentially a useful observation that typical “real-life” distributions of
record accesses, if the records were ordered by frequency, would require that we
visit on average only 10-15% of the list when doing sequential search. This means
that if we had an application that used sequential search, and we wanted to make it
go a bit faster (by a constant amount), we could do so without a major rewrite to
the system to implement something like a search tree. But that is only true if there
is an easy way to (at least approximately) order the records by frequency.
In most applications, we have no means of knowing in advance the frequencies
of access for the data records. To complicate matters further, certain records might
be accessed frequently for a brief period of time, and then rarely thereafter. Thus,
the probability of access for records might change over time (in most database
systems, this is to be expected). Self-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 a heuristic for deciding
how to to reorder the list. These heuristics are similar to the rules for managing
buffer pools (see Section 8.3). In fact, a buffer pool is a form of self-organizing
list. Ordering the buffer pool by expected frequency of access is a good strategy,
because 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
access, the buffer at the end of the list will be the one most appropriate for reuse
when a new page of information must be read. Below are three traditional heuristics
for managing self-organizing lists:
1. The most obvious way to keep a list ordered by frequency would be to store
a count of accesses to each record and always maintain records in this or-
der. This method will be referred to as count. Count is similar to the least
frequently used buffer replacement strategy. Whenever a record is accessed,
it might move toward the front of the list if its number of accesses becomes
greater than a record preceding it. Thus, count will store the records in the
order of frequency that has actually occurred so far. Besides requiring space
for the access counts, count does not react well to changing frequency of
access over time. Once a record has been accessed a large number of times
under the frequency count system, it will remain near the front of the list
regardless of further access history.
2. Bring a record to the front of the list when it is found, pushing 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 a linked list. When records are
stored in an array, bringing a record forward from near the end of the array
will result in a large number of records (slightly) changing position. Move-
to-front's cost is bounded in the sense that it requires at most twice the num-
