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

Question

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

数据写入后，不会对数据进行更新，只会读取。

我需要通过 DatasetKey 和以下之一读取数据：
获取子条目数
获取前 1000 个子条目（如果少于 1000，则最多）
获取前 5000 个子条目（如果少于 5000，则最多）
获取前 100000 个子条目（如果少于 100000，则最多）
获取所有子条目

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

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

我创建一个大小至少为 5MB 的文件。
每个文件至少包含一个 DatasetKey，但如果文件仍然小于 5MB，我会添加新的 DatasetKey（带有子条目），直到超过 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 或所有数据。根据他们的设置。

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

@关于随机访问（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（假设 uint 是 32 位）。

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

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

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

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

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

Answer 2

焦点似乎集中在前 n 个项目上；在这种情况下，protobuf-net 是理想的选择。请允许我演示一下：

using System;
using System.IO;
using System.Linq;
using ProtoBuf;


class Program
{
    static void Main()
    {
        // invent some data
        using (var file = File.Create("data.bin"))
        {
            var rand = new Random(12346);
            for (int i = 0; i < 100000; i++)
            {
                // nothing special about these numbers other than convenience
                var next = new MyData { Foo = i, Bar = rand.NextDouble() };

                Serializer.SerializeWithLengthPrefix(file, next, PrefixStyle.Base128, Serializer.ListItemTag);
            }
        }
        // read it back
        using (var file = File.OpenRead("data.bin"))
        {
            MyData last = null;
            double sum = 0;
            foreach (var item in Serializer.DeserializeItems<MyData>(file, PrefixStyle.Base128, Serializer.ListItemTag)
                .Take(4000))
            {
                last = item;
                sum += item.Foo; // why not?
            }
            Console.WriteLine(last.Foo);
            Console.WriteLine(sum);
        }
    }
}
 [ProtoContract]
class MyData
{
     [ProtoMember(1)]
     public int Foo { get; set; }
     [ProtoMember(2)]
     public double Bar { get; set; }
}

特别是，由于 DeserializeItems 是一个流式 API，因此可以使用 LINQ 的 Take（或者只是 <代码>foreach与break）。

但请注意，现有的公共 dll 不会喜欢您使用 struct； v2 在那里做得更好，但就我个人而言，我会将其设为一个类。

Answer 3

使用尽可能多的设置创建解决方案。然后创建一些测试脚本并查看哪些设置效果最好。

创建一些设置：

• 原始文件大小
• 单独的文件头
• 缓存策略（内存中的数量和内容）

Answer 4

为什么不尝试 内存映射文件 或带有 文件流？