Redis“快”的重要表現(xiàn)：它接收到一個鍵值對操作后，能以微秒級別的速度找到數(shù)據(jù)，并快速完成操作。能夠這么優(yōu)秀的原因一方面，這是因為它是內(nèi)存數(shù)據(jù)庫，所有操作都在內(nèi)存上完成，內(nèi)存的訪問速度本身就很快。另一方面，這要歸功于它的數(shù)據(jù)結(jié)構(gòu)。
底層數(shù)據(jù)結(jié)構(gòu)一共有 6 種，分別是簡單動態(tài)字符串、雙向鏈表、壓縮列表、哈希表、跳表和整數(shù)數(shù)組。
String 類型的底層實現(xiàn)只有一種數(shù)據(jù)結(jié)構(gòu)，也就是簡單動態(tài)字符串。而 List、Hash、Set 和 Sorted Set 這四種數(shù)據(jù)類型，都有兩種底層實現(xiàn)結(jié)構(gòu)。通常情況下，我們會把這四種類型稱為集合類型，它們的特點是一個鍵對應(yīng)了一個集合的數(shù)據(jù)。
鍵和值用什么結(jié)構(gòu)組織？
為了實現(xiàn)從鍵到值的快速訪問，Redis 使用了一個哈希表來保存所有鍵值對。
一個哈希表，其實就是一個數(shù)組，數(shù)組的每個元素稱為一個哈希桶。所以，我們常說，一個哈希表是由多個哈希桶組成的，每個哈希桶中保存了鍵值對數(shù)據(jù)。哈希桶中的元素保存的并不是值本身，而是指向具體值的指針。
這個哈希表保存了所有的鍵值對，所以，我也把它稱為全局哈希表。
注意： Redis 中寫入大量數(shù)據(jù)后，可能發(fā)現(xiàn)操作有時候會突然變慢了。哈希表的沖突問題和 rehash 可能帶來的操作阻塞。
為什么哈希表操作變慢了？
哈希沖突是不可避免的問題。這里的哈希沖突，也就是指，兩個 key 的哈希值和哈希桶計算對應(yīng)關(guān)系時，正好落在了同一個哈希桶中。
Redis 解決哈希沖突的方式，就是鏈?zhǔn)焦?。鏈?zhǔn)焦Ｒ埠苋菀桌斫猓?strong>就是指同一個哈希桶中的多個元素用一個鏈表來保存，它們之間依次用指針連接。如圖所示
但是，這樣的話，哈希沖突鏈上的元素只能通過指針逐一查找再操作，隨著數(shù)量越來越多，性能將會越來越差，為了解決這個問題，Redis 會對哈希表做 rehash 操作。
為了使 rehash 操作更高效，Redis 默認(rèn)使用了兩個全局哈希表：哈希表 1 和哈希表 2。一開始，當(dāng)你剛插入數(shù)據(jù)時，默認(rèn)使用哈希表 1，此時的哈希表 2 并沒有被分配空間。隨著數(shù)據(jù)逐步增多，Redis 開始執(zhí)行 rehash，這個過程分為三步：
給哈希表 2 分配更大的空間，例如是當(dāng)前哈希表 1 大小的兩倍；
把哈希表 1 中的數(shù)據(jù)重新映射并拷貝到哈希表 2 中；
釋放哈希表 1 的空間。
但是這個過程設(shè)計了大量的數(shù)據(jù)拷貝，如果一次性把哈希表 1 中的數(shù)據(jù)都遷移完，會造成 Redis 線程阻塞。為了避免這個問題，Redis 采用了漸進(jìn)式 rehash。主要是將上述第二步的步驟修改為：
- Redis 仍然正常處理客戶端請求，每處理一個請求時，從哈希表 1 中的第一個索引位置開始，順帶著將這個索引位置上的所有 entries 拷貝到哈希表 2 中；等處理下一個請求時，再順帶拷貝哈希表 1 中的下一個索引位置的 entries。
不同操作的復(fù)雜度
單元素操作是基礎(chǔ)；
范圍操作非常耗時；
統(tǒng)計操作通常高效；
例外情況只有幾個。
第一，單元素操作，是指每一種集合類型對單個數(shù)據(jù)實現(xiàn)的增刪改查操作。這些操作的復(fù)雜度由集合采用的數(shù)據(jù)結(jié)構(gòu)決定，例如，HGET、HSET 和 HDEL 是對哈希表做操作，所以它們的復(fù)雜度都是 O(1)；Set 類型用哈希表作為底層數(shù)據(jù)結(jié)構(gòu)時，它的 SADD、SREM、SRANDMEMBER 復(fù)雜度也是 O(1)。
第二，范圍操作，是指集合類型中的遍歷操作，可以返回集合中的所有數(shù)據(jù)，比如 Hash 類型的 HGETALL 和 Set 類型的 SMEMBERS，或者返回一個范圍內(nèi)的部分?jǐn)?shù)據(jù)，比如 List 類型的 LRANGE 和 ZSet 類型的 ZRANGE。這類操作的復(fù)雜度一般是 O(N)，比較耗時，我們應(yīng)該盡量避免。
第三，統(tǒng)計操作，是指集合類型對集合中所有元素個數(shù)的記錄，例如 LLEN 和 SCARD。這類操作復(fù)雜度只有 O(1)，這是因為當(dāng)集合類型采用壓縮列表、雙向鏈表、整數(shù)數(shù)組這些數(shù)據(jù)結(jié)構(gòu)時，這些結(jié)構(gòu)中專門記錄了元素的個數(shù)統(tǒng)計，因此可以高效地完成相關(guān)操作。
第四，例外情況，是指某些數(shù)據(jù)結(jié)構(gòu)的特殊記錄，例如壓縮列表和雙向鏈表都會記錄表頭和表尾的偏移量。這樣一來，對于 List 類型的 LPOP、RPOP、LPUSH、RPUSH 這四個操作來說，它們是在列表的頭尾增刪元素，這就可以通過偏移量直接定位，所以它們的復(fù)雜度也只有 O(1)，可以實現(xiàn)快速操作。
