存储/检索数据结构
我在Python中实现了一个后缀树，用来做全文搜索，效果非常好。不过有个问题：被索引的文本可能非常大，所以我们无法把整个结构都放在内存里。
图片：这是单词BANANAS的后缀树（在我的场景中，想象一下有一棵大100000倍的树）。
所以，我稍微研究了一下，发现了pickle模块，这是一个很棒的Python模块，可以把对象“加载”和“存储”到文件中，结果你猜怎么着？它和我的数据结构配合得非常好。
所以，长话短说：有什么好的策略可以把这个结构存储到磁盘上并从中读取呢？我的意思是，可以把每个节点存储在一个文件里，需要的时候再从磁盘加载，但这样做并不是最好的选择（因为访问磁盘的次数太多了）。
附注：虽然我把这个问题标记为python，但编程语言并不是问题的重点，磁盘存储和读取的策略才是关键。
5 个回答
试试使用压缩后缀树吧。
主要的想法是，和其说有很多只有一个字符的节点，不如把它们合并成一个包含多个字符的节点，这样可以节省很多多余的节点。
这个链接（http://www.cs.sunysb.edu/~algorith/implement/suds/implement.shtml）提到，你可以把一个160MB的后缀树压缩成33MB的压缩后缀树。这个效果真不错。
这些压缩树常用于在超大字符串中进行基因子串匹配。我以前用后缀树时经常内存不够，但压缩后就没有这个内存不足的错误了。
我希望能找到一篇免费的文章，能更好地解释这个实现。(http://dl.acm.org/citation.cfm?id=1768593)
管理这种结构的一个有效方法是使用 内存映射文件。在这个文件里，不是存储节点指针的引用，而是存储文件中的 偏移量。你仍然可以使用 pickle 将节点数据序列化成适合存储在磁盘上的格式，但要避免存储引用，因为 pickle 模块会试图一次性把整个树结构都嵌入进去（就像你看到的那样）。
通过使用 mmap 模块，你可以将文件映射到地址空间，并像读取一大串字节一样读取它。操作系统会处理实际从文件中读取数据、管理文件缓冲区以及所有细节。
你可以把第一个节点存储在文件的开头，然后用偏移量指向下一个节点。读取下一个节点只需要从文件中读取正确的偏移量即可。
内存映射文件的好处是它们不会一次性全部加载到内存中，而是根据需要从磁盘读取。我在一台只有 4 GB 内存的机器上，使用了一个 30 GB 的文件（在 64 位操作系统上），结果运行得很好。
如果你现在用的 pickle 已经能满足你的需求，那你可以看看 ZODB，它在 pickle 的基础上增加了一些功能。我在查看文档时，看到有一段话似乎可以解决你关于大小的担忧：
这个数据库可以在内存和存储之间自由移动对象。如果一个对象有一段时间没有被使用，它可能会被释放，下次使用时再从存储中加载它的内容。