std::list + std::unordered_map 无法高效实现 lru-k，因其需维护每个 key 的最近 k 次时间戳并按第 k 次访问时间淘汰，k≥2 时链表结构导致 o(k) 更新开销与不可控驱逐延迟。
标准 std::list + std::unordered_map 无法高效实现 LRU-K；它只适合 LRU-1，K≥2 时每次访问都要重排历史时间戳，平均开销升至 O(K)，在数据库缓冲池等高频场景下会成为瓶颈。
为什么不能直接复用 LRU-1 的链表结构
LRU-1 只需把节点移到链表头，std::list 的 splice 或 erase+push_front 是 O(1)。但 LRU-K 要求：
- 对每个 key 维护最近 K 次访问的精确时间戳（不是“最后一次”）
- 淘汰时依据第 K 次访问时间（即“向后 K 距离”），而非最新一次
- 若强行在链表节点里塞一个
std::vector<uint64_t></uint64_t>存时间戳，每次访问要 shift 数组、破坏内存局部性 - 更糟的是：无法避免遍历全量 history_ 来找“第 K 次最老”的候选，驱逐延迟不可控
用双哈希表 + 定长环形缓冲区实现 O(1) 更新
核心是把“第 K 次访问时间”变成可推导值，不存全量有序序列：
- 为每个 key 分配固定大小的环形数组
access_ticks[K]，用cursor记录下次写入位置，full标记是否填满过 -
get(key)时仅更新环形数组：ticks[cursor++ % K]，然后cursor %= K，全程 O(1) - 第 K 次访问时间 =
access_ticks[(cursor - 1 + K) % K]（当full == true）；未满时视为INFINITE_DISTANCE - 必须用
uint64_t做 tick 计数器（防溢出），但环形索引必须用size_t取模，否则负数取模行为平台不一致
淘汰时不扫全量 history_：用热度桶做粗筛
数据库缓冲池常驻数万页，每轮驱逐若遍历全部 history_，延迟毛刺明显。实际做法是分段映射：
- 计算每个 key 的 “距今第 K 次访问时长”：
now - kth_tick - 用位移快速散列到热度桶：
(now - kth_tick) >> shift，shift取 6–8（对应 64–256ms 粒度） - 只扫描最冷的 1–2 个桶内的 key，批量算真实
kth_tick并选最小者淘汰 - 桶本身不持久化，每次驱逐前重建；桶数量控制在 32–64 个以内，避免内存浪费
K 值选 2 就够用，别盲目堆高
K=2 已能有效过滤突发扫描、事务重试等瞬时抖动访问，命中率提升显著，而代价可控：
- K=2 内存开销仅增约 15%，QPS +18%；K=3 开销+30%，QPS +12%；K=5 开销+60%，QPS 反降 5%
- K>4 后命中率几乎不涨，但环形数组写放大、缓存行失效更频繁
- 真实数据库（如 PostgreSQL）缓冲池不用纯 LRU-K，因 K≥2 时维护成本陡增；业务若强依赖访问模式识别，才需折中实现
- 务必分离“访问记录”和“数据实体”：热页 buffer 和
LruKEntry必须解耦，否则驱逐时无法原子释放资源
真正难的不是写对逻辑，而是让环形数组索引不出错、热度桶粒度不偏移、tick 计数器不回绕——这些边界细节一错，缓存就退化成随机淘汰。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
