c# - 数据结构的最佳存储，用于快速查找和持久化

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 位数字)。

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

我正在考虑如何以最佳方式存储它。最好在磁盘上(带缓存)，但我希望代码可维护且干净。

如果项目 ID 从 0 开始，我考虑为每个用户创建一个长度为 MaxItemId/8 的字节数组，并在项目存在或不存在时设置一个 true/false 位.这会将每个用户的数组长度限制在 1mb 以上，并提供快速查找以及一种简单的方法来更新每个用户的列表。通过使用 .Net 4 框架将其作为 Memory Mapped Files 持久化，我认为我也可以获得不错的缓存(如果机器有足够的 RAM)而无需自己实现缓存逻辑。解析 ID、去除年份并每年存储一个数组可能是一种解决方案。

ItemId -> UserId[] 列表可以直接序列化到磁盘并使用普通的 FileStream 进行读/写，以便在有更改时保留列表并区分它。

每次添加新用户时，所有列表也必须更新，但这可以在夜间完成。

问题

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

[更新 2010-03-31]

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

• 有两列(userid,itemid)的表都是 Int
• 两列的聚集索引
• 为 180 位用户添加了约 800.000 个项目 - 总计 1.44 亿行
• 为 SQL 服务器分配 4gb 内存
• 双核 2.66ghz 笔记本电脑
• 固态硬盘
• 使用 SqlDataReader 将所有 itemid 读入列表
• 遍历所有用户

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

在此过程中，即使在一个线程上，CPU 也处于屋顶状态。由于快速循环，我的测试应用程序需要一些，其余的用 sql 执行。

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

[更新 2010-03-31 #2]

我用相同的数据进行了快速测试，将其作为内存映射文件中的位。它的表现要好得多。六个线程产生的访问时间在 0.02 秒到 0.06 秒之间。纯粹的内存限制。映射文件由一个进程映射，并同时被其他六个进程访问。由于 sql base 占用了 4gb，磁盘上的文件占用了 23mb。

Answer 1

经过大量测试后，我最终使用了内存映射文件，使用 NTFS Sparse Files with C# 中的代码用稀疏位 (NTFS) 标记它们.

维基百科对 sparse file 的解释是。

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

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

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

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