Redis數(shù)據(jù)類型與底層數(shù)據(jù)類型關(guān)系

簡單來說，底層數(shù)據(jù)結(jié)構(gòu)一共有 6 種，分別是簡單動態(tài)字符串、雙向鏈表、壓縮列表、哈希表、跳表和整數(shù)數(shù)組。它們和數(shù)據(jù)類型的對應(yīng)關(guān)系如下圖所示：

鍵和值的結(jié)構(gòu)組織

為了實現(xiàn)從鍵到值的快速訪問，Redis 使用了一個哈希表來保存所有鍵值對。哈希桶中的元素保存的并不是值本身，而是指向具體值的指針。這也就是說，不管值是 String，還是集合類型，哈希桶中的元素都是指向它們的指針。
在下圖中，可以看到，哈希桶中的 entry 元素中保存了key和value指針，分別指向了實際的鍵和值，這樣一來，即使值是一個集合，也可以通過*value指針被查找到。

因為這個哈希表保存了所有的鍵值對，所以，我也把它稱為全局哈希表。哈希表的最大好處很明顯，就是讓我們可以用 O(1) 的時間復(fù)雜度來快速查找到鍵值對——我們只需要計算
鍵的哈希值，就可以知道它所對應(yīng)的哈希桶位置，然后就可以訪問相應(yīng)的 entry 元素。
你看，這個查找過程主要依賴于哈希計算，和數(shù)據(jù)量的多少并沒有直接關(guān)系。也就是說，不管哈希表里有 10 萬個鍵還是 100 萬個鍵，我們只需要一次計算就能找到相應(yīng)的鍵。
但是，如果你只是了解了哈希表的 O(1) 復(fù)雜度和快速查找特性，那么，當(dāng)你往 Redis 中寫入大量數(shù)據(jù)后，就可能發(fā)現(xiàn)操作有時候會突然變慢了。這其實是因為你忽略了一個潛在的風(fēng)險點，那就是哈希表的沖突問題和 rehash 可能帶來的操作阻塞。

為什么哈希表操作變慢了？

當(dāng)你往哈希表中寫入更多數(shù)據(jù)時，哈希沖突是不可避免的問題。這里的哈希沖突，也就是指，兩個 key 的哈希值和哈希桶計算對應(yīng)關(guān)系時，正好落在了同一個哈希桶中。
畢竟，哈希桶的個數(shù)通常要少于 key 的數(shù)量，這也就是說難免會有一些 key 的哈希值對應(yīng)到了同一個哈希桶中。
Redis 解決哈希沖突的方式，就是鏈?zhǔn)焦！ｆ準(zhǔn)焦Ｒ埠苋菀桌斫?#xff0c;就是指同一個哈希桶中的多個元素用一個鏈表來保存，它們之間依次用指針連接。
如下圖所示：entry1、entry2 和 entry3 都需要保存在哈希桶 3 中，導(dǎo)致了哈希沖突。此時，entry1 元素會通過一個next指針指向 entry2，同樣，entry2 也會通過next指針指向 entry3。這樣一來，即使哈希桶 3 中的元素有 100 個，我們也可以通過 entry 元素中的指針，把它們連起來。這就形成了一個鏈表，也叫作哈希沖突鏈。

但是，這里依然存在一個問題，哈希沖突鏈上的元素只能通過指針逐一查找再操作。如果 哈希表里寫入的數(shù)據(jù)越來越多，哈希沖突可能也會越來越多，這就會導(dǎo)致某些哈希沖突鏈 過長，進而導(dǎo)致這個鏈上的元素查找耗時長，效率降低。對于追求“快”的 Redis 來說， 這是不太能接受的。
所以，Redis 會對哈希表做 rehash 操作。rehash 也就是增加現(xiàn)有的哈希桶數(shù)量，讓逐漸增多的 entry 元素能在更多的桶之間分散保存，減少單個桶中的元素數(shù)量，從而減少單個桶中的沖突。那具體怎么做呢？
其實，為了使 rehash 操作更高效，Redis 默認使用了兩個全局哈希表：哈希表 1 和哈希表 2。一開始，當(dāng)你剛插入數(shù)據(jù)時，默認使用哈希表 1，此時的哈希表 2 并沒有被分配空間。隨著數(shù)據(jù)逐步增多，Redis 開始執(zhí)行 rehash，這個過程分為三步：

• 給哈希表 2 分配更大的空間，例如是當(dāng)前哈希表 1 大小的兩倍；
• 把哈希表 1 中的數(shù)據(jù)重新映射并拷貝到哈希表 2 中；
• 釋放哈希表 1 的空間。

到此，我們就可以從哈希表 1 切換到哈希表 2，用增大的哈希表 2 保存更多數(shù)據(jù)，而原來的哈希表 1 留作下一次 rehash 擴容備用。
這個過程看似簡單，但是第二步涉及大量的數(shù)據(jù)拷貝，如果一次性把哈希表 1 中的數(shù)據(jù)都遷移完，會造成 Redis 線程阻塞，無法服務(wù)其他請求。此時，Redis 就無法快速訪問數(shù)據(jù)了。為了避免這個問題，Redis 采用了漸進式 rehash。
簡單來說就是在第二步拷貝數(shù)據(jù)時，Redis 仍然正常處理客戶端請求，每處理一個請求時，從哈希表 1 中的第一個索引位置開始，順帶著將這個索引位置上的所有 entries 拷貝到哈希表 2 中；等處理下一個請求時，再順帶拷貝哈希表 1 中的下一個索引位置的entries。如下圖所示：

有哪些底層數(shù)據(jù)結(jié)構(gòu)？

集合類型的底層數(shù)據(jù)結(jié)構(gòu)主要有 5 種：整數(shù)數(shù)組、雙向表、哈希表、壓縮列表和跳表。
其中，哈希表的操作特點我們剛剛已經(jīng)學(xué)過了；整數(shù)數(shù)組和雙向鏈表也很常見，它們的操作特征都是順序讀寫，也就是通過數(shù)組下標(biāo)或者鏈表的指針逐個元素訪問，操作復(fù)雜度基本是 O(N)，操作效率比較低；壓縮列表和跳表我們平時接觸得可能不多，但它們也是Redis 重要的數(shù)據(jù)結(jié)構(gòu)，所以我來重點解釋一下。
壓縮列表實際上類似于一個數(shù)組，數(shù)組中的每一個元素都應(yīng)保存一個數(shù)據(jù)。和數(shù)組不同的是，壓縮列表在表頭有三個字段 zlbytes、zltail 和 zllen，分別表示列表長度、列表尾的偏移量和列表中的 entry 個數(shù)；壓縮列表在表尾還有一個 zlend，表示列表結(jié)束。

在壓縮列表中，如果我們要查找定位第一個元素和最后一個元素，可以通過表頭三個字段的長度直接定位，復(fù)雜度是 O(1)。而查找其他元素時，就沒有這么高效了，只能逐個查找，此時的復(fù)雜度就是 O(N) 了。
我們再來看下跳表，有序鏈表只能逐一查找元素，導(dǎo)致操作起來非常緩慢，于是就出現(xiàn)了跳表。具體來說，跳表在鏈表的基礎(chǔ)上，增加了多級索引，通過索引位置的幾個跳轉(zhuǎn)，實現(xiàn)數(shù)據(jù)的快速定位，如下圖所示：

如果我們要在鏈表中查找 33 這個元素，只能從頭開始遍歷鏈表，查找 6 次，直到找到 33為止。此時，復(fù)雜度是 O(N)，查找效率很低。
為了提高查找速度，我們來增加一級索引：從第一個元素開始，每兩個元素選一個出來作為索引。這些索引再通過指針指向原始的鏈表。例如，從前兩個元素中抽取元素 1 作為一級索引，從第三、四個元素中抽取元素 11 作為一級索引。此時，我們只需要 4 次查找就能定位到元素 33 了。
如果我們還想再快，可以再增加二級索引：從一級索引中再抽取部分元素作為二級索引。例如，從一級索引中抽取 1、27、100 作為二級索引，二級索引指向一級索引。這樣，我們只需要 3 次查找，就能定位到元素 33 了。可以看到，這個查找過程就是在多級索引上跳來跳去，最后定位到元素。這也正好符合“跳”表的叫法。
當(dāng)數(shù)據(jù)量很大時，跳表的查找復(fù)雜度就是 O(logN)。
好了，我們現(xiàn)在可以按照查找的時間復(fù)雜度給這些數(shù)據(jù)結(jié)構(gòu)分下類了：

不同操作的復(fù)雜度

我總結(jié)了一個“四句口訣”，希望能幫助你快速記住集合常見操作的復(fù)雜度。這樣你在使用過程中，就可以提前規(guī)避高復(fù)雜度操作了。

• 單元素操作是基礎(chǔ)；
• 范圍操作非常耗時；
• 統(tǒng)計操作通常高效；
• 例外情況只有幾個。

第一，單元素操作，是指每一種集合類型對單個數(shù)據(jù)實現(xiàn)的增刪改查操作。例如，Hash 類型的 HGET、HSET 和HDEL，Set 類型的 SADD、SREM、SRANDMEMBER 等。這些作的復(fù)雜度由集合采用的數(shù)據(jù)結(jié)構(gòu)決定，例如HGET、
HSET 和 HDEL 是對哈希表做操作，所以它們的復(fù)雜度都是 O(1)；Set 類型用哈希表作為底層數(shù)據(jù)結(jié)構(gòu)時，它的SADD、SREM、SRANDMEMBER 復(fù)雜度也是 O(1)。
這里，有個地方你需要注意一下，集合類型支持同時對多個元素進行增刪改查，例如 Hash類型的 HMGET 和 HMSET，Set 類型的 SADD 也支持同時增加多個元素。此時，這些操作的復(fù)雜度，就是由單個元素操作復(fù)雜度和元素個數(shù)決定的。例如，HMSET 增加 M 個元素時，復(fù)雜度就從 O(1) 變成 O(M) 了。
第二，范圍操作，是指集合類型中的遍歷操作，可以返回集合中的所有數(shù)據(jù)，比如 Hash類型的 HGETALL 和 Set 類型的 SMEMBERS，或者返回一個范圍內(nèi)的部分數(shù)據(jù)，比如 List類型的 LRANGE 和 ZSet 類型的 ZRANGE。這類操作的復(fù)雜度一般是 O(N)，比較耗時，我們應(yīng)該盡量避免。
不過，Redis 從 2.8 版本開始提供了 SCAN 系列操作（包括 HSCAN，SSCAN 和ZSCAN），這類操作實現(xiàn)了漸進式遍歷，每次只返回有限數(shù)量的數(shù)據(jù)。這樣一來，相比于
HGETALL、SMEMBERS 這類操作來說，就避免了一次性返回所有元素而導(dǎo)致的 Redis 阻塞。
第三，統(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)快速操作。

總結(jié)

以上是生活随笔為你收集整理的01丨数据结构：快速的Redis有哪些慢操作的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。