哪种数据结构用于查询缓存？
我正在为我们的 .net Web 服务寻找合适的数据结构进行某种查询缓存，该服务获取 xml 作为查询并返回 xml 作为结果。
流程如下：用户给出一个查询字符串（大小约为 2kb）并获得结果（大小约为 50kb）。最后 n 个查询及其相应结果被缓存，因此我们需要 O(1) 查找查询 -> 结果。如果缓存已满（cache_size=n），则应从缓存中删除最旧的项目。
所以最后我需要一个数据结构，它的工作原理主要类似于队列（在 O(1) 中入队和出队），但也支持像字典这样的项目的 O(1) 查找。
我的第一个想法是使用字典将查询映射到结果。为了跟踪项目的顺序，我将使用一个也包含查询的队列。但问题是我会浪费内存，并且在长查询字符串中进行所有这些查找会变慢。我可以使用另一字典将查询映射到创建的唯一 id 值，以便查询字符串仅包含在一个集合中。
对于这个简单的任务，是否有一个更简单、更有效的解决方案？
Iam looking for a suitable data structure for some kind of query caching for our .net web service that gets xml as query and returns xml as result.
The flow is as follows: The user gives a query string (~2kb in size) and gets a result (~50kb in size). The last n queries with their corresponding results are cached, so we need a O(1) lookup query->result. If the cache is full (cache_size=n) the oldest item should get removed from the cache.
So at the end I need a data structure that works mostly like a queue (enqueue and dequeue in O(1)) but also supports O(1) lookup for an item like a dictionary.
My first idea was to use a dictionary which maps from query to the result. For keeping track of the order of the items I would use a queue which also contains the queries. But the problem is then that I would waste memory and and will be slower to make all these lookups which the long query strings. I could use another dictionary which maps the queries to an created unique id value so the query strings are contained only in one collection.
Isn't there a simpler and more efficient solution for this imho simple task?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
对于简单的缓存
OrderedDictionary类可能会做。对于更大的系统，您可能需要考虑成熟的缓存解决方案，例如 memcached。For a simple cache the
OrderedDictionaryclass might do. For a bigger system you might want to consider a full blown caching solution like memcached.System.Web.Caching 支持随时间变化的 Cache 类基于过期和最大字节限制。但它需要 .NET 4。
如果您想要更大（并且可以访问运行 Linux 的东西），我强烈推荐 redis。
我使用 Redis 实现了类似的查询缓存，这是一个完全无痛的过程。
System.Web.Caching supports a Cache class with time-based expiration and maximum bytes limit. It needs .NET 4 though.
If you go bigger (and have access to something running Linux), I highly recommend redis.
I implemented a similar query cache using redis and it was a completely pain free process.
我建议使用现有的 HttpContext.Cache 属性 - http://msdn.microsoft.com/en-us/library/system.web.httpcontext.cache.aspx
对于更大/分布式系统，请查看 memcached（或 memcacheddotnet - http://sourceforge.net/projects/memcacheddotnet/）
在自己实现方面，建议您封装一个
OrderedDictionary<>(http://www.codeproject.com/KB/recipes/GenericOrderedDictionary.aspx) - 添加项目的顺序被保留，以便您可以访问第一个/最后一个并将其添加到结尾。我相信查找固定大小的字典将是 O(1) 。问题是它将仅限于单个 AppDomain。I would suggest using the existing
HttpContext.Cacheproperty - http://msdn.microsoft.com/en-us/library/system.web.httpcontext.cache.aspxFor a bigger/distributed system, look into memcached (or memcacheddotnet - http://sourceforge.net/projects/memcacheddotnet/)
In terms of implementing it yourself, recommend you encapsulate an
OrderedDictionary<>(http://www.codeproject.com/KB/recipes/GenericOrderedDictionary.aspx) - the order of items added is preserved so you can access the first/last and add to the end. Lookups for a fixed-size dictionary will be O(1) I believe. Thing is it would be limited to a single AppDomain.