概述

  Redis底層有六種數據類型包括：簡單動態字元串、雙向鏈表、壓縮列表、哈希表、跳錶和整數數組。這六種數據結構五大數據類型關係如下：

• String：簡單動態字元串
• List：雙向鏈表、壓縮列表
• Hash：壓縮列表、哈希表
• Sorted Set：壓縮列表、跳錶
• Set：哈希表、整數數組

          數據類型和底層數據結構對應關係

  每種數據結構特性不一樣，操作時間也不一樣。

        數據結構的時間複雜度

二、數據結構

  從上述圖中可以知道，Redis的底層數據結構由簡單動態字元串、雙向鏈表、壓縮列表、哈希表、跳錶、整數數組組成，其中哈希表和整數數組基本上大家都很熟悉了，下麵重點介紹一下其餘的幾種數據結構。

1、簡單動態字元串(SDS)

  結構：alloc，len，buf

        簡單動態字元串結構

  buf：位元組數組，保存實際數據。為了表示位元組數組的結束，Redis 會自動在數組最後加一個“\0”，這就會額外占用 1 個位元組的開銷。

  len：占 4 個位元組，表示 buf 的已用長度。

  alloc：也占個 4 位元組，表示 buf 的實際分配長度，一般大於 len。

  那麼SDS與C字元串有什麼區別呢？區別主要有如下兩點：

  （1）獲取字元串長度時間複雜度為O(1)

  （2）在修改字元串時，會先檢查長度是否夠長，不夠會進行擴展，避免緩衝區溢出

2、鏈表

  Redis使用的是雙向無環鏈表，並且具有以下幾個特點：

  （1）雙端：鏈表具有前置節點和後置節點的引用，獲取這兩個節點時間複雜度都為O(1)。

  （2）無環：表頭節點的 prev 指針和表尾節點的 next 指針都指向 NULL,對鏈表的訪問都是以 NULL 結束。

  （3）帶鏈表長度計數器：通過 len 屬性獲取鏈表長度的時間複雜度為 O(1)。

  （4）多態：鏈表節點使用 void* 指針來保存節點值，可以保存各種不同類型的值。

3、壓縮列表

  壓縮列表（ziplist）是Redis為了節省記憶體而開發的，是由一系列特殊編碼的連續記憶體塊組成的順序型數據結構，一個壓縮列表可以包含任意多個節點（entry），每個節點可以保存一個位元組數組或者一個整數值。壓縮列表並不是對數據利用某種演算法進行壓縮，而是將數據按照一定規則編碼在一塊連續的記憶體區域，目的是節省記憶體。

壓縮列表實際上類似於一個數組，數組中的每一個元素都對應保存一個數據。和數組不同的是，壓縮列表在表頭有三個欄位 zlbytes、zltail 和 zllen，分別表示列表長度、列表尾的偏移量和列表中的 entry 個數；壓縮列表在表尾還有一個 zlend，表示列表結束；

我們要查找定位第一個元素和最後一個元素，可以通過表頭三個欄位的長度直接定位，複雜度是 O(1)。而查找其他元素時，就沒有這麼高效了，只能逐個查找，此時的複雜度就是 O(N) 了。

          壓縮表的查找過程

4、跳錶

  跳錶在鏈表的基礎上，增加了多級索引，通過索引位置的幾個跳轉，實現數據的快速定位，時間複雜度為O(logN)，比起鏈表，跳錶的查詢效率大大提高到了 O(logn)。

        跳錶查找過程

三、Redis數據類型的基本數據結構

1、String（字元串）

  1.1 String的內部結構

  redis沒有直接使用C語言中的字元串表示，而是自己構建了一個字元串，名為 “簡單動態字元串” （simple dynamic string ， SDS）。其中，C語言中的字元串只是作為字元串面量（通常在無須對字元串值進行修改的地方使用）。

  String在結構上的實現類似於Java中的ArrayList（預設構造一個大小為10的初始數組），這是冗餘分配記憶體的思想，也稱為預分配；這種思想可以減少擴容帶來的性能消耗。

              String的內部結構

1.2 String使用的數據編碼

  存儲數字的話，採用int類型的編碼，如果是非數字的話，採用 raw 編碼；

1.3 使用場景

  （1） 簡單字元緩存

  （2） 分散式鎖

  （3）計數功能——》計數服務

2、List(列表)

2.1 List的內部結構

  Redis的列表相當於Java語言中的LinkedList，它是一個雙向鏈表數據結構（但是這個結構設計比較巧妙，後面會介紹），支持前後順序遍歷。鏈表結構插入和刪除操作快，時間複雜度O(1)，查詢慢，時間複雜度O(n)。

                List的內部結構

2.2 List使用的數據編碼

  字元串長度及元素個數小於一定範圍使用 ziplist 編碼，任意條件不滿足，則轉化為 linkedlist 編碼。

2.3 使用場景

  （1）利用List實現棧、隊列

  （2）redis做消息隊列（不推薦使用redis做消息隊列）

  （3）列表緩存

3、Hash(字典)

3.1 Hash的內部結構

  Redis的hash(字典)相當於Java語言中的HashMap，它是根據散列值分佈的無序字典，內部的元素是通過鍵值對的方式存儲。

  hash(字典)的實現與Java中的HashMap（JDK1.7）的結構也是一致的，它的數據結構也是數組+鏈表組成的二維結構，節點元素散列在數組上，如果發生hash碰撞則使用鏈表串聯在數組節點上。

        Hash的內部結構

3.2 Hash使用的數據編碼

  hash 對象保存的鍵值對內的鍵和值字元串長度小於一定值及鍵值對。

3.3 使用場景

  （1） 存儲對象

4、Set（集合）

4.1 Set的內部結構

  Redis的set(集合)相當於Java語言里的HashSet，它內部的鍵值對是無序的、唯一的。它的內部實現了一個所有value為null的特殊字典。
集合中的最後一個元素被移除之後，數據結構被自動刪除，記憶體被回收。

        Set的內部結構

4.2 Set使用的數據編碼

  保存元素為整數及元素個數小於一定範圍使用 intset 編碼，任意條件不滿足，則使用 hashtable 編碼。

4.3 使用場景

  （1）標簽，社交，查詢有共同興趣愛好的人,智能推薦

  （2）抽獎

  （3）朋友圈點贊

5、Zset（有序集合）

5.1 Zset的內部結構

  zset(有序集合)是Redis中最常問的數據結構。它類似於Java語言中的SortedSet和HashMap的結合體，它一方面通過set來保證內部value值的唯一性，另一方面通過value的score（權重）來進行排序。這個排序的功能是通過Skip List（跳躍列表）來實現的。zset(有序集合)的最後一個元素value被移除後，數據結構被自動刪除，記憶體被回收。

        Zset的內部結構

5.2 Zset使用的數據編碼

  zset 對象中保存的元素個數小於及成員長度小於一定值使用 ziplist 編碼，任意條件不滿足，則使用 skiplist 編碼。

5.3 使用場景

  （1）排名場景