Python中有B-Tree数据库或框架吗？

Question

我听说B-Tree数据库比Hash表更快，所以我想到在我的项目中使用B-Tree数据库。 python中是否有任何现有的框架允许我们使用这样的数据结构，还是我必须从头开始编码？

Answer 1

无论是在内存中还是在块存储中（如在数据库中），选择 B 树而不是哈希表的唯一原因是支持除 equal 以外的查询。 B 树允许您以良好的性能执行范围查询。不过，许多键值存储（例如 Berkley db）不会使其在外部可见，因为它们仍然对键进行哈希处理，但这仍然可以让您快速稳定地迭代整个数据集（即使有添加，迭代器仍然有效）或删除，或者必须重新平衡树）。

如果不需要范围查询，也不需要并发迭代，那么就不需要b树，使用哈希表，在任何规模上都会更快。

编辑：我有机会证明上述内容实际上是正确的；为此，

blist

包似乎是排序容器库最完整的实现。

Answer 2

你真的应该看看 zodb。 http://www.zodb.org/en/latest/

我很久以前就写了一本关于它的专着，尽管它是西班牙语的http://sourceforge.net/projects/banta/files/Labs/zodb/Monografia%20-%20ZODB.pdf/download

有很多英文信息。

Answer 3

首先对您想要执行的操作进行编程，然后根据需要进行优化。期间。

编辑：

http://pypi.python.org/pypi/blist

替换 python 的内置列表。

Answer 4

SQLite3 在内部使用 B+ 树，但听起来您可能需要一个键值存储。尝试使用 Berkeley DB。如果您不需要事务，请尝试 HDF5。如果您想要分布式键值存储，也可以使用 http://scalien.com/keyspace/，但这是一个服务器-客户端类型系统，可以打开各种 NoSQL 键值存储。

所有这些系统的插入和检索时间复杂度都是 O(log(n))，因此它们可能会比您当前使用的哈希表慢。

Kyoto Cabinet 提供了一个哈希树，因此这可能是您所关注的更多内容，因为它应该是 O(1) 的插入和检索，但是如果您需要的话，您不能进行中序遍历（尽管因为您当前正在使用哈希树，这不应该是问题）。

http://fallabs.com/kyotocabinet/

如果您追求性能，则需要以编译语言实现速度关键项，然后使用 Python 提供包装 API。

Answer 5

Here有一个很好的btree纯python实现。如果需要，您可以对其进行调整。

Answer 6

您可能想看看 mxBeeBase，它是 eGenix mx Base Distribution 的一部分。它包括快速的磁盘 B+Tree 实现，并提供允许在 Python 中构建磁盘字典或数据库的存储类。