質問があります-インデックス内のキーと値のペアのルックアップ-たとえばcassandraまたはpostgresで言いましょう-通常はO(logn)前後です
ソース: https://github.com/tinkerpop/blueprints/wiki/Graph-Indices .
redis のドキュメントでは、ランタイムの複雑さは O(1) であると記載されています。
ソース: http://redis.io/commands/get http://redis.io/commands/hget
また、複数のキーの値を取得することは、線形 O(m) のみです。ここで、m は取得したキーの数です http://redis.io/commands/hmget
それはどのように可能ですか？
Redis はインメモリ ストアです。したがって、メモリ ストレージに適合したデータ構造を使用できます (高速ランダム アクセスが可能)。
ディクショナリを実装するために (メイン ディクショナリだけでなく、ハッシュ オブジェクトとセット オブジェクトにも使用され、zset オブジェクトのスキップ リストと組み合わせて使用されます)、Redis は、アクセスの複雑さが O(1+n/k) である個別のチェーン ハッシュ テーブルを使用します。 n はアイテムの数、k はバケットの数です。
Redis は、実際には n/k が低く保たれるように、アイテムの数に応じてバケットの数が確実に増えるようにします。この再ハッシュ アクティビティは、バックグラウンドで段階的に実行されます。アイテムの数が多い場合、複雑さは O(1) (償却) に近くなります。
他のストア (Cassandra など) は、パフォーマンス上の理由からランダム I/O の数を最小限に抑えながら、データをディスクに格納するように設計されています。ハッシュ テーブルは、データの局所性を強制しないため、これには適したデータ構造ではありません (バッファ キャッシングのメリットはあまりありません)。そのため、ディスク ベースのストアでは通常、O(log n) の複雑さを持つ B ツリー バリアント (ほとんどの RDBMS) またはログ構造マージ (LSM) ツリー バリアント (Cassandra) が使用されます。
そうです、Redis は多くの操作に対して O(1) を提供しますが、制約があります: すべてのデータがメモリに収まる必要があります。ここには魔法はありません。