什麼是redis del命令的時間複雜性？

時間複雜度：O（N），其中N是將被刪除的鍵的數目。當一個要刪除的鍵持有一個字符串以外的值時，這個鍵的個體複雜度是O（M），其中M是列表中元素的數量，集合，排序集合或散列值。刪除包含字符串值的單個鍵是O（1）。

爲什麼？我認爲，即使密鑰指的是複雜類型，del的時間複雜度應該總是爲O（1），redis db找到密鑰的哈希值並將其除去，其中時間複雜度爲O（1）。

在redis的烴源代碼，「刪除命令」的工具是如下：

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); 
}

如上，刪除1個鍵應該具有複雜度O（1），而不管複雜類型的

。

來源

2017-03-22 shengbin_xu

這個問題很好，它的真正意思是'爲什麼DEL的複雜度被列爲O（n），當密鑰是一個複雜的數據結構時「我也希望它是O（1），嘆氣 – user3175580

刪除1個密鑰的複雜度爲O（1）。刪除5個鍵，複雜度爲O（5）（正如它在文檔 - > O（N）中所述）。但是，如果密鑰引用複雜類型（如列表），則Redis需要刪除該列表中的所有內容，而不僅僅是引用列表的密鑰。如果它只是刪除密鑰，該列表仍將使用內存。

Redis中的列表，哈希，集合等不是作爲反序列化，修改，序列化和再次存儲的「字符串」實現的（這不是高性能且使用更多內存），而是作爲高度優化結構體。爲了獲得Redis提供的性能和小內存打印，存在這種「權衡」，即刪除操作不總是O（N），而是O（N * M）。

來源

2017-03-22 12:23:51 japrescott

我的看法是：每個redis對象都有一個refcount屬性，當一個鍵是del時，值對象的refcount減1，然後當refcount爲0時，值內存將自動釋放。你確定redis需要刪除列表中的所有內容嗎？並且從redis源代碼中，我沒有找到del列表中的所有操作，謝謝！ –

對不起，當我繼續閱讀redis源代碼時，我意識到，當列表鍵是del時，Redis確實需要刪除該列表中的所有內容。非常感謝！ –

什麼是redis del命令的時間複雜性？

回答

相關問題