Wie beansprucht Redis O (1) Zeit für Schlüsselsuche?

Question

Ich habe eine Frage - Lookup eines Schlüsselwertpaar in einem Index - sagen wir mal auf cassandra oder Postgres - ist in der Regel bei etwa O (log n)

Quelle: https://github.com/tinkerpop/blueprints/wiki/Graph-Indices.

In der Redis-Dokumentation heißt es, dass die Laufzeitkomplexität O (1) ist.

Quelle: http://redis.io/commands/get http://redis.io/commands/hget

und den Wert von mehreren Tasten immer nur linear O (n) http://redis.io/commands/hmget

Wie ist es möglich?

Answer 1

Redis ist ein In-Memory-Speicher. Es kann daher Datenstrukturen verwenden, die an den Speicher angepasst sind (was einen schnellen wahlfreien Zugriff ermöglicht).

Um Wörterbücher zu implementieren (wird für das Hauptwörterbuch verwendet, aber auch für Hash- und Set-Objekte und in Verbindung mit einer Übersprungliste für Zset-Objekte), verwenden Sie separate chaining hash tables, deren Zugriffskomplexität O (1 + n/k) ist. Dabei steht n für die Anzahl der Elemente und k für die Anzahl der Buckets.

Redis stellt sicher, dass die Anzahl der Eimer mit der Anzahl der Elemente wächst, so dass in der Praxis n/k niedrig gehalten wird. Diese Wiederhash-Aktivität wird schrittweise im Hintergrund ausgeführt. Wenn die Anzahl der Elemente signifikant ist, liegt die Komplexität nahe bei O (1) (amortisiert).

Andere Läden (Cassandra zum Beispiel) sind so konzipiert, Daten auf der Festplatte zu speichern, während die Anzahl des Random-I/O aus Leistungsgründen zu minimieren. Eine Hash-Tabelle ist dafür keine gute Datenstruktur, da sie die Lokalität der Daten nicht erzwingt (sie profitiert nicht sehr gut vom Puffer-Caching). Festplattenbasierte Speicher verwenden normalerweise B-Baum-Varianten (am häufigsten RDBMS) oder log-strukturierte Zusammenführungs (LSM) -Baumvarianten (Cassandra), die O (log n) -Komplexität aufweisen.

Also ja, bietet Redis O (1) für viele Operationen, aber es gibt eine Einschränkung: Alle Daten in den Speicher passen sollte. Es gibt keine Magie hier.