使用结构数组将记录存储在字节数组中

Question

我有2亿条记录,其中一些记录具有可变大小的字段(字符串,可变长度数组等).我需要对它们执行一些过滤器,聚合等(面向分析的查询).

我想把它们全部放在内存中(足以放入一个大盒子里),然后对它们进行线性扫描.我可以采取两种方法,我希望听到您对哪种方法更好的看法,以最大限度地提高速度:

1. 使用带有char*和int*等的结构数组来处理可变长度字段
2. 使用大字节数组,像二进制流一样扫描字节数组,然后解析记录

你会推荐哪种方法？

更新:使用C.

Answer 1

不幸的答案是"这取决于你没有提供的细节",虽然这是真的,但并不是特别有用.解决这类问题的一般建议是从最简单/最明显的设计开始,然后根据需要进行分析和优化.如果它真的很重要,您可以使用您的确切数据和用例来开始一些非常基本的基准测试,以便更准确地了解您应该采取的方向.

查看一些具体设计及其一般优缺点:

一个大缓冲区

 char* pBuffer = malloc(200000000);

• 假设您的数据可以同时适合内存.
• 对所有文本(或主要是文本)数据更好地工作.
• 这不是我对大数据的首选,因为它只是镜像磁盘上的数据.最好只使用硬件/软件文件缓存/提前读取并直接从驱动器读取数据,或者根据需要进行映射.
• 对于线性扫描,这是一种很好的格式,但如果它需要复杂的解析(特别是如果你必须进行多次扫描),你就会失去一些.
• 假设您可以一个接一个地打包结构,可以获得最小的开销.

静态结构

 typedef struct {
     char  Data1[32];
     int   Data2[10];
 } myStruct;

 myStruct *pData = malloc(sizeof(myStruct)*200000000);

• 最简单的设计,可能是以内存为代价的最佳速度(没有实际的分析).
• 如果您的可变长度数组具有多种大小,则会浪费大量内存.由于您有2亿条记录,因此可能没有足够的内存来使用此方法.
• 对于线性扫描,由于内存缓存/预取,这可能是最佳的内存结构.

动态结构

 typedef struct {
     char* pData1;
     int*  pData2;
 } myStruct2;

 myStruct2 *pData = malloc(sizeof(myStruct2)*200000000);

• 有2亿条记录需要大量的动态内存分配,这很可能会对速度产生重大影响.
• 如果您的动态数组具有多种大小,则有可能提高内存效率(尽管请参见下一点).
• 注意指针大小的开销.在32位系统上,这种结构需要8个字节(忽略填充)来存储指针,对于2亿条记录,这些指针仅为1.6 GB!如果您的动态数组通常很小(或为空),那么开销可能会比实际数据花费更多内存.
• 对于数据的线性扫描,当您以非线性方式访问存储器时,这种类型的结构可能表现不佳,这是预取器无法预测的.

流

• 如果您只需要对数据进行一次扫描,那么我将查看一个流式解决方案,您可以从文件中一次读取一小部分数据.
• 适用于不适合内存的非常大的数据集.
• 这里的主要限制是磁盘读取速度以及解析的复杂程度.
• 即使您必须使用文件缓存进行多次传递,这可能与其他方法的速度相当.

哪个是"最好的"真的取决于你的具体情况......我可以想到每个人都是首选的方法.