Redis五種資料結構詳解

Redis是基于c語言編寫的開源非關系型記憶體資料庫，可以用作資料庫、緩存、消息中間件，這麼優秀的東西一定要一點一點的吃透它。

Redis的五種資料結構包括以下五種：

String：字元串類型

List：清單類型

Set：無序集合類型

ZSet：有序集合類型

Hash：哈希表類型但是作為一名優秀的程式在Redis中有一個「核心的對象」叫做redisObject ，是用來表示所有的key和value的，用redisObject結構體來表示String、Hash、List、Set、ZSet五種資料類型。

redisObject的源代碼在redis.h中，使用c語言寫的，感興趣的可以自行檢視，關于redisObject我這裡畫了一張圖，表示redisObject的結構如下所示：

在redisObject中「type表示屬于哪種資料類型，encoding表示該資料的存儲方式」，也就是底層的實作的該資料類型的資料結構。是以這篇文章具體介紹的也是encoding對應的部分。

那麼encoding中的存儲類型又分别表示什麼意思呢？具體資料類型所表示的含義，如下圖所示：

你在Redis中設定一個字元串key 234，然後檢視這個字元串的存儲類型就會看到為int類型，非整數型的使用的是embstr儲存類型，具體操作如下圖所示：員可能不能隻停留在隻會用這五種類型進行crud工作，還是得深入了解這五種資料結構的底層原理。

二、Redis核心對象

三、String類型String是Redis最基本的資料類型，上面的簡介中也說到Redis是用c語言開發的。但是Redis中的字元串和c語言中的字元串類型卻是有明顯的差別。

String類型的資料結構存儲方式有三種int、raw、embstr。那麼這三種存儲方式有什麼差別呢？

int

Redis中規定假如存儲的是「整數型值」，比如set num 123這樣的類型，就會使用 int的存儲方式進行存儲，在redisObject的「ptr屬性」中就會儲存該值。

SDS

假如存儲的「字元串是一個字元串值并且長度大于32個位元組」就會使用SDS（simple dynamic string）方式進行存儲，并且encoding設定為raw；

若是「字元串長度小于等于32個位元組」就會将encoding改為embstr來儲存字元串。

SDS稱為「簡單動态字元串」，對于SDS中的定義在Redis的源碼中有的三個屬性int len、int free、char buf[]。

len儲存了字元串的長度，

free表示buf數組中未使用的位元組數量

buf數組則是儲存字元串的每一個字元元素。

是以當你在Redsi中存儲一個字元串Hello時，根據Redis的源代碼的描述可以畫出SDS的形式的redisObject結構圖如下圖所示：

SDS與c語言字元串對比

Redis使用SDS作為存儲字元串的類型肯定是有自己的優勢，SDS與c語言的字元串相比，SDS對c語言的字元串做了自己的設計和優化，具體優勢有以下幾點：

（1）c語言中的字元串并不會記錄自己的長度，是以「每次擷取字元串的長度都會周遊得到，時間的複雜度是O(n)」，而Redis中擷取字元串隻要讀取len的值就可，時間複雜度變為O(1)。

（2）「c語言」中兩個字元串拼接，若是沒有配置設定足夠長度的記憶體空間就「會出現緩沖區溢出的情況」；而「SDS」會先根據len屬性判斷空間是否滿足要求，若是空間不夠，就會進行相應的空間擴充，是以「不會出現緩沖區溢出的情況」。

（3）SDS還提供「空間預配置設定」和「惰性空間釋放」兩種政策。在為字元串配置設定空間時，配置設定的空間比實際要多，這樣就能「減少連續的執行字元串增長帶來記憶體重新配置設定的次數」。

當字元串被縮短的時候，SDS也不會立即回收不适用的空間，而是通過free屬性将不使用的空間記錄下來，等後面使用的時候再釋放。

具體的空間預配置設定原則是：「當修改字元串後的長度len小于1MB，就會預配置設定和len一樣長度的空間，即len=free；若是len大于1MB，free配置設定的空間大小就為1MB」。

（4）SDS是二進制安全的，除了可以儲存字元串以外還可以儲存二進制檔案（如圖檔、音頻，視訊等檔案的二進制資料）；而c語言中的字元串是以空字元串作為結束符，一些圖檔中含有結束符，是以不是二進制安全的。

為了友善易懂，做了一個c語言的字元串和SDS進行對比的表格，如下所示：

String類型

（1）首先要把上傳得圖檔進行編碼，這裡寫了一個工具類把圖檔處理成了Base64得編碼形式，具體得實作代碼如下：

（2）第二步就是把處理後的圖檔字元串格式存儲進Redis中，實作的代碼如下所示：

這樣就是實作了圖檔得二進制存儲，當然String類型得資料結構得應用也還有正常計數：「統計微網誌數、統計粉絲數」等。

四、Hash類型ash對象的實作方式有兩種分别是ziplist、hashtable，其中hashtable的存儲方式key是String類型的，value也是以key value的形式進行存儲。

字典類型的底層就是hashtable實作的，明白了字典的底層實作原理也就是明白了hashtable的實作原理，hashtable的實作原理可以與HashMap的是底層原理相類比。

字典

兩者在新增時都會通過key計算出數組下标，不同的是計算法方式不同：

HashMap中是以hash函數的方式，

hashtable中計算出hash值後，還要通過sizemask 屬性和哈希值再次得到數組下标。

我們知道hash表最大的問題就是hash沖突，為了解決hash沖突，假如hashtable中不同的key通過計算得到同一個index，就會形成單向連結清單（「鍊位址法」），如下圖所示：

rehash

在字典的底層實作中，value對象以每一個dictEntry的對象進行存儲，當hash表中的存放的鍵值對不斷的增加或者減少時，需要對hash表進行一個擴充或者收縮。

這裡就會和HashMap一樣也會就進行rehash操作，進行重新散列排布。從上圖中可以看到有ht[0]和ht[1]兩個對象，先來看看對象中的屬性是幹嘛用的。

在hash表結構定義中有四個屬性分别是：

dictEntry **table、

unsigned long size、

unsigned long sizemask、

unsigned long used

分别表示的含義就是「哈希表數組、hash表大小、用于計算索引值，總是等于size-1、hash表中已有的節點數」。

ht[0]是用來最開始存儲資料的，當要進行擴充或者收縮時，ht[0]的大小就決定了ht[1]的大小，ht[0]中的所有的鍵值對就會重新散列到ht[1]中。

擴充操作：ht[1]擴充的大小是比目前 ht[0].used 值的二倍大的第一個 2 的整數幂；收縮操作：ht[0].used 的第一個大于等于的 2 的整數幂。

當ht[0]上的所有的鍵值對都rehash到ht[1]中，會重新計算所有的數組下标值，當資料遷移完後ht[0]就會被釋放，然後将ht[1]改為ht[0]，并新建立ht[1]，為下一次的擴充和收縮做準備。

漸進式rehash

假如在rehash的過程中資料量非常大，Redis不是一次性把全部資料rehash成功，這樣會導緻Redis對外服務停止，Redis内部為了處理這種情況采用「漸進式的rehash」。

Redis将所有的rehash的操作分成多步進行，直到都rehash完成，具體的實作與對象中的rehashindex屬性相關，「若是rehashindex 表示為-1表示沒有rehash操作」。

當rehash操作開始時會将該值改成0，在漸進式rehash的過程「更新、删除、查詢會在ht[0]和ht[1]中都進行」，比如更新一個值先更新ht[0]，然後再更新ht[1]。

而新增操作直接就新增到ht[1]表中，ht[0]不會新增任何的資料，這樣保證「ht[0]隻減不增，直到最後的某一個時刻變成空表」，這樣rehash操作完成。

上面就是字典的底層hashtable的實作原理，說完了hashtable的實作原理，我們再來看看Hash資料結構的兩一種存儲方式「ziplist（壓縮清單）」

ziplist

壓縮清單（ziplist）是一組連續記憶體塊組成的順序的資料結構，壓縮清單能夠節省空間，壓縮清單中使用多個節點來存儲資料。

壓縮清單是清單鍵和哈希鍵底層實作的原理之一，「壓縮清單并不是以某種壓縮算法進行壓縮存儲資料，而是它表示一組連續的記憶體空間的使用，節省空間」，壓縮清單的記憶體結構圖如下：

壓縮清單中每一個節點表示的含義如下所示：

zlbytes：4個位元組的大小，記錄壓縮清單占用記憶體的位元組數。

zltail：4個位元組大小，記錄表尾節點距離起始位址的偏移量，用于快速定位到尾節點的位址。

zllen：2個位元組的大小，記錄壓縮清單中的節點數。

entry：表示清單中的每一個節點。

zlend：表示壓縮清單的特殊結束符号’0xFF’。

再壓縮清單中每一個entry節點又有三部分組成，包括previous_entry_ength、encoding、content。

previous_entry_ength表示前一個節點entry的長度，可用于計算前一個節點的其實位址，因為他們的位址是連續的。

encoding：這裡儲存的是content的内容類型和長度。

content：content儲存的是每一個節點的内容。

說到這裡相信大家已經都hash這種資料結構已經非常了解，若是第一次接觸Redis五種基本資料結構的底層實作的話，建議多看幾遍，下面來說一說hash的應用場景。

應用場景

哈希表相對于String類型存儲資訊更加直覺，存儲更加友善，經常會用來做使用者資料的管理，存儲使用者的資訊。

hash也可以用作高并發場景下使用Redis生成唯一的id。下面我們就以這兩種場景用作案例編碼實作。

存儲使用者資料

第一個場景比如我們要儲存使用者資訊，一般使用使用者的ID作為key值，保持唯一性，使用者的其他資訊（位址、年齡、生日、電話号碼等）作為value值存儲。

若是傳統的實作就是将使用者的資訊封裝成為一個對象，通過序列化存儲資料，當需要擷取使用者資訊的時候，就會通過反序列化得到使用者資訊。

但是這樣必然會造成序列化和反序列化的性能的開銷，并且若是隻修改其中的一個屬性值，就需要把整個對象序列化出來，操作的動作太大，造成不必要的性能開銷。

若是使用Redis的hash來存儲使用者資料，就會将原來的value值又看成了一個k v形式的存儲容器，這樣就不會帶來序列化的性能開銷的問題。

分布式生成唯一ID

第二個場景就是生成分布式的唯一ID，這個場景下就是把redis封裝成了一個工具類進行實作，實作的代碼如下：

五、List

Redis中的清單在3.2之前的版本是使用ziplist和linkedlist進行實作的。在3.2之後的版本就是引入了quicklist。

ziplist壓縮清單上面已經講過了，我們來看看linkedlist和quicklist的結構是怎麼樣的。

linkedlist是一個雙向連結清單，他和普通的連結清單一樣都是由指向前後節點的指針。插入、修改、更新的時間複雜度尾O(1)，但是查詢的時間複雜度确實O(n)。

linkedlist和quicklist的底層實作是采用連結清單進行實作，在c語言中并沒有内置的連結清單這種資料結構，Redis實作了自己的連結清單結構。

Redis中連結清單的特性：

每一個節點都有指向前一個節點和後一個節點的指針。

頭節點和尾節點的prev和next指針指向為null，是以連結清單是無環的。

連結清單有自己長度的資訊，擷取長度的時間複雜度為O(1)。

Redis中List的實作比較簡單，下面我們就來看看它的應用場景。

應用場景

Redis中的清單可以實作「阻塞隊列」，結合lpush和brpop指令就可以實作。生産者使用lupsh從清單的左側插入元素，消費者使用brpop指令從隊列的右側擷取元素進行消費。

（1）首先配置redis的配置，為了友善我就直接放在application.yml配置檔案中，實際中可以把redis的配置檔案放在一個redis.properties檔案單獨放置，具體配置如下：

（2）第二步建立redis的配置類，叫做RedisConfig，并标注上@Configuration注解，表明他是一個配置類。

@Configuration
public class RedisConfiguration {

@Value("${spring.redis.host}")
private String host;
@Value("${spring.redis.port}")
private int port;
@Value("${spring.redis.password}")
private String password;
@Value("${spring.redis.pool.max-active}")
private int maxActive;
@Value("${spring.redis.pool.max-idle}")
private int maxIdle;
@Value("${spring.redis.pool.min-idle}")
private int minIdle;
@Value("${spring.redis.pool.max-wait}")
private int maxWait;
@Value("${spring.redis.database}")
private int database;
@Value("${spring.redis.timeout}")
private int timeout;

@Bean
public JedisPoolConfig getRedisConfiguration(){
JedisPoolConfig jedisPoolConfig= new JedisPoolConfig();
jedisPoolConfig.setMaxTotal(maxActive);
jedisPoolConfig.setMaxIdle(maxIdle);
jedisPoolConfig.setMinIdle(minIdle);
jedisPoolConfig.setMaxWaitMillis(maxWait);
return jedisPoolConfig;
}

@Bean
public JedisConnectionFactory getConnectionFactory() {
JedisConnectionFactory factory = new JedisConnectionFactory();
factory.setHostName(host);
factory.setPort(port);
factory.setPassword(password);
factory.setDatabase(database);
JedisPoolConfig jedisPoolConfig= getRedisConfiguration();
factory.setPoolConfig(jedisPoolConfig);
return factory;
}

@Bean
public RedisTemplate<?, ?> getRedisTemplate() {
JedisConnectionFactory factory = getConnectionFactory();
RedisTemplate<?, ?> redisTemplate = new StringRedisTemplate(factory);
return redisTemplate;
}
}
           

（3）第三步就是建立Redis的工具類RedisUtil，自從學了面向對象後，就喜歡把一些通用的東西拆成工具類，好像一個一個零件，需要的時候，就把它組裝起來。

@Component
public class RedisUtil {

@Autowired
private RedisTemplate<String, Object> redisTemplate;
/**
* 存消息到消息隊列中
* @param key 鍵
* @param value 值
* @return
*/
public boolean lPushMessage(String key, Object value) {
try {
redisTemplate.opsForList().leftPush(key, value);
return true;
} catch (Exception e) {
e.printStackTrace();
return false;
}
}

/**
* 從消息隊列中彈出消息
* @param key 鍵
* @return
*/
public Object rPopMessage(String key) {
try {
return redisTemplate.opsForList().rightPop(key);
} catch (Exception e) {
e.printStackTrace();
return null;
}
}

/**
* 檢視消息
* @param key 鍵
* @param start 開始
* @param end 結束 0 到 -1代表所有值
* @return
*/
public List<Object> getMessage(String key, long start, long end) {
try {
return redisTemplate.opsForList().range(key, start, end);
} catch (Exception e) {
e.printStackTrace();
return null;
}
}
           

這樣就完成了Redis消息隊列工具類的建立，在後面的代碼中就可以直接使用。

六、set集合

Redis中清單和集合都可以用來存儲字元串，但是「Set是不可重複的集合，而List清單可以存儲相同的字元串」，Set集合是無序的這個和後面講的ZSet有序集合相對。

Set的底層實作是「ht和intset」，ht（哈希表）前面已經詳細了解過，下面我們來看看inset類型的存儲結構。

inset也叫做整數集合，用于儲存整數值的資料結構類型，它可以儲存int16_t、int32_t 或者int64_t 的整數值。

在整數集合中，有三個屬性值encoding、length、contents[]，分别表示編碼方式、整數集合的長度、以及元素内容，length就是記錄contents裡面的大小。

在整數集合新增元素的時候，若是超出了原集合的長度大小，就會對集合進行更新，具體的更新過程如下：

首先擴充底層數組的大小，并且數組的類型為新元素的類型。

然後将原來的數組中的元素轉為新元素的類型，并放到擴充後數組對應的位置。

整數集合更新後就不會再降級，編碼會一直保持更新後的狀态。

應用場景

Set集合的應用場景可以用來「去重、抽獎、共同好友、二度好友」等業務類型。接下來模拟一個添加好友的案例實作：

@RequestMapping(value = "/addFriend", method = RequestMethod.POST)
public Long addFriend(User user, String friend) {
    String currentKey = null;
    // 判斷是否是目前使用者的好友
    if (AppContext.getCurrentUser().getId().equals(user.getId)) {
        currentKey = user.getId.toString();
    }
    //若是傳回0則表示不是該使用者好友
    return currentKey==null?0l:setOperations.add(currentKey, friend);
}
           

假如兩個使用者A和B都是用上上面的這個接口添加了很多的自己的好友，那麼有一個需求就是要實作擷取A和B的共同好友，那麼可以進行如下操作：

public Set intersectFriend(User userA, User userB) {
    return setOperations.intersect(userA.getId.toString(), userB.getId.toString());
}
```七、ZSet集合
ZSet是有序集合，從上面的圖中可以看到ZSet的底層實作是ziplist和skiplist實作的，ziplist上面已經詳細講過，這裡來講解skiplist的結構實作。

skiplist也叫做「跳躍表」，跳躍表是一種有序的資料結構，它通過每一個節點維持多個指向其它節點的指針，進而達到快速通路的目的。

skiplist有如下幾個特點：

有很多層組成，由上到下節點數逐漸密集，最上層的節點最稀疏，跨度也最大。
每一層都是一個有序連結清單，至少包含兩個節點，頭節點和尾節點。
每一層的每一個每一個節點都含有指向同一層下一個節點和下一層同一個位置節點的指針。
如果一個節點在某一層出現，那麼該以下的所有連結清單同一個位置都會出現該節點。
具體實作的結構圖如下所示：



在跳躍表的結構中有head和tail表示指向頭節點和尾節點的指針，能快速的實作定位。level表示層數，len表示跳躍表的長度，BW表示後退指針，在從尾向前周遊的時候使用。

BW下面還有兩個值分别表示分值（score）和成員對象（各個節點儲存的成員對象）。

跳躍表的實作中，除了最底層的一層儲存的是原始連結清單的完整資料，上層的節點數會越來越少，并且跨度會越來越大。

跳躍表的上面層就相當于索引層，都是為了找到最後的資料而服務的，資料量越大，條表所展現的查詢的效率就越高，和平衡樹的查詢效率相差無幾。

應用場景

因為ZSet是有序的集合，是以ZSet在實作排序類型的業務是比較常見的，比如在首頁推薦10個最熱門的文章，也就是閱讀量由高到低，排行榜的實作等業務。

下面就選用擷取排行榜前前10名的選手作為案例實作，實作的代碼如下所示：


```javascript
@Autowired
private RedisTemplate redisTemplate;
/**
 * 擷取前10排名
 * @return
 */
    public static List<levelVO > getZset(String key, long baseNum, LevelService levelService){
        ZSetOperations<Serializable, Object> operations = redisTemplate.opsForZSet();
        // 根據score分數值擷取前10名的資料
        Set<ZSetOperations.TypedTuple<Object>> set = operations.reverseRangeWithScores(key,0,9);
        List<LevelVO> list= new ArrayList<LevelVO>();
        int i=1;
        for (ZSetOperations.TypedTuple<Object> o:set){
            int uid = (int) o.getValue();
            LevelCache levelCache = levelService.getLevelCache(uid);
            LevelVO levelVO = levelCache.getLevelVO();
            long score = (o.getScore().longValue() - baseNum + levelVO .getCtime())/CommonUtil.multiplier;
            levelVO .setScore(score);
            levelVO .setRank(i);
            list.add( levelVO );
            i++;
        }
        return list;
    }
           

原文位址：https://mp.weixin.qq.com/s/F5Uq0V9jWHpvfb94bTmaow