Berkeleydb - B树与哈希表

Question

我试图理解在使用BerkeleyDB时应该选择哪种访问方法:B-Tree与HashTable.Hashtable提供O(1)查找,但插入是昂贵的(使用线性/可扩展散列我们得到分摊O(1)插入).但B-Trees提供log N(base B)查找和插入时间.B-Tree还可以支持范围查询并允许按排序顺序进行访问.

1. 除了这些考虑因素还应考虑其他因素吗？
2. 如果我不需要支持范围查询,我可以使用Hashtable访问方法吗？

Answer 1

当您的数据集变得非常大时,B树仍然更好,因为大多数内部元数据可能仍然适合缓存.哈希,就其本质而言(数据的统一随机分布)本质上是缓存不友好的.即,一旦数据集的总大小超过工作内存大小,散列性能就会下降,而B树性能会优雅地降低(实际上是对数).

Answer 2

这取决于您的数据集和密钥在小数据集上，您的基准将接近相同，但是在较大的数据集上，它可能会根据密钥类型/您拥有的数据量而有所不同。通常 b 树更好，直到 b 树元数据超出你的缓存并且最终执行大量 io，在这种情况下散列更好。另外，正如您所指出的，b 树插入更昂贵，如果您发现您将执行大量插入和少量读取，则哈希可能会更好，如果您发现您执行很少插入，但进行大量读取，则 b 树可能会更好会更好。

如果您真的关心性能，您可以尝试这两种方法并运行您自己的基准测试=]