摘要：從代碼上看字典也是在哈希表基礎(chǔ)上再抽象了一層而已。在中，哈希表實(shí)際上就是數(shù)組鏈表的形式來構(gòu)建的。后，在哈希沖突時(shí)是將新的節(jié)點(diǎn)添加到鏈表的表尾。在對(duì)哈希表進(jìn)行擴(kuò)展或者收縮操作時(shí)，過程并不是一次性地完成的，而是漸進(jìn)式地完成的。

只有光頭才能變強(qiáng)

最近在學(xué)Redis，我相信只要是接觸過Java開發(fā)的都會(huì)聽過Redis這么一個(gè)技術(shù)。面試也是非常高頻的一個(gè)知識(shí)點(diǎn)，之前一直都是處于了解階段。秋招過后這段時(shí)間是沒有什么壓力的，所以打算系統(tǒng)學(xué)學(xué)Redis，這也算是我從零學(xué)習(xí)Redis的筆記吧。

本文力求講清每個(gè)知識(shí)點(diǎn)，希望大家看完能有所收獲。

首先，肯定是去官網(wǎng)看看官方是怎么介紹Redis的啦。https://redis.io/topics/introduction

如果像我一樣，英語可能不太好的，可能看不太懂。沒事，咱們Chrome瀏覽器可以切換成中文的，中文是我們的母語，肯定沒啥壓力了。Eumm...

讀完之后，發(fā)現(xiàn)中文也就那樣了。

一大堆沒見過的技術(shù)：lua(Lua腳本)、replication(復(fù)制)、Redis Sentinel(哨兵)、Redis Cluster(Redis 集群)，當(dāng)然我們也會(huì)有看得懂的技術(shù)：transactions(事務(wù))、different levels of on-disk persistence(數(shù)據(jù)持久化)、LRU eviction(LRU淘汰機(jī)制)..

至少官方介紹Redis的第一句應(yīng)該是可以很容易看懂："Redis is an open source (BSD licensed),in-memory data structure store, used as a database,cache and message broker."

Redis是一個(gè)開源的，基于內(nèi)存的數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)，可用作于數(shù)據(jù)庫、緩存、消息中間件。

從官方的解釋上，我們可以知道：Redis是基于內(nèi)存，支持多種數(shù)據(jù)結(jié)構(gòu)。

從經(jīng)驗(yàn)的角度上，我們可以知道：Redis常用作于緩存。

就我個(gè)人認(rèn)為：學(xué)習(xí)一種新技術(shù)，先把握該技術(shù)整體的知識(shí)(思想)，再扣細(xì)節(jié)，這樣學(xué)習(xí)起來會(huì)比較輕松一些。所以我們先以“內(nèi)存”、“數(shù)據(jù)結(jié)構(gòu)”、“緩存”來對(duì)Redis入門。

從上面可知：Redis是基于內(nèi)存，常用作于緩存的一種技術(shù)，并且Redis存儲(chǔ)的方式是以key-value的形式。

我們可以發(fā)現(xiàn)這不就是Java的Map容器所擁有的特性嗎，那為什么還需要Redis呢？

Java實(shí)現(xiàn)的Map是本地緩存，如果有多臺(tái)實(shí)例(機(jī)器)的話，每個(gè)實(shí)例都需要各自保存一份緩存，緩存不具有一致性

Redis實(shí)現(xiàn)的是分布式緩存，如果有多臺(tái)實(shí)例(機(jī)器)的話，每個(gè)實(shí)例都共享一份緩存，緩存具有一致性。

Java實(shí)現(xiàn)的Map不是專業(yè)做緩存的，JVM內(nèi)存太大容易掛掉的。一般用做于容器來存儲(chǔ)臨時(shí)數(shù)據(jù)，緩存的數(shù)據(jù)隨著JVM銷毀而結(jié)束。Map所存儲(chǔ)的數(shù)據(jù)結(jié)構(gòu)，緩存過期機(jī)制等等是需要程序員自己手寫的。

Redis是專業(yè)做緩存的，可以用幾十個(gè)G內(nèi)存來做緩存。Redis一般用作于緩存，可以將緩存數(shù)據(jù)保存在硬盤中，Redis重啟了后可以將其恢復(fù)。原生提供豐富的數(shù)據(jù)結(jié)構(gòu)、緩存過期機(jī)制等等簡(jiǎn)單好用的功能。

參考資料：

為什么要用redis而不用map做緩存?https://segmentfault.com/q/1010000009106416

如果我們的網(wǎng)站出現(xiàn)了性能問題(訪問時(shí)間慢)，按經(jīng)驗(yàn)來說，一般是由于數(shù)據(jù)庫撐不住了。因?yàn)橐话銛?shù)據(jù)庫的讀寫都是要經(jīng)過磁盤的，而磁盤的速度可以說是相當(dāng)慢的(相對(duì)內(nèi)存來說)

科普文：讓 CPU 告訴你硬盤和網(wǎng)絡(luò)到底有多慢https://zhuanlan.zhihu.com/p/24726196

如果學(xué)過Mybaits、Hibernate的同學(xué)就可以知道，它們有一級(jí)緩存、二級(jí)緩存這樣的功能(終究來說還是本地緩存)。目的就是為了：不用每次讀取的時(shí)候，都要查一次數(shù)據(jù)庫。

有了緩存之后，我們的訪問就變成這樣了：

本文不會(huì)講述命令的使用方式，具體的如何使用可查詢API。

Redis 命令參考：http://doc.redisfans.com/

try Redis(不用安裝Redis即可體驗(yàn)Redis命令)：http://try.redis.io/

Redis支持豐富的數(shù)據(jù)結(jié)構(gòu)，常用的有string、list、hash、set、sortset這幾種。學(xué)習(xí)這些數(shù)據(jù)結(jié)構(gòu)是使用Redis的基礎(chǔ)！

"Redis is written in ANSI C"-->Redis由C語言編寫

首先還是得聲明一下，Redis的存儲(chǔ)是以key-value的形式的。Redis中的key一定是字符串，value可以是string、list、hash、set、sortset這幾種常用的。

但要值得注意的是：Redis并沒有直接使用這些數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)key-value數(shù)據(jù)庫，而是基于這些數(shù)據(jù)結(jié)構(gòu)創(chuàng)建了一個(gè)對(duì)象系統(tǒng)。

簡(jiǎn)單來說：Redis使用對(duì)象來表示數(shù)據(jù)庫中的鍵和值。每次我們?cè)赗edis數(shù)據(jù)庫中新創(chuàng)建一個(gè)鍵值對(duì)時(shí)，至少會(huì)創(chuàng)建出兩個(gè)對(duì)象。一個(gè)是鍵對(duì)象，一個(gè)是值對(duì)象。

Redis中的每個(gè)對(duì)象都由一個(gè)redisObject結(jié)構(gòu)來表示：

typedef struct redisObject{
    
    // 對(duì)象的類型
    unsigned type 4:;

    // 對(duì)象的編碼格式
    unsigned encoding:4;

    // 指向底層實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)的指針
    void * ptr;

    //.....


}robj;

簡(jiǎn)單來說就是Redis對(duì)key-value封裝成對(duì)象，key是一個(gè)對(duì)象，value也是一個(gè)對(duì)象。每個(gè)對(duì)象都有type(類型)、encoding(編碼)、ptr(指向底層數(shù)據(jù)結(jié)構(gòu)的指針)來表示。

下面我就來說一下我們Redis常見的數(shù)據(jù)類型：string、list、hash、set、sortset。它們的底層數(shù)據(jù)結(jié)構(gòu)究竟是怎么樣的！

簡(jiǎn)單動(dòng)態(tài)字符串(Simple dynamic string,SDS)

Redis中的字符串跟C語言中的字符串，是有點(diǎn)差距的。

Redis使用sdshdr結(jié)構(gòu)來表示一個(gè)SDS值：

struct sdshdr{

    // 字節(jié)數(shù)組，用于保存字符串
    char buf[];

    // 記錄buf數(shù)組中已使用的字節(jié)數(shù)量，也是字符串的長(zhǎng)度
    int len;

    // 記錄buf數(shù)組未使用的字節(jié)數(shù)量
    int free;
}

例子：

SDS與C的字符串表示比較

sdshdr數(shù)據(jù)結(jié)構(gòu)中用len屬性記錄了字符串的長(zhǎng)度。那么獲取字符串的長(zhǎng)度時(shí)，時(shí)間復(fù)雜度只需要O(1)。

SDS不會(huì)發(fā)生溢出的問題，如果修改SDS時(shí)，空間不足。先會(huì)擴(kuò)展空間，再進(jìn)行修改！(內(nèi)部實(shí)現(xiàn)了動(dòng)態(tài)擴(kuò)展機(jī)制)。

SDS可以減少內(nèi)存分配的次數(shù)(空間預(yù)分配機(jī)制)。在擴(kuò)展空間時(shí)，除了分配修改時(shí)所必要的空間，還會(huì)分配額外的空閑空間(free 屬性)。

SDS是二進(jìn)制安全的，所有SDS API都會(huì)以處理二進(jìn)制的方式來處理SDS存放在buf數(shù)組里的數(shù)據(jù)。

對(duì)于鏈表而言，我們不會(huì)陌生的了。在大學(xué)期間肯定開過數(shù)據(jù)結(jié)構(gòu)與算法課程，鏈表肯定是講過的了。在Java中Linkedxxx容器底層數(shù)據(jù)結(jié)構(gòu)也是鏈表+[xxx]的。我們來看看Redis中的鏈表是怎么實(shí)現(xiàn)的：

使用listNode結(jié)構(gòu)來表示每個(gè)節(jié)點(diǎn)：

typedef strcut listNode{

    //前置節(jié)點(diǎn)
    strcut listNode  *pre;

    //后置節(jié)點(diǎn)
    strcut listNode  *pre;

    //節(jié)點(diǎn)的值
    void  *value;

}listNode

使用listNode是可以組成鏈表了，Redis中使用list結(jié)構(gòu)來持有鏈表：

typedef struct list{

    //表頭結(jié)點(diǎn)
    listNode  *head;

    //表尾節(jié)點(diǎn)
    listNode  *tail;

    //鏈表長(zhǎng)度
    unsigned long len;

    //節(jié)點(diǎn)值復(fù)制函數(shù)
    void *(*dup) (viod *ptr);

    //節(jié)點(diǎn)值釋放函數(shù)
    void  (*free) (viod *ptr);

    //節(jié)點(diǎn)值對(duì)比函數(shù)
    int (*match) (void *ptr,void *key);

}list

具體的結(jié)構(gòu)如圖：

Redis的鏈表有以下特性：

無環(huán)雙向鏈表

獲取表頭指針，表尾指針，鏈表節(jié)點(diǎn)長(zhǎng)度的時(shí)間復(fù)雜度均為O(1)

鏈表使用void *指針來保存節(jié)點(diǎn)值，可以保存各種不同類型的值

聲明：《Redis設(shè)計(jì)與實(shí)現(xiàn)》里邊有“字典”這么一個(gè)概念，我個(gè)人認(rèn)為還是直接叫哈希表比較通俗易懂。從代碼上看：“字典”也是在哈希表基礎(chǔ)上再抽象了一層而已。

在Redis中，key-value的數(shù)據(jù)結(jié)構(gòu)底層就是哈希表來實(shí)現(xiàn)的。對(duì)于哈希表來說，我們也并不陌生。在Java中，哈希表實(shí)際上就是數(shù)組+鏈表的形式來構(gòu)建的。下面我們來看看Redis的哈希表是怎么構(gòu)建的吧。

在Redis里邊，哈希表使用dictht結(jié)構(gòu)來定義：

    typedef struct dictht{
        
        //哈希表數(shù)組
        dictEntry **table;  
    
        //哈希表大小
        unsigned long size;    
    
        //哈希表大小掩碼，用于計(jì)算索引值
        //總是等于size-1
        unsigned long sizemark;     
    
        //哈希表已有節(jié)點(diǎn)數(shù)量
        unsigned long used;
         
    }dictht

我們下面繼續(xù)寫看看哈希表的節(jié)點(diǎn)是怎么實(shí)現(xiàn)的吧：

    typedef struct dictEntry {
        
        //鍵
        void *key;
    
        //值
        union {
            void *value;
            uint64_tu64;
            int64_ts64;
        }v;    
    
        //指向下個(gè)哈希節(jié)點(diǎn)，組成鏈表
        struct dictEntry *next;
    
    }dictEntry;

從結(jié)構(gòu)上看，我們可以發(fā)現(xiàn)：Redis實(shí)現(xiàn)的哈希表和Java中實(shí)現(xiàn)的是類似的。只不過Redis多了幾個(gè)屬性來記錄常用的值：sizemark(掩碼)、used(已有的節(jié)點(diǎn)數(shù)量)、size(大小)。

同樣地，Redis為了更好的操作，對(duì)哈希表往上再封裝了一層(參考上面的Redis實(shí)現(xiàn)鏈表)，使用dict結(jié)構(gòu)來表示：

typedef struct dict {

    //類型特定函數(shù)
    dictType *type;

    //私有數(shù)據(jù)
    void *privdata;
  
    //哈希表
    dictht ht[2];

    //rehash索引
    //當(dāng)rehash不進(jìn)行時(shí)，值為-1
    int rehashidx;  

}dict;


//-----------------------------------

typedef struct dictType{

    //計(jì)算哈希值的函數(shù)
    unsigned int (*hashFunction)(const void * key);

    //復(fù)制鍵的函數(shù)
    void *(*keyDup)(void *private, const void *key);
 
    //復(fù)制值得函數(shù)
    void *(*valDup)(void *private, const void *obj);  

    //對(duì)比鍵的函數(shù)
    int (*keyCompare)(void *privdata , const void *key1, const void *key2)

    //銷毀鍵的函數(shù)
    void (*keyDestructor)(void *private, void *key);
 
    //銷毀值的函數(shù)
    void (*valDestructor)(void *private, void *obj);  

}dictType

所以，最后我們可以發(fā)現(xiàn)，Redis所實(shí)現(xiàn)的哈希表最后的數(shù)據(jù)結(jié)構(gòu)是這樣子的：

從代碼實(shí)現(xiàn)和示例圖上我們可以發(fā)現(xiàn)，Redis中有兩個(gè)哈希表：

ht[0]：用于存放真實(shí)的key-vlaue數(shù)據(jù)

ht[1]：用于擴(kuò)容(rehash)

Redis中哈希算法和哈希沖突跟Java實(shí)現(xiàn)的差不多，它倆差異就是：

Redis哈希沖突時(shí)：是將新節(jié)點(diǎn)添加在鏈表的表頭。

JDK1.8后，Java在哈希沖突時(shí)：是將新的節(jié)點(diǎn)添加到鏈表的表尾。

下面來具體講講Redis是怎么rehash的，因?yàn)槲覀儚纳厦婵梢悦黠@地看到，Redis是專門使用一個(gè)哈希表來做rehash的。這跟Java一次性直接rehash是有區(qū)別的。

在對(duì)哈希表進(jìn)行擴(kuò)展或者收縮操作時(shí)，reash過程并不是一次性地完成的，而是漸進(jìn)式地完成的。

Redis在rehash時(shí)采取漸進(jìn)式的原因：數(shù)據(jù)量如果過大的話，一次性rehash會(huì)有龐大的計(jì)算量，這很可能導(dǎo)致服務(wù)器一段時(shí)間內(nèi)停止服務(wù)。

Redis具體是rehash時(shí)這么干的：

(1:在字典中維持一個(gè)索引計(jì)數(shù)器變量rehashidx，并將設(shè)置為0，表示rehash開始。

(2:在rehash期間每次對(duì)字典進(jìn)行增加、查詢、刪除和更新操作時(shí)，除了執(zhí)行指定命令外；還會(huì)將ht[0]中rehashidx索引上的值rehash到ht[1]，操作完成后rehashidx+1。

(3:字典操作不斷執(zhí)行，最終在某個(gè)時(shí)間點(diǎn)，所有的鍵值對(duì)完成rehash，這時(shí)將rehashidx設(shè)置為-1，表示rehash完成

(4:在漸進(jìn)式rehash過程中，字典會(huì)同時(shí)使用兩個(gè)哈希表ht[0]和ht[1]，所有的更新、刪除、查找操作也會(huì)在兩個(gè)哈希表進(jìn)行。例如要查找一個(gè)鍵的話，服務(wù)器會(huì)優(yōu)先查找ht[0]，如果不存在，再查找ht[1]，諸如此類。此外當(dāng)執(zhí)行新增操作時(shí)，新的鍵值對(duì)一律保存到ht[1]，不再對(duì)ht[0]進(jìn)行任何操作，以保證ht[0]的鍵值對(duì)數(shù)量只減不增，直至變?yōu)榭毡怼?/p> 2.4跳躍表(shiplist)

跳躍表(shiplist)是實(shí)現(xiàn)sortset(有序集合)的底層數(shù)據(jù)結(jié)構(gòu)之一！

跳躍表可能對(duì)于大部分人來說不太常見，之前我在學(xué)習(xí)的時(shí)候發(fā)現(xiàn)了一篇不錯(cuò)的文章講跳躍表的，建議大家先去看完下文再繼續(xù)回來閱讀：

漫畫算法：什么是跳躍表？http://blog.jobbole.com/111731/

Redis的跳躍表實(shí)現(xiàn)由zskiplist和zskiplistNode兩個(gè)結(jié)構(gòu)組成。其中zskiplist保存跳躍表的信息(表頭，表尾節(jié)點(diǎn)，長(zhǎng)度)，zskiplistNode則表示跳躍表的節(jié)點(diǎn)。

按照慣例，我們來看看zskiplistNode跳躍表節(jié)點(diǎn)的結(jié)構(gòu)是怎么樣的：

typeof struct zskiplistNode {
        // 后退指針
        struct zskiplistNode *backward;
        // 分值
        double score;
        // 成員對(duì)象
        robj *obj;
        // 層
        struct zskiplistLevel {
                // 前進(jìn)指針
                struct zskiplistNode *forward;
                // 跨度
                unsigned int span;
        } level[];
} zskiplistNode;

zskiplistNode的對(duì)象示例圖(帶有不同層高的節(jié)點(diǎn))：

示例圖如下：

zskiplist的結(jié)構(gòu)如下：

typeof struct zskiplist {
        // 表頭節(jié)點(diǎn)，表尾節(jié)點(diǎn)
        struct skiplistNode *header,*tail;
        // 表中節(jié)點(diǎn)數(shù)量
        unsigned long length;
        // 表中最大層數(shù)
        int level;
} zskiplist;

最后我們整個(gè)跳躍表的示例圖如下：

整數(shù)集合是set(集合)的底層數(shù)據(jù)結(jié)構(gòu)之一。當(dāng)一個(gè)set(集合)只包含整數(shù)值元素，并且元素的數(shù)量不多時(shí)，Redis就會(huì)采用整數(shù)集合(intset)作為set(集合)的底層實(shí)現(xiàn)。

整數(shù)集合(intset)保證了元素是不會(huì)出現(xiàn)重復(fù)的，并且是有序的(從小到大排序)，intset的結(jié)構(gòu)是這樣子的：

typeof struct intset {
        // 編碼方式
        unit32_t encoding;
        // 集合包含的元素?cái)?shù)量
        unit32_t lenght;
        // 保存元素的數(shù)組
        int8_t contents[];
} intset;

intset示例圖：

說明：雖然intset結(jié)構(gòu)將contents屬性聲明為int8_t類型的數(shù)組，但實(shí)際上contents數(shù)組并不保存任何int8_t類型的值，contents數(shù)組的真正類型取決于encoding屬性的值：

INTSET_ENC_INT16

INTSET_ENC_INT32

INTSET_ENC_INT64

從編碼格式的名字我們就可以知道，16,32,64編碼對(duì)應(yīng)能存放的數(shù)字范圍是不一樣的。16明顯最少，64明顯最大。

如果本來是INTSET_ENC_INT16的編碼，想要存放大于INTSET_ENC_INT16編碼能存放的整數(shù)值，此時(shí)就得編碼升級(jí)(從16升級(jí)成32或者64)。步驟如下：

1）根據(jù)新元素類型拓展整數(shù)集合底層數(shù)組的空間并為新元素分配空間。

2）將底層數(shù)組現(xiàn)有的所以元素都轉(zhuǎn)換成與新元素相同的類型，并將類型轉(zhuǎn)換后的元素放到正確的位上，需要維持底層數(shù)組的有序性質(zhì)不變。

3）將新元素添加到底層數(shù)組。

另外一提：只支持升級(jí)操作，并不支持降級(jí)操作。

壓縮列表(ziplist)是list和hash的底層實(shí)現(xiàn)之一。如果list的每個(gè)都是小整數(shù)值，或者是比較短的字符串，壓縮列表(ziplist)作為list的底層實(shí)現(xiàn)。

壓縮列表(ziplist)是Redis為了節(jié)約內(nèi)存而開發(fā)的，是由一系列的特殊編碼的連續(xù)內(nèi)存塊組成的順序性數(shù)據(jù)結(jié)構(gòu)。

壓縮列表結(jié)構(gòu)圖例如下：

下面我們看看節(jié)點(diǎn)的結(jié)構(gòu)圖：

壓縮列表從表尾節(jié)點(diǎn)倒序遍歷，首先指針通過zltail偏移量指向表尾節(jié)點(diǎn)，然后通過指向節(jié)點(diǎn)記錄的前一個(gè)節(jié)點(diǎn)的長(zhǎng)度依次向前遍歷訪問整個(gè)壓縮列表。

再次看回這張圖，覺不覺得就很好理解了？

在上面的圖我們知道string類型有三種編碼格式：

int：整數(shù)值，這個(gè)整數(shù)值可以使用long類型來表示

如果是浮點(diǎn)數(shù)，那就用embstr或者raw編碼。具體用哪個(gè)就看這個(gè)數(shù)的長(zhǎng)度了

embstr：字符串值，這個(gè)字符串值的長(zhǎng)度小于39字節(jié)

raw：字符串值，這個(gè)字符串值的長(zhǎng)度大于39字節(jié)

embstr和raw的區(qū)別：

raw分配內(nèi)存和釋放內(nèi)存的次數(shù)是兩次，embstr是一次

embstr編碼的數(shù)據(jù)保存在一塊連續(xù)的內(nèi)存里面

編碼之間的轉(zhuǎn)換：

int類型如果存的不再是一個(gè)整數(shù)值，則會(huì)從int轉(zhuǎn)成raw

embstr是只讀的，在修改的時(shí)候回從embstr轉(zhuǎn)成raw

在上面的圖我們知道list類型有兩種編碼格式：

ziplist：字符串元素的長(zhǎng)度都小于64個(gè)字節(jié)&&總數(shù)量少于512個(gè)

linkedlist：字符串元素的長(zhǎng)度大于64個(gè)字節(jié)||總數(shù)量大于512個(gè)

ziplist編碼的列表結(jié)構(gòu)：

    redis > RPUSH numbers 1 "three" 5
    (integer) 3 

linkedlist編碼的列表結(jié)構(gòu)：

編碼之間的轉(zhuǎn)換：

原本是ziplist編碼的，如果保存的數(shù)據(jù)長(zhǎng)度太大或者元素?cái)?shù)量過多，會(huì)轉(zhuǎn)換成linkedlist編碼的。

在上面的圖我們知道hash類型有兩種編碼格式：

ziplist：key和value的字符串長(zhǎng)度都小于64字節(jié)&&鍵值對(duì)總數(shù)量小于512

hashtable：key和value的字符串長(zhǎng)度大于64字節(jié)||鍵值對(duì)總數(shù)量大于512

ziplist編碼的哈希結(jié)構(gòu)：

hashtable編碼的哈希結(jié)構(gòu)：

編碼之間的轉(zhuǎn)換：

原本是ziplist編碼的，如果保存的數(shù)據(jù)長(zhǎng)度太大或者元素?cái)?shù)量過多，會(huì)轉(zhuǎn)換成hashtable編碼的。

在上面的圖我們知道set類型有兩種編碼格式：

intset：保存的元素全都是整數(shù)&&總數(shù)量小于512

hashtable：保存的元素不是整數(shù)||總數(shù)量大于512

intset編碼的集合結(jié)構(gòu)：

hashtable編碼的集合結(jié)構(gòu)：

編碼之間的轉(zhuǎn)換：

原本是intset編碼的，如果保存的數(shù)據(jù)不是整數(shù)值或者元素?cái)?shù)量大于512，會(huì)轉(zhuǎn)換成hashtable編碼的。

在上面的圖我們知道set類型有兩種編碼格式：

ziplist：元素長(zhǎng)度小于64&&總數(shù)量小于128

skiplist：元素長(zhǎng)度大于64||總數(shù)量大于128

ziplist編碼的有序集合結(jié)構(gòu)：

skiplist編碼的有序集合結(jié)構(gòu)：

有序集合(sortset)對(duì)象同時(shí)采用skiplist和哈希表來實(shí)現(xiàn)：

skiplist能夠達(dá)到插入的時(shí)間復(fù)雜度為O(logn)，根據(jù)成員查分值的時(shí)間復(fù)雜度為O(1)

編碼之間的轉(zhuǎn)換：

原本是ziplist編碼的，如果保存的數(shù)據(jù)長(zhǎng)度大于64或者元素?cái)?shù)量大于128，會(huì)轉(zhuǎn)換成skiplist編碼的。

(1：服務(wù)器在執(zhí)行某些命令的時(shí)候，會(huì)先檢查給定的鍵的類型能否執(zhí)行指定的命令。

比如我們的數(shù)據(jù)結(jié)構(gòu)是sortset，但你使用了list的命令。這是不對(duì)的，服務(wù)器會(huì)檢查一下我們的數(shù)據(jù)結(jié)構(gòu)是什么才會(huì)進(jìn)一步執(zhí)行命令

(2：Redis的對(duì)象系統(tǒng)帶有引用計(jì)數(shù)實(shí)現(xiàn)的內(nèi)存回收機(jī)制。

對(duì)象不再被使用的時(shí)候，對(duì)象所占用的內(nèi)存會(huì)釋放掉

(3：Redis會(huì)共享值為0到9999的字符串對(duì)象

(4：對(duì)象會(huì)記錄自己的最后一次被訪問時(shí)間，這個(gè)時(shí)間可以用于計(jì)算對(duì)象的空轉(zhuǎn)時(shí)間。

本文主要講了一下Redis常用的數(shù)據(jù)結(jié)構(gòu)，以及這些數(shù)據(jù)結(jié)構(gòu)的底層設(shè)計(jì)是怎么樣的。整體來說不會(huì)太難，因?yàn)檫@些數(shù)據(jù)結(jié)構(gòu)我們?cè)趯W(xué)習(xí)的過程中多多少少都接觸過了，《Redis設(shè)計(jì)與實(shí)現(xiàn)》這本書寫得也足夠通俗易懂。

至于我們?cè)谑褂玫臅r(shí)候挑選哪些數(shù)據(jù)結(jié)構(gòu)作為存儲(chǔ)，可以簡(jiǎn)單看看：

string-->簡(jiǎn)單的key-value

list-->有序列表(底層是雙向鏈表)-->可做簡(jiǎn)單隊(duì)列

set-->無序列表(去重)-->提供一系列的交集、并集、差集的命令

hash-->哈希表-->存儲(chǔ)結(jié)構(gòu)化數(shù)據(jù)

sortset-->有序集合映射(member-score)-->排行榜

如果大家有更好的理解方式或者文章有錯(cuò)誤的地方還請(qǐng)大家不吝在評(píng)論區(qū)留言，大家互相學(xué)習(xí)交流~~~

參考博客：

Redis簡(jiǎn)明教程http://bridgeforyou.cn/2018/05/19/Redis-Tutorial/

五旬大爺教你一窺redis之謎https://zhuanlan.zhihu.com/p/34762100

參考資料：

《Redis設(shè)計(jì)與實(shí)現(xiàn)》

《Redis實(shí)戰(zhàn)》

一個(gè)堅(jiān)持原創(chuàng)的Java技術(shù)公眾號(hào)：Java3y，歡迎大家關(guān)注

原創(chuàng)技術(shù)文章導(dǎo)航：

文章的目錄導(dǎo)航(腦圖+海量視頻資源)：https://github.com/ZhongFuCheng3y/3y