我想要一个允许查询最近X分钟内有多少个项目的数据结构。一个项目可能只是一个简单的标识符或者一个更复杂的数据结构，优选地，该项目的时间戳记将在该项目中，而不是存储在外部(作为散列或者类似内容，不希望多个项目具有相同时间戳记)。

到目前为止，看来使用LINQ可以轻松过滤时间戳大于给定时间的项目并汇总计数。尽管我很犹豫是否尝试将.NET 3.5特定的东西用于我的生产环境。对于类似的数据结构还有其他建议吗？

我感兴趣的另一部分是老化旧数据，如果我只想查询少于6小时前的项目计数，那么我希望从我的数据结构中删除比该数据还旧的内容是一个长期运行的程序。

解决方案

回答

我认为重要的考虑因素将是查询与添加/删除的频率。如果我们要进行频繁查询(特别是如果馆藏很大)，则可以使用B树：

http://en.wikipedia.org/wiki/B-tree

我们可能需要一些线程来定期清理该树或者使其成为搜索的一部分(再次取决于使用情况)。基本上，我们将进行树搜索以找到" x分钟前"的地点，然后计算节点上具有新时间的子节点数。如果我们使节点下的子代数保持最新，则此总和可以很快完成。

回答

一个简单的链表可用于此目的。

基本上，我们将新项目添加到末尾，并从一开始就删除太旧的项目，这是一种廉价的数据结构。

示例代码：

list.push_end(new_data)
while list.head.age >= age_limit:
    list.pop_head()

如果该列表足够繁忙，以至于一次不能切掉比一个更大的片段，那么我同意dmo，使用树状结构或者类似的方法可以在更高层次上进行修剪。

回答

具有滑动到期时间的缓存将完成此任务。

将物品塞进去，然后缓存处理老化....

http://www.sharedcache.com/cms/