问题标签 [on-disk]

我有一个要索引的文件（具体来说是 fasta 文件），以便我可以快速找到文件中的任何子字符串，然后在原始 fasta 文件中找到该位置。

在许多情况下，使用 Trie 或子字符串数组很容易做到这一点，不幸的是，我需要索引的字符串是 800+ MB，这意味着在内存中执行它们是不可接受的，所以我正在寻找一种合理的方法来创建它磁盘上的索引，内存使用量最少。

（编辑澄清）

我只对蛋白质的标题感兴趣，所以对于我感兴趣的最大数据库，这是大约 800 MB 的文本。

我希望能够根据输入字符串在 O(N) 时间内找到确切的子字符串。这必须在 32 位机器上可用，因为它将被运送给随机的人，他们预计不会拥有 64 位机器。

我希望能够针对一行中的任何断字进行索引，直到行尾（尽管行可能有几 MB 长）。

希望这可以阐明需要什么以及为什么给出的当前解决方案没有启发性。

我还应该补充一点，这需要在 java 中完成，并且必须在各种操作系统的客户端计算机上完成，所以我不能使用任何特定于操作系统的解决方案，它必须是一个编程解决方案。

我喜欢使用 STL 开发算法，但是，我经常遇到这个问题，即我的数据集对于堆来说太大了。

我一直在寻找 STL 容器和磁盘支持的算法的替代品，即存储在磁盘上而不是堆上的数据结构。

一位朋友最近向我指出了stxxl。在我过多参与之前......我应该考虑是否有其他可用的磁盘支持的 STL 替代品？

注意：我对持久性或嵌入式数据库不感兴趣。请不要提及 boost::serialization、POST++、关系模板库、Berkeley DB、sqlite 等。我知道这些项目并在它们适合我的目的时使用它们。

更新：有几个人提到了内存映射文件和使用自定义分配器，顺便说一句，这是很好的建议，但我会指出他们在这里的讨论中，大卫亚伯拉罕建议磁盘支持的容器需要自定义迭代器。这意味着自定义分配器方法不太可能奏效。

我需要存储大量整数。整数的输入流中可能有重复项，我只需要在它们之间存储不同的内容。我最初使用的是 stl set，但是当输入的整数数量太高时它会 OutOfMem。我正在寻找一些 C++ 容器库，它允许我存储可能由文件支持的上述要求的数字，即容器不应尝试将所有数字保留在内存中。我不需要持久存储这些数据，我只需要在其中找到唯一值。

有谁知道在哪里可以找到 B+Tree 磁盘实现？我前后浏览了谷歌，不幸的是我找不到任何明智的东西。其他线程建议可能从 sqlite、sqljet 或 bdb 中获取树，但这些树嵌套在整个数据库中，您不能真正“仅仅”过滤掉 B+Tree。我真的只是在寻找磁盘上的 B+Tree ......周围没有任何花哨的东西。

我有大约 5 亿个 128 位整数，每年增加大约 1 亿个。什么都不会被删除。这些数字在规模和时间上是均匀分布的。

基本上，我需要的只是一个添加操作，它还返回数据库中是否已经存在该数字。另外，我不想为这个系统使用太多的 RAM，所以只是将所有内容存储在内存中并不是我想要的。

到目前为止，我们已经在 MySQL 上使用了几个 MyISAM 表，使用两个 bigint 作为主键。这给了我们不错的性能，但我怀疑它不是这项工作的正确工具。在拆分表之前，我们遇到了一些性能问题，并且我们在断电时遇到了损坏。此外，数据库为我们提供了更多我们不需要的功能。

我在 Linux 上使用 Python，但我愿意接受建议。

C++ 中的类似问题。

更新：Marcelo 的评论提到了Bloom Filter，这对我来说似乎很有希望。由于我正在使用哈希，我已经放弃了完全的准确性，所以这可能是一个很好的精度/性能折衷。

我希望获得 Java 中稀疏文件的准确（即磁盘上的实际大小，而不是包含所有 0 的正常大小）测量值。

在 Windows 上的 C++ 中，人们会使用GetCompressedFileSize. 我还没有遇到过如何在 Java 中做到这一点？

如果没有直接的等价物，我将如何测量稀疏文件中的数据，而不是包括所有零的大小？

为了澄清起见，我希望在 Linux 操作系统和 Windows 上运行稀疏文件测量，但是我不介意编写两个单独的应用程序！

问题的简化版本

我有一个巨大的类似矩阵的数据集，我们现在可以假装它实际上是存储在磁盘上的一个n逐个n矩阵作为n^2IEEE-754 双精度数（请参阅行下方的详细信息，了解这是如何简化的——它可能很重要）。该文件的数量级为千兆字节，但在某个（纯）函数中，我只需要其中n包含的元素的顺序。确切需要哪些元素是复杂的，而不是像一个简单的切片。

从磁盘读取文件和计算解耦的选项是什么？最重要的是，我想把磁盘上的数据当作内存中的数据来对待（我当然准备向所有参照透明之神发誓，磁盘上的数据不会改变）。我看过mmap和朋友，但一些粗略的测试表明，这些似乎没有足够积极的空闲内存。

如果我需要对内存中保存多少文件进行如此细粒度的控制，我是否必须将我的计算与 IO 结合起来？

更真实的磁盘数据描述

磁盘上的数据实际上并不像描述的那么简单。更接近事实的情况如下：文件以 32 位整数开头n。然后精确出现以下情况n：一个 32 位整数m_i> 0 (1 ≤ i ≤ n)，紧随其后的是m_iIEEE-754 doubles x_(i,1),…,x_(i, m_i)。（所以，这是一个锯齿状的二维数组）。

在实践中，确定i和j需要哪个x_(i, j)在很大程度上取决于m_i's. 当处理 mmap 的问题时，读取这么多这些m_is 的需要似乎本质上是将整个文件加载到内存中。问题是这一切似乎都停留在那里，我担心我将不得不将我的计算拉入IO，以便对这个内存的释放进行更细粒度的控制。

此外，“数据结构”实际上由大量这些文件组成，这些文件由它们的文件名参数化。它们加起来大约为 1 GB。

尝试更加挥手，但可能更容易理解问题的版本

假设我在磁盘上有一些由n^2元素组成的数据。纯 Haskell 函数需要元素的顺序n，但它们中的哪一个以复杂的方式取决于值。我不想将整个文件加载到内存中，因为它很大。一种解决方案是将我的函数放入IOmonad 并在需要时读出元素，但我称之为“放弃”。mmap让我们将磁盘上的数据视为在内存中，本质上是在操作系统的虚拟内存系统的帮助下进行惰性 IO。这很好，但是由于确定需要哪些数据元素需要访问大量文件，因此 mmap 似乎在内存中保留了太多文件。在实践中，我发现读取我需要的数据来确定我需要的数据实际上需要在使用 mmap 时将整个文件加载到内存中。

我有什么选择？

鉴于存储布局需要与逻辑设计完全匹配，我想知道如何最好地使用磁盘数据结构。我发现当您需要为存储设置特定布局时，结构对齐和包装并没有太大帮助。

我解决这个问题的方法是使用处理器指令定义结构的（宽度），并在分配遵循逻辑结构模型的数据后写入磁盘的字符（字节）数组时使用宽度。

例如：

如果我将 foo 持久保存在磁盘上，则“标志”值将出现在数据的最后。鉴于我可以在使用 &foo 类型的 fread 读取数据时轻松使用 foo ，然后正常使用该结构而无需任何进一步的字节摆弄。

相反，我更喜欢这样做

然后我只使用 fwrite 和 fread 提交和读取字节，但后来解压缩它们以使用存储在各种逻辑字段中的数据。

我想知道哪种方法最好使用，因为我希望磁盘存储的布局与逻辑布局相匹配……这只是一个例子……

如果有人知道每种方法在解码/解包字节与直接从其磁盘表示复制结构方面的效率如何，请分享，我个人更喜欢使用第二种方法，因为它可以让我完全控制存储布局，但我还没有准备好牺牲寻找性能，因为这种方法需要大量循环逻辑来解包/遍历字节到数据中的各种边界。

谢谢。

我目前正在尝试了解 iOS On-Disk Encryption 的工作原理。我已经阅读了 iOS App Programming Guide 中的使用磁盘加密保护数据。它说用户必须为设备设置有效的密码锁。

但有些事情对我来说仍然不清楚：

如果...，应用程序仍然能够解密以前加密的文件吗？

1. 用户将禁用密码？
2. 用户将禁用密码，然后以相同的值重新启用它？
3. 用户将更改密码？

在通过给定节点的传入和传出关系进行查询时，我注意到性能差异。在这种情况下，传出速度要快得多。

生成图形的输入文件按每条边的起始节点排序。

输入文件的顺序重要吗？外向关系的处理方式是否有所不同？

我阅读了一些关于内部的背景知识，但似乎没有回答我关于性能差异的问题。