data structures - Why the time complexity of insertion in a redis SET is O(n)? - Stack Overflow
Complexity is not O(n) but O(N) for N members added. Concretely, it means that you can consider that each insertion operation is done in constant time - O(1) - which is only asymptotically true.
Hereunder, we suppose that n is the number of items in the set.
To perform a SADD operation Redis has to first lookup the object representing the set (hash lookup - complexity O(1)), and then try to add the item in the object itself.
The set can be represented in memory as an intset or a hash table.
If the object is a intset (i.e. a sorted vector of integers), it will perform a binary search to search for the position of the item - O(log n) and then eventually, insert the item - O(n) - however this is only for small values of n. The set-max-intset-entries must be chosen so that the whole object fits in the CPU caches for optimal performance.
If the object is a hash table, then Redis will have to perform a lookup and add the item if needed - complexity is O(1).
Because a SADD command can add N items, the resulting asymptotic complexity is O(N).
Read full article from data structures - Why the time complexity of insertion in a redis SET is O(n)? - Stack Overflow
No comments:
Post a Comment