How does redis claim O(1) time for key lookup?

Question

I have a question - lookup of a key value pair in an index - let's say on cassandra or postgres - is typically at around O(logn)

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

In the redis documentation it states that runtime complexity is O(1).

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

And getting the value of multiple keys is only linear O(m) where m is the number of keys retrieved http://redis.io/commands/hmget

How is it possible?

question from:https://stackoverflow.com/questions/15216897/how-does-redis-claim-o1-time-for-key-lookup

Answer 1

Redis is an in-memory store. It can therefore use data structures which are adapted to memory storage (allowing for fast random access).

To implement dictionaries (used for the main dictionary, but also for hash and set objects, and in conjunction with a skip list for zset objects), Redis use separate chaining hash tables, whose access complexity is O(1+n/k) where n is the number of items and k the number of buckets.

Redis makes sure the number of buckets grows with the number of items so that in practice n/k is kept low. This rehashing activity is done incrementally in background. When the number of items is significant, the complexity is close to O(1) (amortized).

Other stores (Cassandra for instance) are designed to store data on disk while minimizing the number of random I/Os for performance reasons. A hash table is not a good data structure for this, because it does not enforce the locality of the data (it does not benefit from buffer caching very well). So disk based stores usually use B-tree variants (most RDBMS) or log-structured merge (LSM) trees variants (Cassandra), which have O(log n) complexity.

So yes, Redis offers O(1) for many operations, but there is a constraint: all data should fit in memory. There is no magic here.