底層數據結構有六種，分別是簡單動態字符串、鏈表、壓縮列表、哈希表、跳轉表和整數數組。它們與數據類型的對應關系如下圖所示:
如您所見，String類型的底層實現只有壹個數據結構，這是壹個簡單的動態字符串。列表、散列、集合和排序集合這四種數據類型都有兩個底層實現結構。通常我們會把這四種類型稱為集合類型，它們的特點是壹個鍵對應壹個集合的數據。
為了實現從鍵到值的快速訪問，Redis使用壹個散列表來存儲所有的鍵-值對。哈希表實際上是壹個數組，數組的每個元素稱為壹個哈希桶。哈希桶中的元素保存的不是值本身，而是壹個指向特定值的指針。
也就是說，無論值是字符串還是集合類型，哈希桶中的元素都是指向它們的指針。在下圖中，您可以看到鍵和值指針保存在哈希桶的entry元素中，它們分別指向實際的鍵和值。
哈希沖突，即兩個鍵的哈希值和哈希桶計算對應關系時，剛好落入同壹個哈希桶。畢竟哈希桶的數量通常小於鍵的數量，這意味著鍵的壹些哈希值必然會對應同壹個哈希桶。Redis解決哈希沖突的方式是鏈式哈希。鏈式哈希也很好理解，意思是同壹個哈希桶中的多個元素保存在壹個鏈表中，它們通過指針依次連接。
如下圖所示:entry1，entry2，entry3都需要保存在哈希桶3中，產生哈希沖突。此時，entry1元素將通過下壹個指針指向entry2，類似地，entry2將通過下壹個指針指向entry3。這樣，即使Hash Bucket 3中有100個元素，我們也可以通過entry元素中的指針將它們連接起來。
事實上，為了讓重散列操作更高效，Redis默認使用兩個全局哈希表:哈希表1和哈希表2。起初，當您只是插入數據時，默認使用散列表1。此時，散列表2還沒有被分配空間。隨著數據的逐漸增多，Redis開始執行rehash，分為三個步驟:
這個過程看似簡單，但第二步涉及到大量的數據拷貝。如果壹次性遷移散列表1中的所有數據，Redis線程將被阻塞，其他請求無法得到服務。此時，Redis無法快速訪問數據。為了避免這個問題，Redis采用了漸進式的重散列。
簡單來說，第二步復制數據時，Redis仍然正常處理客戶端請求。在處理每個請求時，它從哈希表1中的第壹個索引位置開始，順便將這個索引位置的所有條目復制到哈希表2中。當處理下壹個請求時，會順便復制哈希表1中下壹個索引位置的條目。如下圖所示:
對於字符串類型，找到哈希桶後可以直接添加、刪除、更改查詢，所以哈希表的O(1)運算的復雜度也是它的復雜度。
對於壹個集合類型的值，第壹步是通過全局哈希表找到對應哈希桶的位置，第二步是在集合中添加、刪除和檢查。首先，操作復雜度與集合的底層數據結構有關。例如，使用哈希表實現的集合的訪問效率高於使用鏈表實現的訪問效率。其次，運行效率與這些操作的執行特性有關。例如，讀寫壹個元素比讀寫所有元素更高效。
對應於字符串類型的簡單動態字符串將在後面討論。集合類型的基本數據結構有五種:整數數組、鏈表、哈希表、壓縮表和跳表。
整型數組和雙向鏈表也很常見，它們的操作特點是順序讀寫，即通過數組下標或鏈表指針逐元素訪問，運算復雜度基本為O(N)，所以運算效率比較低；壓縮列表和跳轉列表我們可能接觸不多，但它們也是Redis的重要數據結構。
壓縮列表實際上類似於壹個數組，數組中的每個元素保存壹段相應的數據。與數組不同的是，壓縮後的鏈表在頭中有三個字段zlbytes、zltail和zllen，分別代表鏈表的長度、鏈表尾部的偏移量和鏈表中條目的個數。壓縮列表在表的末尾還有壹個zlend，表示列表的末尾。
跳轉表在鏈表的基礎上增加了壹個多級索引，通過索引位置的幾次跳轉可以快速定位數據，如下圖所示:
Redis能夠快速操作鍵值對，壹方面是因為復雜度為O(1)的哈希表應用廣泛，包括字符串、哈希和集合，其操作復雜度基本由哈希表決定；另壹方面，有序集也采用復雜度為O(logN)的跳表。但是，集合類型的範圍操作的復雜度通常為O(N)，因為它需要遍歷底層數據結構。
不能忘記復雜度很高的鏈表類型，它的兩個底層實現結構:雙向鏈表和壓縮鏈表在運算復雜度上都是O(N)。因此，要因地制宜地使用列表類型。比如，由於其POP/PUSH效率高，所以主要用於FIFO隊列場景，而不是作為壹個可以隨機讀寫的集合。