最佳的储存的数据结构，用于快速查找和持久性

Question

方案

我有以下方法：

public void AddItemSecurity(int itemId, int[] userIds)
public int[] GetValidItemIds(int userId)

最初我想存在的形式：

itemId -> userId, userId, userId

和

userId -> itemId, itemId, itemId

AddItemSecurity 根据我得到的数据从一个第三方API， GetValidItemIds 是我想用它在运行时间。

有潜在的用户2000年和10百万的项目。项目id的形式：2007123456,2010001234(10个数字在第四个代表年)。

AddItemSecurity 不必执行速度飞快，但是 GetValidIds 需要亚秒.此外，如果有一个更新现有的 itemId 我需要消除这itemId为用户不再在清单。

我在想我怎么应该存在这一最佳方式。最好在盘(与缓存)，但是我希望代码维护和清洁。

如果该项目id已经开始在0,我以为关于创建一个字节列的长度 MaxItemId / 8 对于每个用户，并设置一个true/false位，如果该项目是本或没有。这将限制的阵列的长度略超过1mb每个用户，并得到快速查询以及一个简单的方法来更新该名单每户。通过坚持这样 存储器映的文件 与。净4框架，我认为我会得到体面缓存，以及(如果该机有足够的内)没有执行缓存的逻辑自己。分析的id，剥离出来的一年中，和储存的一个阵列，每年可能是一个解决方案。

ItemId->Id[]列表中可以列化的直接盘和读写有一个正常的 FileStream 为了保持清单的和比较时有变化。

每次一个新的用户加入所有的列出了必须更新，但是这个可以做每晚。

的问题

我应该继续尝试这种办法，或是有其他的路径，它应该探讨？我想到SQL服务器不会执行的速度不够快，并且它将得到开销的(至少是如果它的托管不同的服务器上的)，但是我的假设可能是错误的。任何思想或见解，对此事表示赞赏。我想试图解决它没有加入过多的硬件:)

[更新2010-03-31]

我现在已经过测试，与SQL服务器2008年在下述条件。

• 两列的表格(userid,itemid)两者都是Int
• 聚集指数上的两列
• 加入-800,000名项目180的用户-总额为144亿行
• 分配4g ram SQL服务器
• 双核2.66ghz的笔记本电脑
• SSD盘
• 使用SqlDataReader读取所有itemid的成列表
• 循环的所有用户

如果我运行一个线程平均数在0.2秒钟。当我增加第二线去了0.4秒钟，这仍然是确定。从那结果是减少。添加的第三个线程带来了很多的查询最多2seonds.阐述线，达到4秒钟，第五尖峰的一些查询最多50秒。

CPU是屋顶虽然这是怎么回事，甚至在一个线程。我的测试应用程序需要一些由于迅速的循环，并sql的其余部分。

这导致我的结论是，它不会的规模非常好。至少不在我的测试硬件。有没有方法来优化数据库，说存储一系列int的每个用户，而不是一个记录每项目。但是这使得它难以消除的项目。

[更新2010-03-31#2]

我做了一个快速测试相同数据，把它作为位在存储器映的文件。它执行多更好。六线产量访问次数之间的0.02s和0.06s.纯粹存的约束。映射的文件进行映射的一个进程，访问的六个其他人同时进行。而作为sql基花了4gb，磁盘上的文件了23mb.

Answer 1

经过大量的测试结果我使用的存储器映的文件，这标志着他们的疏位(NTFS)，使用代码 NTFS疏文件C#.

维基百科上具有解释什么 疏文件 是。

福利的使用稀疏的文件，我不必关心的范围是什么我的id。如果我只写id之间2006000000和2010999999，该文件将仅分配62万5000字节偏250,750,000在文件。所有空间来抵消未分配的文件系统。每个id被储存作为一种设定点的文件。种类的处理作为一位阵列。如果id序列突然的变化，那么它将在另一个部分的文件。

为了检索其id的设置，我可以执行一个操作系统通话获得的部分分配的稀疏的文件，然后我检查一下每一位在那些序列。还检查，如果一个特定的id设定是非常快。如果它落之外所分配的区块，那么它就是不存在的，如果它落在，它只是一个字节的读位掩检查，看看是否正确的位置。

所以对于特定的情况下，你有很多的身份证，你要检查与尽可能多的速度，这是最佳办法，我已经找到为止。

和良好的部分是，所存储器映的文件可以共享与Java以及(这竟然是需要的东西).Java也支持存储器映文件，在Windows，并执行读写的逻辑是相当微不足道的。

Answer 2

我真的觉得你应该试试一个很好的数据库之前，你做决定。像这样的东西将是一个挑战，保持长期运行。你的用户基础其实是相当小的。SQL服务器应当能够处理你需要什么没有任何问题。

Answer 3

2000用户是不是太糟糕了，但是与10mil相关的项目，你真的应该考虑把这个变成一个数据库。DBs做的所有储存、持久性、索引编制、缓存等。你需要和他们进行得非常好。

它们还能更好地扩展到未来。如果你突然需要处理两百万的用户和数十亿的设置具有一个良好的数据库的地方将扩展非的问题。