python - 存储/检索数据结构

Question

我已经在 Python 中实现了一个后缀树来进行全文搜索，而且效果非常好。但是有一个问题:索引的文本可能非常大，所以我们无法将整个结构保存在 RAM 中。

IMAGE:单词 BANANAS 的后缀树(在我的场景中，想象一棵大 100000 倍的树)。

因此，通过稍微研究一下，我发现了 pickle 模块，这是一个很棒的 Python 模块，用于从文件“加载”和“转储”对象，猜猜是什么？它非常适合我的数据结构。

所以，长话短说:在磁盘上存储和检索此结构的最佳策略是什么？我的意思是，一个解决方案可能是将每个节点存储在一个文件中，并在需要时从磁盘加载它，但这不是最好的想法(磁盘访问太多)。

---

脚注:虽然我已将此问题标记为 python ，编程语言不是问题的重要部分，磁盘存储/检索策略才是重点。

Answer 1

管理这种结构的有效方法是使用内存映射文件。在文件中，不是存储节点指针的引用，而是将偏移量 存储到文件中。您仍然可以使用 pickle 将节点数据序列化为适合存储在磁盘上的流，但您将希望避免存储引用，因为 pickle 模块将希望嵌入您的一次完成整棵树(如您所见)。

使用 mmap模块，您可以将文件映射到地址空间并像读取一个巨大的字节序列一样读取它。操作系统负责实际读取文件和管理文件缓冲区以及所有细节。

您可以将第一个节点存储在文件的开头，并具有指向下一个节点的偏移量。读取下一个节点只是从文件中的正确偏移量读取的问题。

内存映射文件的优点是它们不会一次加载到内存中，而是仅在需要时从磁盘读取。我已经(在 64 位操作系统上)在一台只安装了 4 GB RAM 的机器上用一个 30 GB 的文件完成了这项工作，并且运行良好。