database - 数据库查询时间如何随数据库大小变化？

Question

我最近在使用 OEIS(整数序列在线百科全书)，试图查找我拥有的特定序列。

现在，这个数据库相当大。该网站表示，如果打印 2006 年(!5 岁)版本，将占用 750 卷文本。

我确信这也是 Google 必须处理的同类问题。但是，他们也有一个分布式系统，可以利用负载平衡。

然而，忽略负载平衡，与数据库大小相比，执行查询需要多少时间？

或者换句话说，关于数据库大小的查询的时间复杂度是多少？

编辑:为了使事情更具体，假设输入查询只是查找一串数字，例如:

1, 4, 9, 16, 25, 36, 49

Answer 1

这在很大程度上取决于查询、数据库结构、争用等。但通常大多数数据库都会找到一种使用索引的方法，并且该索引要么是某种树结构(参见 http://en.wikipedia.org/wiki/B-tree 的一个选项)，在这种情况下访问时间与 log(n) 成正比，或者是哈希，在这种情况下访问时间平均与 O(1) 成正比(请参阅 http://en.wikipedia.org/wiki/Hash_function#Hash_tables 了解它们如何工作的解释)。

所以答案通常是 O(1) 或 O(log(n))，具体取决于所使用的数据结构类型。

这可能会让你想知道为什么我们不总是使用散列函数。有多种原因。哈希函数使得检索值范围变得困难。如果哈希函数不能很好地分配数据，则访问时间有可能变为 O(n)。哈希偶尔需要调整大小，这可能非常昂贵。并且 log(n) 增长得足够慢，您可以将其视为在所有实际数据集中相当接近常数。 (从 1000 到 1 PB，它变化了 5 倍。)而且经常主动请求的数据显示某种局部性，哪些树在 RAM 中保存得更好。因此，树木在实践中更为常见。 (尽管哈希值并不罕见。)