In che modo i redis richiedono il tempo O (1) per la ricerca dei tasti?

Question

Ho una domanda - ricerca di una coppia chiave-valore in un indice - diciamo su Cassandra o Postgres - è in genere intorno alle O (log n)

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

Nella documentazione Redis si afferma che il runtime complessità è O (1).

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

e ottenere il valore più chiavi è solo O lineare (n) http://redis.io/commands/hmget

Come è possibile?

Answer 1

Redis è un negozio in-memory. Può quindi utilizzare strutture dati adattate all'archiviazione della memoria (che consente un accesso casuale rapido).

Per implementare dizionari (utilizzati per il dizionario principale, ma anche per hash e set oggetti e in combinazione con un elenco di salto per oggetti zset), Redis usa separate chaining hash tables, la cui complessità di accesso è O (1 + n/k) dove n è il numero di articoli e k il numero di secchi.

Redis si assicura il numero di contenitori aumenta con il numero di elementi in modo che in pratica n/k è mantenuto basso. Questa attività di rilubrificazione viene eseguita in modo incrementale in background. Quando il numero di elementi è significativo, la complessità è vicina a O (1) (ammortizzato).

Altri negozi (Cassandra per esempio) sono progettati per memorizzare dati su disco riducendo al minimo il numero di I/O casuali per motivi di prestazioni. Una tabella hash non è una buona struttura dati per questo, perché non applica la localizzazione dei dati (non beneficia molto bene della memorizzazione nella cache del buffer). Pertanto, i negozi basati su disco utilizzano solitamente varianti di varianti B-tree (la maggior parte degli RDBMS) o log-strutturate (LSM) (Cassandra), che hanno complessità O (log n).

Quindi sì, Redis offre O (1) per molte operazioni, ma c'è un vincolo: tutti i dati dovrebbero rientrare nella memoria. Non c'è magia qui.