LRU算法概念介绍
LRU（Least Recently Used，最近最少使用）算法是一种用于缓存管理的常见算法。它的核心思想是：当需要淘汰（替换）一个数据时，选择最长时间未被访问的数据进行淘汰，即选择最近最少使用的数据。
以下是LRU算法的概念介绍和基本工作原理：
- 缓存管理： LRU算法通常用于管理缓存中的数据。缓存是一个用于临时存储数据的高速存储区域，旨在提高数据的访问速度。缓存大小有限，因此需要一种方法来确定哪些数据应该保留在缓存中，哪些应该被淘汰。
- 访问顺序跟踪： LRU算法维护一个数据结构，通常是一个双向链表或数组，用于跟踪数据的访问顺序。每当数据被访问时，它就被移到数据结构的前端，表示它是最近使用的数据。
- 淘汰策略： 当需要淘汰一个数据以腾出空间给新的数据时，LRU算法选择数据结构末尾的数据进行淘汰，因为它们是最久未被使用的数据。这样可以确保缓存中始终保留最近使用的数据。
- 例子： 假设有一个缓存，可以存储3个数据（A、B、C）。当访问数据A时，它会被移到缓存的最前面。接下来访问数据B，它也会被移到最前面。然后访问数据C，同样移到最前面。如果现在需要缓存一个新的数据D，但缓存已满，LRU算法会淘汰末尾的数据A，然后将D放入最前面。
- 时间复杂度： LRU算法的时间复杂度通常是O(1)，因为它只需要对数据结构的头尾进行操作，而不需要遍历整个数据集。
需要注意的是，虽然LRU算法是一种简单而有效的缓存管理算法，但它也有一些缺点。例如，它不一定能够很好地适应某些访问模式，特别是在存在突发的热点数据访问时。在某些情况下，需要考虑其他缓存淘汰算法，如LFU（Least Frequently Used，最不经常使用）或ARC（Adaptive Replacement Cache，自适应替换缓存）。选择缓存算法应根据具体的应用场景和性能需求来决定。
MySQL为什么改进LRU算法？
- 如上图，按照传统的LRU算法的话，真正的热点数据将会被淘汰掉。
改进后的LRU算法
- MySQL改进之后的LRU算法
- 将链表分为了 new 和 old 两个部分，数据插入的时候从中间分隔点 midpoint 位置插入
- 这样的话，如果数据很快被访问，数据将会向 Young 区域的头部移动，反之向 Old 区域的尾部移动
- 这样避免了 “真正的热数据” 被淘汰