数据结构的最佳存储,以实现快速查找和持久性

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个用户和1000万个项目.项目ID在表格上:2007123456,2010001234(前10位代表年份的10位数字).

AddItemSecurity不必执行超快,但GetValidIds需要亚秒.此外,如果现有更新,itemId我需要为列表中不再包含的用户删除该itemId.

我正在考虑如何以最佳方式存储它.最好在磁盘上(带缓存),但我希望代码可维护和清洁.

如果项目id从0开始,我考虑MaxItemId / 8为每个用户创建一个字节数组长度,如果项目存在与否则设置一个真/假位.这将限制每个用户的阵列长度超过1mb,并提供快速查找以及更新每个用户列表的简便方法.通过使用.Net 4框架将其作为内存映射文件持久化,我认为我也可以获得不错的缓存(如果机器有足够的RAM),而不是自己实现缓存逻辑.解析id,剥离年份,每年存储一个阵列可能是一个解决方案.

ItemId - > UserId []列表可以直接序列化到磁盘并使用法线FileStream进行读/写,以便持久保存列表并在发生更改时进行区分.

每次添加新用户时,所有列表也必须更新,但这可以在每晚完成.

题

我应该继续尝试这种方法,还是应该探索其他途径？我认为SQL服务器执行速度不够快,而且会产生开销(至少如果它托管在不同的服务器上),但我的假设可能是错误的.任何关于此事的想法或见解都表示赞赏.我想尝试解决它而不添加太多硬件:)

[更新2010-03-31]

我现在已经在以下条件下使用SQL Server 2008进行了测试.

• 具有两列(userid,itemid)的表都是Int
• 两列上的聚簇索引
• 为180个用户添加了约800,000个项目 - 总计1.44亿行
• 为SQL服务器分配4gb ram
• 双核2.66ghz笔记本电脑
• SSD磁盘
• 使用SqlDataReader将所有itemid读入List
• 遍历所有用户

如果我运行一个线程,它的平均值为0.2秒.当我添加第二个线程时,它会上升到0.4秒,这仍然可以.从那里开始,结果正在减少.添加第三个线程会带来很多查询,最多可达2个.第四个线程,最多4秒,第五个线程查询一些查询,最多50秒.

即使在一个线程上,CPU也在进行屋顶处理.我的测试应用程序需要一些由于快速循环,并sql其余.

这使我得出结论,它不会很好地扩展.至少不在我测试的硬件上.有没有办法优化数据库,比如存储每个用户的int数组而不是每个项目一个记录.但这使得删除项目变得更加困难.

[更新2010-03-31#2]

我使用相同的数据进行了快速测试,将其作为内存映射文件中的位.它表现得更好.六个线程产生的访问时间介于0.02s和0.06s之间.纯粹的记忆力.映射文件由一个进程映射,并由六个其他进程同时访问.并且由于sql base占用了4GB,磁盘上的文件占用了23mb.

Answer 1

经过多次测试后，我最终使用了内存映射文件，用稀疏位 (NTFS) 标记它们，并使用NTFS 稀疏文件中的代码和 C#。

维基百科对什么是稀疏文件有解释。

使用稀疏文件的好处是我不必关心我的 id 的范围。如果我只在 2006000000 和 2010999999 之间写入 id，则该文件只会从文件中的偏移量 250,750,000 分配 625,000 字节。文件系统中直到该偏移量的所有空间均未分配。每个 id 都作为一组位存储在文件中。有点被视为位数组。如果id序列突然改变，那么它将在文件的另一部分分配。

为了检索设置的 id，我可以执行操作系统调用来获取稀疏文件的已分配部分，然后检查这些序列中的每一位。检查是否设置了特定的 id 也非常快。如果它落在分配的块之外，则它不在那里，如果它落在分配的块内，则只需读取一个字节并进行位掩码检查以查看是否设置了正确的位。

因此，对于您有许多 id 并希望以尽可能快的速度检查的特定场景，这是我迄今为止发现的最佳方法。

好的一点是内存映射文件也可以与 Java 共享（事实证明这是需要的）。Java 还支持 Windows 上的内存映射文件，并且实现读/写逻辑相当简单。