我有一个非常普遍的问题，为磁盘中的字符串数组创建索引。简而言之，我需要将每个字符串的位置存储在磁盘中的表示形式中。例如，一个非常幼稚的解决方案将是一个索引数组，如下所示:
uint64 idx [] = {0，20，500，1024，...，103434};
也就是说，第一个字符串位于位置0，第二个字符串位于位置20，第三个字符串位于位置500，第n个字符串位于位置103434。
这些位置始终是连续的非负64位整数。尽管数字可能有所不同，但实际上我希望典型的差异在2 ^ 8到2 ^ 20的范围内。我希望该索引在内存中被映射，并且位置将被随机访问(假设分布均匀)。
我当时正在考虑编写自己的代码以进行某种块增量编码或其他更复杂的编码，但是在编码/解码速度和空间之间存在许多不同的折衷，我宁愿以一个可用的库作为起点甚至无需任何定制就可以解决问题。
有什么提示吗？一个c库将是理想的，但是一个c++库也将允许我运行一些初始基准测试。
如果您仍在关注其他一些细节。这将用于在库cmph(http://cr.yp.to/cdb/cdbmake.html)的顶部构建类似于cdb(http://cmph.sf.net)的库。简而言之，它适用于基于大磁盘的只读关联映射，并且在内存中具有较小的索引。
由于它是一个库，因此我无法控制输入，但是我要优化的典型用例具有数以百计的值，平均值大小在几千字节范围内，最大值在2 ^ 31。
作为记录，如果我找不到准备使用的库，则打算在64个整数的块中实现增量编码，到目前为止，初始字节指定了块偏移量。块本身将用一棵树索引，从而给我O(log(n/64))访问时间。还有太多其他选择，我不愿讨论它们。我真的很期待可以使用代码，而不是有关如何实现编码的想法。一旦工作，我将很高兴与大家分享我所做的事情。
感谢您的帮助，如果您有任何疑问，请告诉我。
最佳答案
我使用fastbit(Kesheng Wu LBL.GOV)，看来您需要一些好，快速且立即的东西，因此fastbit是Oracle BBC(字节对齐的位图代码，berkeleydb)的一项非常有竞争力的改进。它很容易设置，而且非常好。
但是，如果有更多的时间，您可能需要查看gray code解决方案，这似乎对您的目的而言是最佳的。
Daniel Lemire在code.google上发布了许多C/++/Java库，我已经阅读了他的一些论文，它们相当不错，在fastbit上有几项改进，并且提供了使用置换格雷码对列进行重新排序的替代方法。
几乎忘了，我也遇到过Tokyo Cabinet，尽管我认为它不太适合我当前的项目，但如果我以前知道它的话，我可能会认为它更多；)，它具有很大的互操作性，
就像您提到的CDB一样，TC基准测试具有TC模式(TC支持对不同性能的几个操作约束)，其中CDB的读取性能和写入性能超过CDB十倍。
关于您的增量编码要求，我对bsdiff很有信心，它的性能优于任何file.exe内容修补系统，它可能还具有一些基本接口(interface)可以满足您的一般需求。
Google的新二进制压缩应用程序courgette可能值得一试，以防万一您错过了新闻稿，在我看到的一个测试用例中，diff的差异是bsdiff的10倍。