我想创建一个以这种方式存储具有到期日期的数据（到期数据的格式可以更改：时间戳、日期对象、时间增量等）的进程。
使用计时器，我希望定期删除已过期的数据。
如果我有一千个有过期日期的元素，我应该使用什么样的数据结构来快速插入、查找和删除？
我的第一个想法是使用 UTC 时间戳和heapqueue。性能非常好，但它仍然是 O(log(n))，所以它会随着项目的数量而增加。
redis / memcache 做了什么来为这些操作提供 O(1) ？
问问题
155 次
2 回答
2
基本上有两种方法应该结合起来 - 命中和未命中 + 清理所有数据（以“离线”方式 - 而不是在请求期间）。
在内存
Memcache 不会在过期时间到期时驱逐密钥，因为这样做是不可能的，同时仍保证 O(1) 操作时间。相反，过期更像是一种说明密钥应该被视为过时的时间。执行 GET 时，Memcache 在返回之前检查密钥的过期时间是否仍然有效。
在 redis 上
Redis 密钥以两种方式过期：被动方式和主动方式。仅当某些客户端尝试访问密钥并且发现密钥超时时，密钥才会主动过期。当然这还不够，因为有过期的密钥将永远不会被再次访问。无论如何，这些密钥都应该过期，因此 Redis 会定期在设置过期的密钥中随机测试几个密钥。所有已经过期的键都会从键空间中删除。
旁注 - 概率方法万岁
以下是关于memcache和redis的参考资料
于 2013-02-28T09:14:41.867 回答
0
您是否按顺序插入具有到期日期的数据？如果是这样，堆队列将比线性队列慢，在线性队列中插入 O(1)，弹出 O(1)。
于 2013-03-01T02:41:09.207 回答