CODEWITHSUNDEEP
redis
shengbin_xu
shengbin_xu

Reputation: 168

what is the Time complexity of redis del command?

the offical document about del command:

Time complexity: O(N) where N is the number of keys that will be removed. When a key to remove holds a value other than a string, the individual complexity for this key is O(M) where M is the number of elements in the list, set, sorted set or hash. Removing a single key that holds a string value is O(1).

why? I think even if the key refers to a complex type, the Time complexity of del should always is O(1) 。 the redis db find the hash value of the key and remove it，which operation Time complexity is O(1)。

in the redis souce code,the implement of "del command" is as follow:

void delCommand(client *c) {
    int deleted = 0, j;

    for (j = 1; j < c->argc; j++) {
        expireIfNeeded(c->db,c->argv[j]);
        if (dbDelete(c->db,c->argv[j])) {
            signalModifiedKey(c->db,c->argv[j]);
            notifyKeyspaceEvent(NOTIFY_GENERIC,
                "del",c->argv[j],c->db->id);
            server.dirty++;
            deleted++;
        }
    }
    addReplyLongLong(c,deleted);
}

as above,deleting 1 key should has a complexity of O(1),regardless of a complex type。

Upvotes: 1

Views: 2970

Answers (1)

japrescott
japrescott

Reputation: 5015

deleting 1 key has a complexity of O(1). deleting 5keys, has a complexity of O(5) (as it says in the documentation -> O(N) ). But if the key refers to a complex type, like a list, Redis needs to delete everything within that list as well, not just the key refering to the list. If it would just delete the key, the list would still be using memory.

a list, hash, set, etc. in Redis are not implemented as a "string" that is deserialized, modified, serialized and stored again (which would be not performant and use more memory), but as a highly optimized structure. To gain the performance and small memory print Redis provides, there is this "tradeoff" that a delete operation isnt always O(N), but O(N*M).

Upvotes: 4

Related Questions