存储/检索数据结构

我已经在Python中实现了一个后缀树以进行全文搜索，并且它工作得很好。但是有一个问题：索引文本可能非常大，所以我们无法在RAM中拥有整个结构。存储/检索数据结构

enter image description here

IMAGE：这个词BANANAS后缀树（在我的情况下，设想一个树大10万次）。

因此，研究一下它，我发现pickle模块是一个很棒的Python模块，用于从文件中“加载”和“倾倒”对象，并猜测是什么？它对我的数据结构非常有用。

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

脚注：虽然我已标记这个问题为python，编程语言不是问题的重要组成部分，在磁盘存储/检索策略，是真正的重点。

来源

2011-11-28 juliomalegria

一个重要的问题是您是否要创建此结构*一次*并多次使用它，或者是否要创建它并*允许更新*。 –

@GregHewgill：基本上，只需要一个大的文本处理来创建结构，然后就可以使用它。顺便提一下 – juliomalegria

- 使用cPickle - 酸菜快得多。也为什么不使用JSON，而是工作与磁盘工作对付nosql数据库（我不是专家是这个主题告诉你哪一个，但NosSql是已知的解决方案，正是这种场景 - 很好，我相信比多个磁盘文件） – alonisser

如果pickle已经在为您工作，您可能需要查看ZODB，它在pickle之上添加了一些功能。看看这个文档，我看到这个段落的目的是解决你所面对的大小问题：

数据库在内存和存储之间自由移动对象。如果对象有一段时间没有被使用，它可能会在下次使用时从内存中加载并释放内容。

来源

2011-11-28 18:59:07 jcollado

感谢所有回答，在测试了所有选项并经过多次讨论之后，我做出了我的决定：我将使用'ZODB'，一个非常有趣的模块，如果您喜欢这种类型的模块，请检查一下。 – juliomalegria

将它存储在sqlite？

SQLite的：

有高达2个TB的数据，
支持SQL查询的支持，
是用于存储应用程序内的数据大更换，
可以支持〜100K访问（如果用于平均web应用程序），

因此，仔细研究此解决方案可能会更好，因为它已被证明成为在应用程序中存储数据的有效方式。

来源

2011-11-28 18:42:32 Tadeck

感谢所有回答，在测试完所有选项并经过多次深思熟虑后，我做出了我的决定：我将使用'ZODB'，一个非常有趣的模块，如果您喜欢这种类型的模块，请检查一下。 – juliomalegria

@ julio.alegria：好的，感谢分享解决方案:) – Tadeck

也许你可以结合cPickle和bsddb数据库，它可以让你将你的酸洗节点存储在一个类似于字典的对象中，该对象将存储在文件系统中;因此您可以稍后加载数据库并从您需要的节点获得真正出色的性能。

在一个非常简单的方法：

import bsddb 
import cPickle 

db = bsddb.btopen('/tmp/nodes.db', 'c') 
def store_node(node, key, db): 
    db[key] = cPickle.dumps(node) 

def get_node(key, db): 
    return cPickle.loads(db[key])

来源

2011-11-28 18:48:22

感谢所有的答复，经过测试你的所有选择和经过大量的审议后，我做出了我的决定：我要使用'ZODB'，a非常有趣的模块，如果你喜欢这种类型的东西，请检查一下。 – juliomalegria

不错的选择:-) –

一种有效的方式来管理一个结构类似这样是使用内存映射文件。在文件中，不是存储节点指针的引用，而是将偏移量存储到文件中。您仍然可以使用pickle将节点数据串行化为适合存储在磁盘上的流，但是您将希望避免存储引用，因为pickle模块需要一次嵌入整个树（如您所见）。

使用mmap模块，可以将文件映射到地址空间并像读取大量字节一样读取它。操作系统负责从文件中读取文件，管理文件缓冲区和所有细节。

您可能会将第一个节点存储在文件的起始位置，并具有指向下一个节点的偏移量。读取下一个节点仅仅是从文件中正确的偏移量读取的问题。

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

来源

2011-11-28 18:49:13

感谢所有的回答，经过测试所有的选择和经过大量的审议后，我做出了我的决定：我要使用'ZODB'，一个非常有趣的模块，检查出来，如果你像这样的事情。 – juliomalegria

试试看压缩后的后缀树。

其主要思想是代替1个字符的大量节点，可以将它们压缩为1个节点中的多个字符，从而节省额外的节点。

此处链接（http://www.cs.sunysb.edu/~algorith/implement/suds/implement.shtml）表示您可以将160MB后缀树转换为33MB压缩后缀树。收益颇丰。

这些压缩树被用于巨大字符串上的遗传子字符串匹配。我以前用后缀树的内存不足，但我压缩后，内存不足错误消失。

我希望我能找到一个更好解释实施的未付费文章。（http://dl.acm.org/citation.cfm?id=1768593）

来源

2011-12-16 03:10:58 Adrian

但即使树被压缩，它也必须存储在磁盘中。根据你的数据的大小，最终是否是 – juliomalegria

。 DNA序列相当长，压缩的后缀树与它们一起工作（全部在内存中）。 – Adrian

存储/检索数据结构

回答

相关问题