Berkeleydb-B树与哈希表 [英] Berkeleydb - B-Tree versus Hash Table

问题描述

我试图了解在使用BerkeleyDB时，什么会驱动访问方法的选择:B树与HashTable. Hashtable提供O(1)查找，但是插入操作很昂贵(使用线性/可扩展哈希，我们可以为插入操作分摊O(1)).但是B树提供了日志N(基于B)的查找和插入时间. B树还可以支持范围查询，并允许按排序顺序进行访问.

I am trying to understand what should drive the choice of the access method while using a BerkeleyDB : B-Tree versus HashTable. A Hashtable provides O(1) lookup but inserts are expensive (using Linear/Extensible hashing we get amortized O(1) for insert). But B-Trees provide log N (base B) lookup and insert times. A B-Tree can also support range queries and allow access in sorted order.

1. 除了这些考虑因素之外，还应考虑哪些因素?
2. 如果我不需要支持范围查询，是否可以使用哈希表访问方法?

推荐答案

当您的数据集变得非常大时，B树仍然更好，因为大多数内部元数据可能仍适合缓存.从本质上说，哈希(数据的均匀随机分布)本质上是不友好的缓存.也就是说，一旦数据集的总大小超过了工作内存大小，哈希性能就会下降，而B树性能会正常下降(实际上是对数的).

When your data sets get very large, B-trees are still better because the majority of the internal metadata may still fit in cache. Hashes, by their nature (uniform random distribution of data) are inherently cache-unfriendly. I.e., once the total size of the data set exceeds the working memory size, hash performance drops off a cliff while B-tree performance degrades gracefully (logarithmically, actually).

这篇关于Berkeleydb-B树与哈希表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！