about

LRU(Least Recently Used)即最近最久未使用的意思，常用于缓存、散列表场景中。

LRU算法的关键点：

• 最大容量(Max Capacity)、两个API(PUT、GET)
• 保证都是O(1)的时间复杂度
• 上一次访问的元素在队列首位

LRU算法的特点是：

• 查找快、插入快、删除快
• 存储有序

LRU

LRU TWO

MySQL InnoDB 算法

https://blog.csdn.net/baijiu1/article/details/89228209

https://www.jianshu.com/p/d533d8a66795

MySQL是如何对LRU算法进行优化的？又该如何对MySQL进行调优？

https://mp.weixin.qq.com/mp/appmsgalbum?__biz=MzI4Mjg2NjUzNw==&action=getalbum&album_id=1342559017767632897&scene=173&from_msgid=2247484001&from_itemidx=1&count=3#wechat_redirect

更多关于LRU算法，参见：https://www.cnblogs.com/Neeo/articles/13882916.html，

传统的LRU算法

缓存技术中最常见的缓存管理算法是LRU（但MySQL略有区别），它一般是一种链表结构。这里我们主要了解其原理即可。

因为缓存是稀缺资源，当缓存满的时候，再有数据访问的时候会分别触发以下两种操作：

1. 页已经在缓冲池里，那就只做"移至"LRU头部的动作，而没有页被淘汰。
2. 页不在缓冲池里，除了做"放入"LRU头部的动作，还要做"淘汰"LRU尾部页的动作。

传统的LRU算法一般有如下一些问题：

1. 缓存垃圾导致利用率低： 把数据预取加载到缓存区域以后，再也没有访问过这个缓存页，这一部分缓存的利用率就很低，或者说是程序数据局部性很差

**解决思路**：对于这种缓存垃圾，理论上是越早被淘汰出缓存越好，而不是像传统LRU算法一样，放到首部。

2. 缓冲池污染： 当某个sql语句要批量扫描大量数据时，可能导致把缓冲池的所有页都替换出去，导致大量热数据被换出，MySQL性能急剧下降，这种情况叫缓冲池污染。

**解决思路**：对于这种大批量数据占用缓存，不要占用所有的缓存，只占用其中一部分是最好的选择。

---

that's all,see also: [LRU算法](https://www.cnblogs.com/wyq178/p/9976815.html)