Home >Database >Mysql Tutorial >LRU在MySQL缓存池的实现_MySQL

LRU在MySQL缓存池的实现_MySQL

WBOY
WBOYOriginal
2016-06-01 13:17:091166browse

MySQL的InnoDB引擎设置有索引及数据缓存池,其中用到的LRU算法来维持缓存的命中率

这里用到了顺序表list来作为缓冲池,每个数据节点称为block

该算法采用“中点插入法”:当插入一个新block时,移除表尾最近最少使用的block,在中点插入新block。

这个中点将链表分为两部分:

1.靠近表头的一部分,为young区,这里的block是最近使用的节点

2.靠近表尾的一部分,为old区,这里的block是最近少使用的

该算法通过链表中的block的使用热度来维持各block的位置,其中old区的block为链表满的时候移除的候选区

具体算法如下:

1.链表的3/8被设置为old区

2.中点不是链表的中间点,而是old区的表头节点,即old区与young区的相邻的那个节点

3.当读取的数据不在缓冲池里的时候,读取到的block需要插入到链表中,插入点为中点,但是插入的新节点为old区的节点,如果此时old区满了得话,移除表尾的block(LRU节点)

4.当读取old区的block时,该节点将变成“young”节点:此节点移动到young区的表头(young区的头部那里)

5.在数据库操作中,被访问的节点将移除到young的表头,这样一来,在young区中的未被访问的节点将逐渐往表尾移动,当移动过中点,将变为old区的节点。而old区的节点若被访问到将变为young节点移动到表头,而old区中的为被访问的节点依旧往表尾移动,当表满时,表尾那个block将会被淘汰掉

这里不涉及到具体代码实现,只是简单讲了下原理,待实现出来后再贴上来

 

转载请注明出处:http://www.cnblogs.com/iamsupercp/p/3682659.html 谢谢合作

 

 

Statement:
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn