hkeys - ¿Cómo redis reclama O(1) tiempo para la búsqueda de claves?

redis table

Question

Tengo una pregunta: la búsqueda de un par de valores clave en un índice, digamos en cassandra o postgres, generalmente está alrededor de O (logn)

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

En la documentación de redis indica que la complejidad del tiempo de ejecución es O (1).

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

Y obtener el valor de varias claves es solo O (m) lineal, donde m es el número de claves recuperadas http://redis.io/commands/hmget

¿Como es posible?

Answer 1

Redis es una tienda en memoria. Por lo tanto, puede utilizar estructuras de datos que están adaptadas al almacenamiento de memoria (lo que permite un acceso aleatorio rápido).

Para implementar diccionarios (utilizados para el diccionario principal, pero también para hash y para establecer objetos, y junto con una lista de omisión para objetos zset), Redis usa tablas hash de encadenamiento separadas , cuya complejidad de acceso es O (1 + n / k) donde n es el número de elementos y k el número de cubos.

Redis se asegura de que la cantidad de cubos crezca con la cantidad de elementos para que, en la práctica, n / k se mantenga bajo. Esta actividad de repasar se realiza de forma incremental en el fondo. Cuando el número de elementos es significativo, la complejidad es cercana a O (1) (amortizada).

Otras tiendas (por ejemplo, Cassandra) están diseñadas para almacenar datos en el disco a la vez que minimizan el número de E / S aleatorias por motivos de rendimiento. Una tabla hash no es una buena estructura de datos para esto, porque no aplica la localidad de los datos (no se beneficia del almacenamiento en caché del búfer). Por lo tanto, los almacenes basados ​​en disco usualmente utilizan variantes de árbol B (la mayoría de RDBMS) o variantes de árbol de fusión estructurada de registro (LSM) (Cassandra), que tienen una complejidad de O (registro n).

Entonces, sí, Redis ofrece O (1) para muchas operaciones, pero hay una restricción: todos los datos deben caber en la memoria. No hay magia aquí.