数据库查询时间比例如何随数据库大小变化？

Question

我最近在OEIS（整数序列的在线百科全书）上，试图查找一个特定的序列，我有。

现在，这个数据库是相当大的。该网站指出，如果2006版（！5岁）版本被印刷，它将占用750卷的文本。

我相信这也是谷歌必须处理的问题。但是，他们也有一个分布式系统，他们利用负载平衡。

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

换句话说，查询的时间复杂度与数据库大小有关？

编辑：为了使事情变得更具体，假设输入查询简单地查找号码如一串：

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中。因此，树木在实践中更常见。 （尽管散列并不稀罕）。

Answer 2

这取决于许多因素，包括数据库引擎实现，索引策略，查询的详细信息，可用硬件，数据库配置等。

无法回答这样的一般问题。

Answer 3

一个正确设计和实现的数据库，具有TB级的数据可能实际上胜过设计不好的小型数据库（特别是没有索引的一个数据库，以及使用性能较差的非可查询查询以及诸如相关子查询之类的东西）。这就是为什么任何期望拥有大量数据的人都需要雇用专家来处理大型数据库的数据库设计，以便在数据库规模不大的时候进行初始设计。您也可能需要投资处理该尺寸所需的设备类型。