我最近在 OEIS（整数序列在线百科全书）上，试图查找我拥有的特定序列。
现在，这个数据库相当大。该网站称，如果 2006 年（！5 年前）版本印刷，它将占据 750 卷文本。
我确信这也是 Google 必须处理的同一类问题。但是，他们也有一个分布式系统，可以利用负载平衡。
然而，忽略负载平衡，与数据库大小相比，执行查询需要多少时间？
或者换句话说，查询相对于数据库大小的时间复杂度是多少？
编辑：为了使事情更具体，假设输入查询只是查找一串数字，例如：
1, 4, 9, 16, 25, 36, 49
它在很大程度上取决于查询、数据库的结构、争用等。但一般来说，大多数数据库都会找到一种使用索引的方法，并且该索引将是某种树结构（参见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 中保存得更好。因此，树在实践中更为常见。（尽管散列并不罕见。）
这取决于许多因素，包括数据库引擎实现、索引策略、查询细节、可用硬件、数据库配置等。
没有办法回答这样一个笼统的问题。
具有 TB 级数据的正确设计和实现的数据库实际上可能胜过设计不佳的小型数据库（特别是没有索引的数据库和使用性能不佳的非 sargable 查询和诸如相关子查询之类的东西的数据库）。这就是为什么任何希望拥有大量数据的人都需要聘请大型数据库的数据库设计专家来进行初始设计，而不是在数据库很大时进行。您可能还需要购买处理尺寸所需的设备类型。