Redis, anahtar arama için O (1) zamanını nasıl talep ediyor?

Question

Bir sorum var - bir dizin anahtar değer çifti arama - en cassandra veya Postgres'e üzerinde diyelim - tipik etrafında O (logn)

kaynak: https://github.com/tinkerpop/blueprints/wiki/Graph-Indices. Redis belgelerinde çalışma zamanı karmaşıklığının O (1) olduğunu belirtmektedir.

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

Ve birden anahtarlarının değeri elde yalnızca doğrusal O (n) http://redis.io/commands/hmget

nasıl mümkün olabilir mi?

Answer 1

Redis bir bellek deposudur. Bu nedenle, bellek depolamaya uyarlanmış veri yapılarını kullanabilir (hızlı rastgele erişime izin verir).

Sözlükleri uygulamak için (ana sözdizimi için kullanılan, ancak karma ve set nesneleri için ve zset nesneleri için bir atlama listesiyle birlikte kullanılan), Redis, erişim karmaşıklığı O (1 + n/k) olan separate chaining hash tables kullanın. n, öğelerin sayısı ve k sayısıdır.

Redis, pratikte n/k'nin düşük tutulması için, küme sayısının öğe sayısıyla büyüdüğünden emin olur. Bu rehashing aktivitesi artımlı olarak arka planda yapılır. Maddelerin sayısı önemli olduğunda, karmaşıklık O (1) 'e yakındır (itfa edilmiş).

Diğer mağazalar (örneğin Cassandra), disk üzerindeki verileri saklamak için performans nedenleriyle rasgele I/O'sayısını en aza indirecek şekilde tasarlanmıştır. Bir karma tablosu, bunun için iyi bir veri yapısı değildir, çünkü verilerin yerini etkilemez (arabelleğe alma işleminden çok iyi yararlanamaz). Bu nedenle, disk tabanlı depolar genellikle O (log n) karmaşıklığı olan B-tree varyantlarını (çoğu RDBMS) veya log-structured birleştirme (LSM) ağaçları varyantlarını (Cassandra) kullanır.

Evet, Redis birçok işlem için O (1) sunar, ancak bir kısıtlama vardır: tüm veriler belleğe sığmalıdır. Burada sihir yok.