快速随机访问二进制文件,但也可以在需要时顺序访问.怎么布局？

Question

我有大约10亿个数据集,它们有一个DatasetKey,每个数据集有1到5 000 000个子条目(一些对象),平均值大约是100,但有很多胖尾巴.

写入数据后,数据不会更新,只会读取数据.

我需要通过DatasetKey读取数据并执行以下操作之一:
获取子条目数
获取前1000个子条目(最大值小于1000)
获取前5000个子条目(最大值小于5000)
获取前100000个子条目(最大值如果小于100000)
获取所有子条目

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

我想要使​​用的布局如下:

我创建了一个大小至少为5MB的文件.
每个文件至少包含一个DatasetKey,但如果文件仍然小于5MB,我添加新的DatasetKeys(带子条目),直到我超过5 MB.
首先,我存储一个标题,说明哪些文件偏移我会找到什么样的数据.
此外,我计划使用协议缓冲区存储序列化包.
前1000个条目的一个包,
一个用于接下来的4000个条目,
一个用于接下来的95000个条目,
一个用于下一个剩余的条目.

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

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

使用这个设计我有以下几点:

我想将我的数据存储在一个自己的二进制文件而不是数据库中,以便将来更容易备份和处理文件.
我会使用postgresql,但我想出存储二进制数据会使postgresqls-toast不止一次寻求访问数据.
为每个DatasetKey存储一个文件需要太多时间将所有值写入磁盘.
数据在RAM中计算(因为并非整个数据在RAM中同时拟合,它是以块为单位计算的).
5MB的文件大小只是一个粗略的估计.

你说什么？提前谢谢你的帮助!

编辑

更多背景资料:

DatasetKey的类型为ulong.

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

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

我无法确切地知道访问了哪些数据.计划是用户可以访问特定DatasetKeys的前1000,5000,100000或所有数据.根据他们的设置.

我希望尽可能降低响应时间并尽可能少地使用磁盘空间.

@Regarding随机访问(Marc Gravells问题):

我不需要访问元素号.123456用于特定的DatasetKey.

当在一个文件中存储多个DatasetKey(带有子条目)时(我将其设计为不创建大量文件的方式),我需要随机访问该文件中特定DatasetKey的前1000个条目,或者第一个5000(所以我会阅读1000和4000包).

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

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

编辑,在一个类中流式传输一个列表？

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”是可以存储在单个磁盘块上的 ID+偏移对的数量（尽管操作系统可能需要额外的一两次查找才能找到每个块）。

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

密集 ID 空间：但是，如果您的 ID 空间相对密集，那么所有这些都是完全不必要的，这似乎可能是因为您在总共可能的约 40 亿个 ID 中拥有 10 亿个 ID（假设是uint32 位）。

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

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

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

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

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