Python中有什么好的磁盘“集合”实现？

Question

我正在用Python写一个程序，需要存储一个持久的“集合”数据结构，这个集合里包含很多固定大小的哈希值（SHA256，不过这不是重点）。最重要的操作是 插入 和 查找。删除操作在正常情况下不需要。这个集合会随着时间的推移而增长，最终可能会装不下所有数据。

我考虑过：

• 用 pickle 存储在磁盘上的 set（写新文件到磁盘很慢，可能需要几秒钟，而且最终会装不下所有数据）
• 使用SQLite数据库（这需要额外的依赖，默认情况下没有）
• 自定义基于磁盘的平衡树结构，比如B树或类似的结构

理想情况下，应该有一个内置的Python模块，可以支持这些操作。这里有什么好的选择吗？

在我写完这些后，我发现了一个链接 快速的基于磁盘的哈希表？，里面有一些不错的想法。我喜欢那里的mmap/bucket的回答。

（如果你感兴趣，这是为了重写 shaback。）

Answer 1

按照Brian Minton的建议，把第二个值设置为1是个方便的解决办法。cPickle也不错。

不过，你也可以考虑用json。查一下谷歌，听说json的解析速度比Pickle/cPickle快。（例如，http://kovshenin.com/2010/pickle-vs-json-which-is-faster/）

Answer 2

你可以使用一种叫做DBM的数据库风格。我正在用dbm做类似的事情，只是把所有的键都存成值为'1'。因为它是BSD许可的，所以dbhash模块应该可以用。（不过这个模块已经不推荐使用了，所以在Python 3中不能用；而且因为这个原因，长期使用也不是个好主意）。另外，你可以使用gdbm模块（在Python 3中是dbm.gdbm）和ndbm模块（在Python 3中是dbm.dbm）。还有一个叫做dumbdbm的模块（在Python 3中是dbm.dumbdbm），这个模块是纯Python写的，永远可以用，但速度稍微慢一点。如果你需要同时进行多个读取和写入，绝对不要使用dumbdbm模块。

这些不同的dbm模块的工作方式和Python字典很像，只不过它们的键和值都需要是字符串。你可以像使用集合或字典那样使用“in”关键字。

Answer 3

另一个选择是使用 shelve，我知道它和 pickle 是一样的（底层实现上），但我觉得这是个不错的选择（我在你的选项列表中没看到这个 :-))。或者，如果你不介意使用第三方库的话，可以看看 shove（它可以看作是 shelve 的升级版）。