c# - 快速随机访问二进制文件，但在需要时也可以顺序访问。如何布局？

Question

我有大约 10 亿个具有 DatasetKey 的数据集，每个数据集有 1 到 50 000 000 个子条目(一些对象)，平均约为 100，但有很多肥尾。

一旦写入数据，就不会更新数据，只有读取。

我需要通过 DatasetKey 和以下之一读取数据:
获取子条目数
获取前 1000 个子条目(如果小于 1000，则为最大值)
获取前 5000 个子条目(如果小于 5000，则为最大值)
获取前 100000 个子条目(如果小于 100000，则为最大值)
获取所有子条目

每个子条目的大小约为 20 字节到 2KB(平均 450 字节)。

我想使用的布局如下:

我创建了一个大小至少为 5MB 的文件。
每个文件至少包含一个 DatasetKey，但如果文件仍然小于 5MB，我会添加新的 DatasetKey(带有子条目)直到超过 5MB。
首先，我存储一个 header ，说明我将在哪个文件偏移量处找到什么样的数据。
此外，我计划使用 Protocol Buffer 存储序列化包。
前1000个参赛作品一个包，
一个用于接下来的 4000 个条目，
一个用于接下来的 95000 个条目，
一个用于下一个剩余条目。

我将文件大小存储在 RAM 中(存储所有 header 将占用我使用的机器所需的大量 RAM)。 当我需要访问特定的 DatasetKey 时，我会在 RAM 中查看我需要的文件。然后我从 RAM 中获取文件大小。 当文件大小约为 5MB 或更少时，我会将整个文件读入内存并进行处理。 如果超过 5MB，我将只读取第一个 xKB 以获取 header 。然后我从磁盘加载我需要的位置。

这听起来怎么样？这完全是胡说八道吗？或者一个好的方法？

使用这个设计我有以下想法:

我想将我的数据存储在自己的二进制文件中而不是数据库中，以便将来更容易备份和处理文件。
我本可以使用 postgresql，但我发现存储二进制数据会使 postgresqls-toast 执行不止一次访问数据的请求。
为每个 DatasetKey 存储一个文件需要太多时间将所有值写入磁盘。
数据是在 RAM 中计算的(因为不是所有数据都同时适合 RAM，它是按 block 计算的)。
5MB 的文件大小只是一个粗略的估计。

你说呢？ 提前感谢您的帮助!

编辑

一些更多的背景信息:

DatasetKey 是 ulong 类型。

子条目(有不同的类型)大部分时间如下所示:

public struct ChildDataSet
{
    public string Val1;
    public string Val2;
    public byte Val3;
    public long Val4;
}

我无法确定具体访问了哪些数据。计划是用户可以访问特定 DatasetKeys 的前 1000、5000、100000 或所有数据。基于他们的设置。

我想保持尽可能短的响应时间并使用尽可能少的磁盘空间。

@关于随机访问(Marc Gravells 问题):

我不需要访问元素编号。 123456 对于特定的 DatasetKey。

当在一个文件中存储多个 DatasetKey(带有子条目)时(我将其设计为不必创建太多文件的方式)， 我需要随机访问该文件中特定 DatasetKey 的前 1000 个条目，或前 5000 个(因此我会读取 1000 和 4000 包)。

我只需要访问与一个特定 DatasetKey (uint) 有关的以下内容:
1000 个子条目(如果少于 1000，则为所有子条目)
5000 个子条目(如果少于 5000，则为所有子条目)
100000 个子条目(如果小于 100000，则为所有子条目)
所有子条目

我提到的所有其他事情只是我的设计尝试:-)

编辑，为一个类(class)中的一个列表流式传输？

public class ChildDataSet
{
    [ProtoMember(1)]
    public List<Class1> Val1;
    [ProtoMember(2)]
    public List<Class2> Val2;
    [ProtoMember(3)]
    public List<Class3> Val3;
}

我可以流式传输 Val1，例如获取 Val1 的前 5000 个条目

Answer 1

使用单个文件。在文件的前面，存储 ID 到偏移量的映射。假设您的 ID 空间稀疏，存储一个 ID+偏移量对数组，按 ID 排序。使用二进制搜索找到正确的条目。大致log(n/K) 查找，其中“K”是您可以存储在单个磁盘 block 上的 ID+偏移对的数量(尽管操作系统可能需要额外的一两次查找才能找到每个 block )。

如果您想花费一些内存来减少磁盘寻道，请在内存中存储每 10,000 个 ID 的排序数组。查ID的时候，找最近的ID，不要翻过去。这将在 header 中为您提供一个 10,000-ID 范围，您可以对其进行二进制搜索。您可以通过增加/减少内存表中的键数来非常精确地增加/减少内存使用量。

密集的 ID 空间:但是如果您的 ID 空间相对密集，那么所有这些都是完全没有必要的，这似乎是因为在总共约 40 亿个 ID 中您有 10 亿个 ID(假设 uint 是 32 位)。

上述排序数组技术需要存储 10 亿个 ID 的 ID+偏移量。假设偏移量是 8 个字节，这需要 12 GB 的文件头。如果您使用直接偏移量数组，文件头中需要 32 GB，但现在只有一个磁盘寻道(加上操作系统的寻道)并且没有内存中查找表。

如果 32 GB 太多，您可以使用混合方案，在前 16 位或 24 位上使用数组，在后 16 位或 8 位上使用排序数组。如果您有多个级别的数组，那么您基本上有一个 trie(正如其他人所建议的)。

关于多个文件的注意事项:对于多个文件，您基本上是在尝试使用操作系统的名称查找机制来处理一级 ID 到偏移量查找。这不如自己处理整个查找有效。

不过，将事物存储为多个文件可能还有其他原因。对于单个文件，如果有任何变化，您需要重写整个数据集。对于多个文件，您只需重写一个文件。这就是操作系统的名称查找机制派上用场的地方。

但如果您最终使用多个文件，ID 查找可能更有效，以确保它们具有大致相同的 key 数量而不是相同的文件大小。