LRU and MRU algorithm for data inventory taking buffer
Cache Hit and Cache Miss
When the user issues a request for query data to the database, the database will first find the data in the buffer. If the data to be accessed is just in the buffer (we call Cache Hit), This data is read in the buffer.
Vioence, if there is no user to query the data to be queried, this situation is called Cache Miss, in which case the database will first read the user's data from the disk into the buffer, the user is again The buffer reads the data.
Obviously, from the feeling of cache hits, the speed is faster than Cache Miss.
2. LRU (Recent User Algorithm) And MRU (Recently User Algorithm)
The basic concept of the so-called LRU (Least Recently Used) algorithm is that when the remaining available space of the memory is not enough, the buffer is as possible to preserve the most commonly used data, in other words, it is preferred to use it. Data "and release its space. The reason why" less commonly used data "is used to use quotation marks because the so-called less frequently used standard is human, unstrusted. So-called MOSTLY USED The meaning of the algorithm is just the opposite of the LRU algorithm.
Below we look at the use of LRU and MRU in Oracle 9i Cache to see the roles and differences in both buffer working mechanisms:
In Oracle 9i, there is a concept of LRU List: We can imagine LRU List to be a series of buffer collections, both ends are LRU terminals and MRU terminals, when the database reads data from the disk, the system must First determine that Free buffers in the buffer, this time Oracle 9i will scan LRU LIST, the basic principles of scan are:
1. End from the LRU to the MRU terminal;
2. When scanning to free buffer or the number of scanned buffers exceed the critical value, the scanning action is stopped;
If the free buffer is found smoothly in the LRU List, Oracle 9i writes the data read from the disk to free buffer, add free buffer to the LRU LIST MRU side.
Then if the scanning process does not find free buffer in the lru list? Of course, it will be a new space from the LRU side of the LRU List. This can make a new space.
The following figure is an example:
User query data A. Initial Time, there is no data A in the LRU List, so Oracle 9i to disk read A, then put it into the MRU side of the LRU List, read data A from the LRU List A, the same for B , When the LRU List is full, if the user queries N, N is not in the LRU LIST and there is no free buffer in the LRU List, at this time, Oracle 9i will begin to eliminate A from the LRU terminal to store N .
figure 1
Let's take another situation:
After State 3, the user's continuous query A-this will cause a buffer that is approached by the MRU side, and the result will be shown in Figure 2, you will find State M 'and Figure 1 The data stored in the State m buffer is exactly the same but the storage location is different. At this time, the lru list is full. If the LRU List is eliminated when it is placed, because A's query is higher than B, so Lru List let A staying in the buffer for a longer time and eliminating the "less common" B.
figure 2
