私は最近、OEIS (整数シーケンスのオンライン百科事典) に参加していて、自分が持っていた特定のシーケンスを調べようとしていました。
さて、このデータベースはかなり大きいです。ウェブサイトによると、2006 年版 (! 5 年前) が印刷された場合、750 巻のテキストを占めることになります。
これは、Google が対処しなければならないのと同じ種類の問題だと確信しています。ただし、負荷分散を利用する分散システムもあります。
ただし、負荷分散を無視すると、データベースのサイズと比較して、クエリを実行するのにどれくらいの時間がかかりますか?
言い換えれば、DB サイズに対するクエリの時間計算量はどれくらいですか?
編集：物事をより具体的にするために、入力クエリが次のような数字の文字列を単に検索していると仮定します。
1, 4, 9, 16, 25, 36, 49
これは、クエリ、データベースの構造、競合などに大きく依存します。しかし、一般に、ほとんどのデータベースはインデックスを使用する方法を見つけます。そのインデックスは、ある種のツリー構造 ( 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 ペタバイトまでは 5 倍の割合で変化します。) また、頻繁に要求されたデータは、ツリーが RAM に保持するのに適したある種の局所性を示します。その結果、木は実際にはより一般的に見られます。(ただし、ハッシュは決して珍しいものではありません。)
これは、データベース エンジンの実装、インデックス作成戦略、クエリの詳細、利用可能なハードウェア、データベース構成など、さまざまな要因によって異なります。
そのような一般的な質問に答える方法はありません。
適切に設計され、実装されたテラバイトのデータを持つデータベースは、実際には、設計が不適切な小さなデータベースよりもパフォーマンスが優れている可能性があります (特に、インデックスが作成されていないデータベースや、パフォーマンスの悪い sargable でないクエリや相関サブクエリなどを使用するデータベース)。これが、大量のデータを期待する人が、大規模データベースのデータベース設計の専門家を雇って、データベースが大規模になってからでなく初期設計を行う必要がある理由です。また、サイズを処理するために必要な種類の機器にも投資する必要がある場合があります。