當談到 redis 時，我們通常會聯想到一個關鍵詞：“速度”。然而，你是否曾思考過 Redis 之所以如此迅猛，到底在哪里呢？實際上，這其中有一個關鍵特性：Redis 能夠在微秒級別內找到數據并快速執行操作。
那么，Redis 為何在眾多數據庫中脫穎而出呢？這其中有幾個關鍵因素。首先，Redis 是一種內存數據庫，它的所有操作都在內存中進行，而內存的訪問速度本身就非?？?。此外，Redis 還依賴于高效的數據結構。這是因為 Redis 的鍵值對實際上是按照特定的數據結構組織的，因此鍵值對的操作實際上是對數據結構進行增刪改查操作，高效的數據結構是 Redis 處理數據的基礎。在這節課中，我們將深入探討這些數據結構。
也許你會說：“這些我都知道，這不就是 Redis 的數據類型嗎？包括字符串、列表、哈希、集合和有序集合？”不過，這些只是 Redis 鍵值對中值的數據類型，也就是數據的存儲方式。而在這里，我們所說的數據結構，指的是要深入了解它們的底層實現原理。
以簡單明了的方式來描述，總共有 6 種底層數據結構，它們與數據類型之間存在如下對應關系，具體如下圖所示：
可以看到，String 類型的底層實現只有一種數據結構，也就是簡單動態字符串。而 List、Hash、Set 和 Sorted Set 這四種數據類型，都有兩種底層實現結構。通常情況下，我們會把這四種類型稱為集合類型，它們的特點是一個鍵對應了一個集合的數據。
看到這里，其實有些問題已經值得我們去考慮了：
- 這些數據結構都是值的底層實現，鍵和值本身之間用什么結構組織？
- 為什么集合類型有那么多的底層結構，它們都是怎么組織數據的，都很快嗎？
- 什么是簡單動態字符串，和常用的字符串是一回事嗎？
接下來，我就和你聊聊前兩個問題。這樣，你不僅可以知道 Redis“快”的基本原理，還可以借此理解 Redis 中有哪些潛在的“慢操作”，最大化 Redis 的性能優勢。而關于簡單動態字符串，我會在后面的課程中再和你討論。
我們先來看看鍵和值之間是用什么結構組織的。
鍵和值用什么結構組織？
為了實現從鍵到值的快速訪問，Redis 使用了一個哈希表來保存所有鍵值對。
一個哈希表，其實就是一個數組，數組的每個元素稱為一個哈希桶。所以，我們常說，一個哈希表是由多個哈希桶組成的，每個哈希桶中保存了鍵值對數據。
看到這里，你可能會問了：“如果值是集合類型的話，作為數組元素的哈希桶怎么來保存呢？”其實，哈希桶中的元素保存的并不是值本身，而是指向具體值的指針。這也就是說，不管值是 String，還是集合類型，哈希桶中的元素都是指向它們的指針。
在下圖中，可以看到，哈希桶中的 entry 元素中保存了*key和*value指針，分別指向了實際的鍵和值，這樣一來，即使值是一個集合，也可以通過*value指針被查找到。
因為這個哈希表保存了所有的鍵值對，所以，我也把它稱為全局哈希表。哈希表的最大好處很明顯，就是讓我們可以用 O(1) 的時間復雜度來快速查找到鍵值對——我們只需要計算鍵的哈希值，就可以知道它所對應的哈希桶位置，然后就可以訪問相應的 entry 元素。
你看，這個查找過程主要依賴于哈希計算，和數據量的多少并沒有直接關系。也就是說，不管哈希表里有 10 萬個鍵還是 100 萬個鍵，我們只需要一次計算就能找到相應的鍵。
但是，如果你只是了解了哈希表的 O(1) 復雜度和快速查找特性，那么，當你往 Redis 中寫入大量數據后，就可能發現操作有時候會突然變慢了。這其實是因為你忽略了一個潛在的風險點，那就是哈希表的沖突問題和 rehash 可能帶來的操作阻塞。
為什么哈希表操作變慢了？
當你往哈希表中寫入更多數據時，哈希沖突是不可避免的問題。這里的哈希沖突，也就是指，兩個 key 的哈希值和哈希桶計算對應關系時，正好落在了同一個哈希桶中。
畢竟，哈希桶的個數通常要少于 key 的數量，這也就是說，難免會有一些 key 的哈希值對應到了同一個哈希桶中。
Redis 解決哈希沖突的方式，就是鏈式哈希。鏈式哈希也很容易理解，就是指同一個哈希桶中的多個元素用一個鏈表來保存，它們之間依次用指針連接。
如下圖所示：entry1、entry2 和 entry3 都需要保存在哈希桶 3 中，導致了哈希沖突。此時，entry1 元素會通過一個*next指針指向 entry2，同樣，entry2 也會通過*next指針指向 entry3。這樣一來，即使哈希桶 3 中的元素有 100 個，我們也可以通過 entry 元素中的指針，把它們連起來。這就形成了一個鏈表，也叫作哈希沖突鏈。
但是，這里依然存在一個問題，哈希沖突鏈上的元素只能通過指針逐一查找再操作。如果哈希表里寫入的數據越來越多，哈希沖突可能也會越來越多，這就會導致某些哈希沖突鏈過長，進而導致這個鏈上的元素查找耗時長，效率降低。對于追求“快”的 Redis 來說，這是不太能接受的。
所以，Redis 會對哈希表做 rehash 操作。rehash 也就是增加現有的哈希桶數量，讓逐漸增多的 entry 元素能在更多的桶之間分散保存，減少單個桶中的元素數量，從而減少單個桶中的沖突。那具體怎么做呢？
其實，為了使 rehash 操作更高效，Redis 默認使用了兩個全局哈希表：哈希表 1 和哈希表 2。一開始，當你剛插入數據時，默認使用哈希表 1，此時的哈希表 2 并沒有被分配空間。隨著數據逐步增多，Redis 開始執行 rehash，這個過程分為三步：
- 給哈希表 2 分配更大的空間，例如是當前哈希表 1 大小的兩倍；
- 把哈希表 1 中的數據重新映射并拷貝到哈希表 2 中；
- 釋放哈希表 1 的空間。
到此，我們就可以從哈希表 1 切換到哈希表 2，用增大的哈希表 2 保存更多數據，而原來的哈希表 1 留作下一次 rehash 擴容備用。
這個過程看似簡單，但是第二步涉及大量的數據拷貝，如果一次性把哈希表 1 中的數據都遷移完，會造成 Redis 線程阻塞，無法服務其他請求。此時，Redis 就無法快速訪問數據了。
為了避免這個問題，Redis 采用了漸進式 rehash。
簡單來說就是在第二步拷貝數據時，Redis 仍然正常處理客戶端請求，每處理一個請求時，從哈希表 1 中的第一個索引位置開始，順帶著將這個索引位置上的所有 entries 拷貝到哈希表 2 中；等處理下一個請求時，再順帶拷貝哈希表 1 中的下一個索引位置的 entries。如下圖所示：
漸進式rehash
這樣就巧妙地把一次性大量拷貝的開銷，分攤到了多次處理請求的過程中，避免了耗時操作，保證了數據的快速訪問。
好了，到這里，你應該就能理解，Redis 的鍵和值是怎么通過哈希表組織的了。對于 String 類型來說，找到哈希桶就能直接增刪改查了，所以，哈希表的 O(1) 操作復雜度也就是它的復雜度了。
但是，對于集合類型來說，即使找到哈希桶了，還要在集合中再進一步操作。接下來，我們來看集合類型的操作效率又是怎樣的。
集合數據操作效率
和 String 類型不同，一個集合類型的值，第一步是通過全局哈希表找到對應的哈希桶位置，第二步是在集合中再增刪改查。那么，集合的操作效率和哪些因素相關呢？
首先，與集合的底層數據結構有關。例如，使用哈希表實現的集合，要比使用鏈表實現的集合訪問效率更高。其次，操作效率和這些操作本身的執行特點有關，比如讀寫一個元素的操作要比讀寫所有元素的效率高。
接下來，我們就分別聊聊集合類型的底層數據結構和操作復雜度。
有哪些底層數據結構？
剛才，我也和你介紹過，集合類型的底層數據結構主要有 5 種：整數數組、雙向鏈表、哈希表、壓縮列表和跳表。
其中，哈希表的操作特點我們剛剛已經學過了；整數數組和雙向鏈表也很常見，它們的操作特征都是順序讀寫，也就是通過數組下標或者鏈表的指針逐個元素訪問，操作復雜度基本是 O(N)，操作效率比較低；壓縮列表和跳表我們平時接觸得可能不多，但它們也是 Redis 重要的數據結構，所以我來重點解釋一下。
壓縮列表實際上類似于一個數組，數組中的每一個元素都對應保存一個數據。和數組不同的是，壓縮列表在表頭有三個字段 zlbytes、zltAIl 和 zllen，分別表示列表長度、列表尾的偏移量和列表中的 entry 個數；壓縮列表在表尾還有一個 zlend，表示列表結束。
在壓縮列表中，如果我們要查找定位第一個元素和最后一個元素，可以通過表頭三個字段的長度直接定位，復雜度是 O(1)。而查找其他元素時，就沒有這么高效了，只能逐個查找，此時的復雜度就是 O(N) 了。
我們再來看下跳表。
有序鏈表只能逐一查找元素，導致操作起來非常緩慢，于是就出現了跳表。具體來說，跳表在鏈表的基礎上，增加了多級索引，通過索引位置的幾個跳轉，實現數據的快速定位，如下圖所示：
跳表的快速查找過程
如果我們要在鏈表中查找 33 這個元素，只能從頭開始遍歷鏈表，查找 6 次，直到找到 33 為止。此時，復雜度是 O(N)，查找效率很低。
為了提高查找速度，我們來增加一級索引：從第一個元素開始，每兩個元素選一個出來作為索引。這些索引再通過指針指向原始的鏈表。例如，從前兩個元素中抽取元素 1 作為一級索引，從第三、四個元素中抽取元素 11 作為一級索引。此時，我們只需要 4 次查找就能定位到元素 33 了。
如果我們還想再快，可以再增加二級索引：從一級索引中，再抽取部分元素作為二級索引。例如，從一級索引中抽取 1、27、100 作為二級索引，二級索引指向一級索引。這樣，我們只需要 3 次查找，就能定位到元素 33 了。
可以看到，這個查找過程就是在多級索引上跳來跳去，最后定位到元素。這也正好符合“跳”表的叫法。當數據量很大時，跳表的查找復雜度就是 O(logN)。
好了，我們現在可以按照查找的時間復雜度給這些數據結構分下類了：
不同操作的復雜度
集合類型的操作類型很多，有讀寫單個集合元素的，例如 HGET、HSET，也有操作多個元素的，例如 SADD，還有對整個集合進行遍歷操作的，例如 SMEMBERS。這么多操作，它們的復雜度也各不相同。而復雜度的高低又是我們選擇集合類型的重要依據。
我總結了一個“四句口訣”，希望能幫助你快速記住集合常見操作的復雜度。這樣你在使用過程中，就可以提前規避高復雜度操作了。
- 單元素操作是基礎；
- 范圍操作非常耗時；
- 統計操作通常高效；
例外情況只有幾個：
第一，單元素操作，是指每一種集合類型對單個數據實現的增刪改查操作。例如，Hash 類型的 HGET、HSET 和 HDEL，Set 類型的 SADD、SREM、SRANDMEMBER 等。這些操作的復雜度由集合采用的數據結構決定，例如，HGET、HSET 和 HDEL 是對哈希表做操作，所以它們的復雜度都是 O(1)；Set 類型用哈希表作為底層數據結構時，它的 SADD、SREM、SRANDMEMBER 復雜度也是 O(1)。
這里，有個地方你需要注意一下，集合類型支持同時對多個元素進行增刪改查，例如 Hash 類型的 HMGET 和 HMSET，Set 類型的 SADD 也支持同時增加多個元素。此時，這些操作的復雜度，就是由單個元素操作復雜度和元素個數決定的。例如，HMSET 增加 M 個元素時，復雜度就從 O(1) 變成 O(M) 了。
第二，范圍操作，是指集合類型中的遍歷操作，可以返回集合中的所有數據，比如 Hash 類型的 HGETALL 和 Set 類型的 SMEMBERS，或者返回一個范圍內的部分數據，比如 List 類型的 LRANGE 和 ZSet 類型的 ZRANGE。這類操作的復雜度一般是 O(N)，比較耗時，我們應該盡量避免。
不過，Redis 從 2.8 版本開始提供了 SCAN 系列操作（包括 HSCAN，SSCAN 和 ZSCAN），這類操作實現了漸進式遍歷，每次只返回有限數量的數據。這樣一來，相比于 HGETALL、SMEMBERS 這類操作來說，就避免了一次性返回所有元素而導致的 Redis 阻塞。
第三，統計操作，是指集合類型對集合中所有元素個數的記錄，例如 LLEN 和 SCARD。這類操作復雜度只有 O(1)，這是因為當集合類型采用壓縮列表、雙向鏈表、整數數組這些數據結構時，這些結構中專門記錄了元素的個數統計，因此可以高效地完成相關操作。
第四，例外情況，是指某些數據結構的特殊記錄，例如壓縮列表和雙向鏈表都會記錄表頭和表尾的偏移量。這樣一來，對于 List 類型的 LPOP、RPOP、LPUSH、RPUSH 這四個操作來說，它們是在列表的頭尾增刪元素，這就可以通過偏移量直接定位，所以它們的復雜度也只有 O(1)，可以實現快速操作。
小結
我們學習了 Redis 的底層數據結構，這既包括了 Redis 中用來保存每個鍵和值的全局哈希表結構，也包括了支持集合類型實現的雙向鏈表、壓縮列表、整數數組、哈希表和跳表這五大底層結構。
Redis 之所以能快速操作鍵值對，一方面是因為 O(1) 復雜度的哈希表被廣泛使用，包括 String、Hash 和 Set，它們的操作復雜度基本由哈希表決定，另一方面，Sorted Set 也采用了 O(logN) 復雜度的跳表。不過，集合類型的范圍操作，因為要遍歷底層數據結構，復雜度通常是 O(N)。這里，我的建議是：用其他命令來替代，例如可以用 SCAN 來代替，避免在 Redis 內部產生費時的全集合遍歷操作。
當然，我們不能忘了復雜度較高的 List 類型，它的兩種底層實現結構：雙向鏈表和壓縮列表的操作復雜度都是 O(N)。因此，我的建議是：因地制宜地使用 List 類型。例如，既然它的 POP/PUSH 效率很高，那么就將它主要用于 FIFO 隊列場景，而不是作為一個可以隨機讀寫的集合。
Redis 數據類型豐富，每個類型的操作繁多，我們通常無法一下子記住所有操作的復雜度。所以，最好的辦法就是掌握原理，以不變應萬變。這里，你可以看到，一旦掌握了數據結構基本原理，你可以從原理上推斷不同操作的復雜度，即使這個操作你不一定熟悉。這樣一來，你不用死記硬背，也能快速合理地做出選擇了。
