redis 為什么要這莫快？一個(gè)就是他是基于內(nèi)存的，另外一個(gè)就是他是他的數(shù)據(jù)結(jié)構(gòu)

說(shuō)到這兒，你肯定會(huì)說(shuō)：“這個(gè)我知道，不就是 String（字符串）、List（列表）、
Hash（哈希）、Set（集合）和 Sorted Set（有序集合）嗎？”其實(shí)，這些只是 Redis 鍵
值對(duì)中值的數(shù)據(jù)類(lèi)型，也就是數(shù)據(jù)的保存形式。而這里，我們說(shuō)的數(shù)據(jù)結(jié)構(gòu)，是要去看看
它們的底層實(shí)現(xiàn)。

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

?可以看到，String 類(lèi)型的底層實(shí)現(xiàn)只有一種數(shù)據(jù)結(jié)構(gòu)，也就是簡(jiǎn)單動(dòng)態(tài)字符串。而 List、
Hash、Set 和 Sorted Set 這四種數(shù)據(jù)類(lèi)型，都有兩種底層實(shí)現(xiàn)結(jié)構(gòu)。通常情況下，我們會(huì)
把這四種類(lèi)型稱(chēng)為集合類(lèi)型，它們的特點(diǎn)是一個(gè)鍵對(duì)應(yīng)了一個(gè)集合的數(shù)據(jù)

以上 底層的數(shù)據(jù)結(jié)構(gòu)我單寫(xiě)一篇文章

看到這里，其實(shí)有些問(wèn)題已經(jīng)值得我們?nèi)タ紤]了：

????????這些數(shù)據(jù)結(jié)構(gòu)都是值的底層實(shí)現(xiàn)，鍵和值本身之間用什么結(jié)構(gòu)組織？
????????為什么集合類(lèi)型有那么多的底層結(jié)構(gòu)，它們都是怎么組織數(shù)據(jù)的，都很快嗎？
????????什么是簡(jiǎn)單動(dòng)態(tài)字符串，和常用的字符串是一回事嗎？

接下來(lái)，我就和你聊聊前兩個(gè)問(wèn)題。這樣，你不僅可以知道 Redis“快”的基本原理，還
可以借此理解 Redis 中有哪些潛在的“慢操作”，最大化 Redis 的性能優(yōu)勢(shì)。

鍵和值用什么結(jié)構(gòu)組織？

了實(shí)現(xiàn)從鍵到值的快速訪問(wèn)，Redis 使用了一個(gè)哈希表來(lái)保存所有鍵值對(duì)。

一個(gè)哈希表，其實(shí)就是一個(gè)數(shù)組，數(shù)組的每個(gè)元素稱(chēng)為一個(gè)哈希桶。所以，我們常說(shuō)，一
個(gè)哈希表是由多個(gè)哈希桶組成的，每個(gè)哈希桶中保存了鍵值對(duì)數(shù)據(jù)。

看到這里，你可能會(huì)問(wèn)了：“如果值是集合類(lèi)型的話，作為數(shù)組元素的哈希桶怎么來(lái)保存
呢？”其實(shí)，哈希桶中的元素保存的并不是值本身，而是指向具體值的指針。這也就是
說(shuō)，不管值是 String，還是集合類(lèi)型，哈希桶中的元素都是指向它們的指針。

在下圖中，可以看到，哈希桶中的 entry 元素中保存了*key和*value指針，分別指向了
實(shí)際的鍵和值，這樣一來(lái)，即使值是一個(gè)集合，也可以通過(guò)*value指針被查找到。

?因?yàn)檫@個(gè)哈希表保存了所有的鍵值對(duì)，所以，我也把它稱(chēng)為全局哈希表。哈希表的最大好
處很明顯，就是讓我們可以用 O(1) 的時(shí)間復(fù)雜度來(lái)快速查找到鍵值對(duì)——我們只需要計(jì)算
鍵的哈希值，就可以知道它所對(duì)應(yīng)的哈希桶位置，然后就可以訪問(wèn)相應(yīng)的 entry 元素。

你看，這個(gè)查找過(guò)程主要依賴于哈希計(jì)算，和數(shù)據(jù)量的多少并沒(méi)有直接關(guān)系。也就是說(shuō)，
不管哈希表里有 10 萬(wàn)個(gè)鍵還是 100 萬(wàn)個(gè)鍵，我們只需要一次計(jì)算就能找到相應(yīng)的鍵

但是，如果你只是了解了哈希表的 O(1) 復(fù)雜度和快速查找特性，那么，當(dāng)你往 Redis 中
寫(xiě)入大量數(shù)據(jù)后，就可能發(fā)現(xiàn)操作有時(shí)候會(huì)突然變慢了。這其實(shí)是因?yàn)槟愫雎粤艘粋€(gè)潛在
的風(fēng)險(xiǎn)點(diǎn)，那就是哈希表的沖突問(wèn)題和 rehash 可能帶來(lái)的操作阻塞。

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

當(dāng)你往哈希表中寫(xiě)入更多數(shù)據(jù)時(shí)，哈希沖突是不可避免的問(wèn)題。這里的哈希沖突，也就是
指，兩個(gè) key 的哈希值和哈希桶計(jì)算對(duì)應(yīng)關(guān)系時(shí)，正好落在了同一個(gè)哈希桶中。

畢竟，哈希桶的個(gè)數(shù)通常要少于 key 的數(shù)量，這也就是說(shuō)，難免會(huì)有一些 key 的哈希值對(duì)
應(yīng)到了同一個(gè)哈希桶中

Redis 解決哈希沖突的方式，就是鏈?zhǔn)焦?。鏈?zhǔn)焦Ｒ埠苋菀桌斫猓褪侵竿粋€(gè)哈希
桶中的多個(gè)元素用一個(gè)鏈表來(lái)保存，它們之間依次用指針連接。

如下圖所示：entry1、entry2 和 entry3 都需要保存在哈希桶 3 中，導(dǎo)致了哈希沖突。此
時(shí)，entry1 元素會(huì)通過(guò)一個(gè)*next指針指向 entry2，同樣，entry2 也會(huì)通過(guò)*next指針
指向 entry3。這樣一來(lái)，即使哈希桶 3 中的元素有 100 個(gè)，我們也可以通過(guò) entry 元素
中的指針，把它們連起來(lái)。這就形成了一個(gè)鏈表，也叫作哈希沖突鏈。

?但是，這里依然存在一個(gè)問(wèn)題，哈希沖突鏈上的元素只能通過(guò)指針逐一查找再操作。如果
哈希表里寫(xiě)入的數(shù)據(jù)越來(lái)越多，哈希沖突可能也會(huì)越來(lái)越多，這就會(huì)導(dǎo)致某些哈希沖突鏈
過(guò)長(zhǎng)，進(jìn)而導(dǎo)致這個(gè)鏈上的元素查找耗時(shí)長(zhǎng)，效率降低。對(duì)于追求“快”的 Redis 來(lái)說(shuō)，
這是不太能接受的。

所以，Redis 會(huì)對(duì)哈希表做 rehash 操作。rehash 也就是增加現(xiàn)有的哈希桶數(shù)量，讓逐漸
增多的 entry 元素能在更多的桶之間分散保存，減少單個(gè)桶中的元素?cái)?shù)量，從而減少單個(gè)
桶中的沖突。那具體怎么做呢？

其實(shí)，為了使 rehash 操作更高效，Redis 默認(rèn)使用了兩個(gè)全局哈希表：哈希表 1 和哈希
表 2。一開(kāi)始，當(dāng)你剛插入數(shù)據(jù)時(shí)，默認(rèn)使用哈希表 1，此時(shí)的哈希表 2 并沒(méi)有被分配空
間。隨著數(shù)據(jù)逐步增多，Redis 開(kāi)始執(zhí)行 rehash，這個(gè)過(guò)程分為三步：

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

到此，我們就可以從哈希表 1 切換到哈希表 2，用增大的哈希表 2 保存更多數(shù)據(jù)，而原來(lái)
的哈希表 1 留作下一次 rehash 擴(kuò)容備用.

這個(gè)過(guò)程看似簡(jiǎn)單，但是第二步涉及大量的數(shù)據(jù)拷貝，如果一次性把哈希表 1 中的數(shù)據(jù)都
遷移完，會(huì)造成 Redis 線程阻塞，無(wú)法服務(wù)其他請(qǐng)求。此時(shí)，Redis 就無(wú)法快速訪問(wèn)數(shù)據(jù)
了.

為了避免這個(gè)問(wèn)題，Redis 采用了漸進(jìn)式 rehash

簡(jiǎn)單來(lái)說(shuō)就是在第二步拷貝數(shù)據(jù)時(shí)，Redis 仍然正常處理客戶端請(qǐng)求，每處理一個(gè)請(qǐng)求
時(shí)，從哈希表 1 中的第一個(gè)索引位置開(kāi)始，順帶著將這個(gè)索引位置上的所有 entries 拷貝
到哈希表 2 中；等處理下一個(gè)請(qǐng)求時(shí)，再順帶拷貝哈希表 1 中的下一個(gè)索引位置的
entries。如下圖所示：

?這樣就巧妙地把一次性大量拷貝的開(kāi)銷(xiāo)，分?jǐn)偟搅硕啻翁幚碚?qǐng)求的過(guò)程中，避免了耗時(shí)操
作，保證了數(shù)據(jù)的快速訪問(wèn)。
好了，到這里，你應(yīng)該就能理解，Redis 的鍵和值是怎么通過(guò)哈希表組織的了。對(duì)于
String 類(lèi)型來(lái)說(shuō)，找到哈希桶就能直接增刪改查了，所以，哈希表的 O(1) 操作復(fù)雜度也就
是它的復(fù)雜度了。
但是，對(duì)于集合類(lèi)型來(lái)說(shuō)，即使找到哈希桶了，還要在集合中再進(jìn)一步操作。接下來(lái)，我
們來(lái)看集合類(lèi)型的操作效率又是怎樣的

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

集合類(lèi)型的底層數(shù)據(jù)結(jié)構(gòu)主要有 5 種：整數(shù)數(shù)組、雙向鏈表、哈
希表、壓縮列表和跳表

其中，哈希表的操作特點(diǎn)我們剛剛已經(jīng)學(xué)過(guò)了；整數(shù)數(shù)組和雙向鏈表也很常見(jiàn)，它們的操
作特征都是順序讀寫(xiě)，也就是通過(guò)數(shù)組下標(biāo)或者鏈表的指針逐個(gè)元素訪問(wèn)，操作復(fù)雜度基
本是 O(N)，操作效率比較低；壓縮列表和跳表我們平時(shí)接觸得可能不多，但它們也是
Redis 重要的數(shù)據(jù)結(jié)構(gòu)，所以我來(lái)重點(diǎn)解釋一下。

壓縮列表實(shí)際上類(lèi)似于一個(gè)數(shù)組，數(shù)組中的每一個(gè)元素都對(duì)應(yīng)保存一個(gè)數(shù)據(jù)。和數(shù)組不同
的是，壓縮列表在表頭有三個(gè)字段 zlbytes、zltail 和 zllen，分別表示列表長(zhǎng)度、列表尾的
偏移量和列表中的 entry 個(gè)數(shù)；壓縮列表在表尾還有一個(gè) zlend，表示列表結(jié)束。

?

在壓縮列表中，如果我們要查找定位第一個(gè)元素和最后一個(gè)元素，可以通過(guò)表頭三個(gè)字段
的長(zhǎng)度直接定位，復(fù)雜度是 O(1)。而查找其他元素時(shí)，就沒(méi)有這么高效了，只能逐個(gè)查
找，此時(shí)的復(fù)雜度就是 O(N) 了。

我們?cè)賮?lái)看下跳表。

有序鏈表只能逐一查找元素，導(dǎo)致操作起來(lái)非常緩慢，于是就出現(xiàn)了跳表。具體來(lái)說(shuō)，跳
表在鏈表的基礎(chǔ)上，增加了多級(jí)索引，通過(guò)索引位置的幾個(gè)跳轉(zhuǎn)，實(shí)現(xiàn)數(shù)據(jù)的快速定位，
如下圖所示

?可以看到，這個(gè)查找過(guò)程就是在多級(jí)索引上跳來(lái)跳去，最后定位到元素。這也正好符
合“跳”表的叫法。當(dāng)數(shù)據(jù)量很大時(shí)，跳表的查找復(fù)雜度就是 O(logN)。

?

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

集合類(lèi)型的操作類(lèi)型很多，有讀寫(xiě)單個(gè)集合元素的，例如 HGET、HSET，也有操作多個(gè)元
素的，例如 SADD，還有對(duì)整個(gè)集合進(jìn)行遍歷操作的，例如 SMEMBERS。這么多操作，
它們的復(fù)雜度也各不相同。而復(fù)雜度的高低又是我們選擇集合類(lèi)型的重要依據(jù)。我總結(jié)了一個(gè)“四句口訣”，希望能幫助你快速記住集合常見(jiàn)操作的復(fù)雜度。這樣你在使用過(guò)程中，就可以提前規(guī)避高復(fù)雜度操作了

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

第一，單元素操作，是指每一種集合類(lèi)型對(duì)單個(gè)數(shù)據(jù)實(shí)現(xiàn)的增刪改查操作。例如，Hash 類(lèi)
型的 HGET、HSET 和 HDEL，Set 類(lèi)型的 SADD、SREM、SRANDMEMBER 等。這些操
作的復(fù)雜度由集合采用的數(shù)據(jù)結(jié)構(gòu)決定，例如，HGET、HSET 和 HDEL 是對(duì)哈希表做操
作，所以它們的復(fù)雜度都是 O(1)；Set 類(lèi)型用哈希表作為底層數(shù)據(jù)結(jié)構(gòu)時(shí)，它的 SADD、
SREM、SRANDMEMBER 復(fù)雜度也是 O(1)。
這里，有個(gè)地方你需要注意一下，集合類(lèi)型支持同時(shí)對(duì)多個(gè)元素進(jìn)行增刪改查，例如 Hash
類(lèi)型的 HMGET 和 HMSET，Set 類(lèi)型的 SADD 也支持同時(shí)增加多個(gè)元素。此時(shí)，這些操
作的復(fù)雜度，就是由單個(gè)元素操作復(fù)雜度和元素個(gè)數(shù)決定的。例如，HMSET 增加 M 個(gè)元
素時(shí)，復(fù)雜度就從 O(1) 變成 O(M) 了。

第二，范圍操作，是指集合類(lèi)型中的遍歷操作，可以返回集合中的所有數(shù)據(jù)，比如 Hash
類(lèi)型的 HGETALL 和 Set 類(lèi)型的 SMEMBERS，或者返回一個(gè)范圍內(nèi)的部分?jǐn)?shù)據(jù)，比如 List
類(lèi)型的 LRANGE 和 ZSet 類(lèi)型的 ZRANGE。這類(lèi)操作的復(fù)雜度一般是 O(N)，比較耗時(shí)，
我們應(yīng)該盡量避免。
不過(guò)，Redis 從 2.8 版本開(kāi)始提供了 SCAN 系列操作（包括 HSCAN，SSCAN 和
ZSCAN），這類(lèi)操作實(shí)現(xiàn)了漸進(jìn)式遍歷，每次只返回有限數(shù)量的數(shù)據(jù)。這樣一來(lái)，相比于
HGETALL、SMEMBERS 這類(lèi)操作來(lái)說(shuō)，就避免了一次性返回所有元素而導(dǎo)致的 Redis 阻
塞。

第三，統(tǒng)計(jì)操作，是指集合類(lèi)型對(duì)集合中所有元素個(gè)數(shù)的記錄，例如 LLEN 和 SCARD。這
類(lèi)操作復(fù)雜度只有 O(1)，這是因?yàn)楫?dāng)集合類(lèi)型采用壓縮列表、雙向鏈表、整數(shù)數(shù)組這些數(shù)
據(jù)結(jié)構(gòu)時(shí)，這些結(jié)構(gòu)中專(zhuān)門(mén)記錄了元素的個(gè)數(shù)統(tǒng)計(jì)，因此可以高效地完成相關(guān)操作。

第四，例外情況，是指某些數(shù)據(jù)結(jié)構(gòu)的特殊記錄，例如壓縮列表和雙向鏈表都會(huì)記錄表頭
和表尾的偏移量。這樣一來(lái)，對(duì)于 List 類(lèi)型的 LPOP、RPOP、LPUSH、RPUSH 這四個(gè)操
作來(lái)說(shuō)，它們是在列表的頭尾增刪元素，這就可以通過(guò)偏移量直接定位，所以它們的復(fù)雜
度也只有 O(1)，可以實(shí)現(xiàn)快速操作。

edis 之所以能快速操作鍵值對(duì)，一方面是因?yàn)?O(1) 復(fù)雜度的哈希表被廣泛使用，包括
String、Hash 和 Set，它們的操作復(fù)雜度基本由哈希表決定，另一方面，Sorted Set 也采
用了 O(logN) 復(fù)雜度的跳表。不過(guò)，集合類(lèi)型的范圍操作，因?yàn)橐闅v底層數(shù)據(jù)結(jié)構(gòu)，復(fù)
雜度通常是 O(N)。這里，我的建議是：用其他命令來(lái)替代，例如可以用 SCAN 來(lái)代替，
避免在 Redis 內(nèi)部產(chǎn)生費(fèi)時(shí)的全集合遍歷操作。

當(dāng)然，我們不能忘了復(fù)雜度較高的 List 類(lèi)型，它的兩種底層實(shí)現(xiàn)結(jié)構(gòu)：雙向鏈表和壓縮列
表的操作復(fù)雜度都是 O(N)。因此，我的建議是：因地制宜地使用 List 類(lèi)型。例如，既然
它的 POP/PUSH 效率很高，那么就將它主要用于 FIFO 隊(duì)列場(chǎng)景，而不是作為一個(gè)可以隨
機(jī)讀寫(xiě)的集合文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-615881.html

到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)：快速的Redis有哪些慢操作？的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！