redis的5種數(shù)據(jù)類型以及其底層實(shí)現(xiàn)

redis 是KV(key-value pair)存儲(chǔ)，不管是K還是V，底層都是對(duì)象（object 組成）的，其中K是一個(gè)字符串對(duì)象(string object)，V 分別有我們常聽(tīng)說(shuō)的5種數(shù)據(jù)類型，分別是字符串(String)、列表(List)、哈希(Hash)、集合(Set)、有序集合(Zset)。不過(guò)是K還是V，底層都是用 redisObject 數(shù)據(jù)結(jié)構(gòu)表示，如下：

struct redisObject {
    unsigned type:4;//4 bit
    unsigned encoding:4;//4 bit
    //24 bit=3byte
    unsigned lru:LRU_BITS; /* LRU time (relative to global lru_clock) or
                            * LFU data (least significant 8 bits frequency
                            * and most significant 16 bits access time). */
    
    int refcount;//4byte
    void *ptr;//8type
};

其中 type 表示對(duì)象的類型，分別有 REDIS_STRING(字符串)，REDIS_LIST(列表)，REDIS_HASH(哈希)，REDIS_SET(集合對(duì)象)，REDIS_ZSET(有序集合)；

encoding 字段表示底層的編碼實(shí)現(xiàn)，因?yàn)槊糠N數(shù)據(jù)類型其實(shí)底層實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)至少有2種，根據(jù)不同的條件選擇不同的數(shù)據(jù)結(jié)構(gòu)，而且會(huì)根據(jù)條件的變化升級(jí)或者更換數(shù)據(jù)結(jié)構(gòu)，最終的目的是盡可能壓縮存儲(chǔ)和提升效率。具體每個(gè)數(shù)據(jù)類型的編碼以及數(shù)據(jù)結(jié)構(gòu)下面會(huì)詳解。

ptr: 指向的是底層實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)

5種數(shù)據(jù)類型對(duì)應(yīng)的底層編碼結(jié)構(gòu)如下圖：

字符串(String)

如上圖1所示，數(shù)據(jù)類型為String的底層編碼有3種：INT，EMBSTR，RAW。

當(dāng) value的值是整數(shù)時(shí)，采用INT編碼。

當(dāng) value 非整數(shù)時(shí)，小于等于44字節(jié)時(shí)，采用 EMBSTR 編碼，大于44字節(jié)時(shí)采用RAW編碼，如下：

localhost:6379> set test "01234567890123456789012345678901234567890123"
OK
localhost:6379> OBJECT ENCODING test
"embstr"
localhost:6379> set test "012345678901234567890123456789012345678901234"
OK
localhost:6379> OBJECT ENCODING test
"raw"

EMBSTR 編碼 VS RAW編碼
EMBSTR 編碼和 RAW 編碼底層實(shí)現(xiàn)都是 redisObject 結(jié)構(gòu) + SDS 結(jié)構(gòu)
小于等于44字節(jié)用 EMBSTR編碼，對(duì)比RAW有什么優(yōu)勢(shì)：
1. 其實(shí)EMBSTR和RAW編碼都是 redisObject 結(jié)構(gòu) + SDS 結(jié)構(gòu)，只是 embstr 編碼只需要1次內(nèi)存分配（redisObject和SDS結(jié)構(gòu)是連續(xù)的內(nèi)存），而 RAW 編碼需要分別為redisObject和 SDS 進(jìn)行分配，內(nèi)存一般不連續(xù)，對(duì)比EMBSTR，RAW多一次內(nèi)存分配
2. 內(nèi)存釋放時(shí)，EMBSTR 比 RAW 少一次調(diào)用內(nèi)存釋放函數(shù)
3. EMBSTR 編碼分配的內(nèi)存的連續(xù)的，可以更好利用CPU緩存提升性能。
為啥是44字節(jié)

答：因?yàn)閮?nèi)存分配函數(shù)最大1次分配是64字節(jié)，除開(kāi)redisObject 占用16字節(jié)、SDS 結(jié)構(gòu)3個(gè)字節(jié)、字符串結(jié)尾字符\0的1個(gè)字節(jié)，剩余最大：64-16-3-1=44字節(jié)。

SDS

SDS：simple dynamic string，redis 采用這個(gè)數(shù)據(jù)結(jié)構(gòu)來(lái)代替 C 字符串（使用N+1的字符數(shù)組表示長(zhǎng)度為N的字符串，最后一個(gè)字符是空字符'\0') ，SDS的結(jié)構(gòu)圖如下：

sds

len: 字符串長(zhǎng)度。可通過(guò) O(1) 復(fù)雜度獲取字符串長(zhǎng)度，不像C 字符串需要遍歷所有原素、時(shí)間復(fù)雜度 O(N) 來(lái)獲取

alloc: 分配給字符串的空間。用于擴(kuò)容判斷，當(dāng) alloc - len 的空間不滿足新字符串空間要求，進(jìn)行擴(kuò)容，擴(kuò)容策略如上圖。

flags: SDS的類型，redis 3.2版本后，定義了 5 種不同的類型結(jié)構(gòu)，為了根據(jù)最小適用原則選擇更節(jié)省內(nèi)存的結(jié)構(gòu),如下:

struct __attribute__ ((__packed__)) sdshdr5 {
    unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len; /* used */
    uint8_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr16 {
    uint16_t len; /* used */
    uint16_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr32 {
    uint32_t len; /* used */
    uint32_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr64 {
    uint64_t len; /* used */
    uint64_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};

buf[]: 字符數(shù)組，用于存儲(chǔ)實(shí)際數(shù)據(jù)。對(duì)比 C字符串，該數(shù)組可以存儲(chǔ)任意字符，不像 C 字符串限制不能存儲(chǔ) '\0' 字符。

總結(jié) redis 在很多場(chǎng)景使用 SDS 代替 C 字符串來(lái)表示字符串的原因：

SDS 獲取字符串長(zhǎng)度是O(1)，C字符串是 O(N)，性能更高
SDS API 更加安全。C 字符串在字符串拼接時(shí)，需依賴程序員確?？臻g足夠，如果空間不足又忘記分配，就會(huì)出現(xiàn)緩沖區(qū)溢出，而 SDS 通過(guò)將確?？臻g足夠封裝到API里面（由 redis內(nèi)部判斷是否需要擴(kuò)容），不需程序員管理，更加安全。
在修改字符串時(shí)， SDS 的內(nèi)存重分配次數(shù)少于 C 字符串。因?yàn)镾DS使用空間預(yù)分配（分配多余的空間）和惰性空間釋放（字符長(zhǎng)度縮短時(shí)，并不釋放無(wú)用字符占用的空間，后續(xù)使用直接替代即可）來(lái)減少內(nèi)存重新分配，提升效率，有點(diǎn)空間換時(shí)間意思。
存儲(chǔ)的數(shù)據(jù)類型更廣。C 字符串只適合存儲(chǔ)文本數(shù)據(jù)，不能存儲(chǔ)圖片、音視頻等二進(jìn)制數(shù)據(jù)，而 SDS 可以。

列表(List)

Redis 3.2版本之前，List 的編碼有2種：分別是 ZIPLIST（壓縮列表）和 LINKEDLIST(雙向鏈表)。當(dāng) LIST 中每個(gè)字符串長(zhǎng)度都小于64字節(jié)并且列表的元素個(gè)數(shù)小于512個(gè)時(shí)，采用 ZIPLIST 編碼，否則采用 LINKEDLIST 編碼。

大于等于3.2 版本后，結(jié)合 ZIPLIST 和 LINKELIST的優(yōu)缺點(diǎn)，誕生了快速列表（QUICKLIST），其實(shí)就是 ZIPLIST + LINKEDLIST 結(jié)合體。

ZIPLIST（壓縮列表）

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

ziplist

ziplist主要屬性

zlbtyes: 整個(gè)列表占用字節(jié)數(shù)

zltail_offset: 最后一個(gè)元素的偏移量，為了支持反向遍歷

zlength: 元素個(gè)數(shù)。

entry列表：存儲(chǔ)具體數(shù)據(jù)的節(jié)點(diǎn)

zlend: 結(jié)束標(biāo)識(shí)。

entry主要屬性

prelen: 前一個(gè)節(jié)點(diǎn)長(zhǎng)度，以1個(gè)字節(jié)或者5個(gè)字節(jié)，根據(jù)上個(gè)節(jié)點(diǎn)的長(zhǎng)度是否超過(guò)254字節(jié)來(lái)選擇

encoding: 記錄content的類型和長(zhǎng)度，通過(guò)前面2bit記錄content類型，后面的bit記錄長(zhǎng)度。具體：前面2bit是 00、01或10時(shí)，表示字節(jié)數(shù)組編碼（content保存字節(jié)數(shù)組），剩余其他bit表示content長(zhǎng)度；前面bit是11，表示整數(shù)編碼，content存的是整數(shù)，剩余的其他bit表示整數(shù)的類型和長(zhǎng)度。

content: 存儲(chǔ)實(shí)際的內(nèi)容，可以是字節(jié)數(shù)組或者整數(shù)，類型有encoding決定

ZIPLIST的優(yōu)缺點(diǎn)

優(yōu)點(diǎn)

內(nèi)存空間連續(xù)、數(shù)據(jù)結(jié)構(gòu)緊湊（對(duì)比 LINKEDLIST 沒(méi)有前后指針的占用），占用內(nèi)存更小，內(nèi)存使用率更高
內(nèi)存空間連續(xù)，遍歷時(shí)可以利用CPU緩存，遍歷效率更高

缺點(diǎn)：

新增和修改時(shí)，會(huì)重新分配內(nèi)存，還有可能引起 級(jí)聯(lián)更新問(wèn)題 （因?yàn)楦乱粋€(gè)元素，導(dǎo)致后續(xù)元素都需要進(jìn)行更新。如果上個(gè)自己小于254字節(jié)，prelen會(huì)用一個(gè)字節(jié)表示，否則5字節(jié)，如果某個(gè)小于254字節(jié)的entry修改后大于等于254字節(jié)，那么下個(gè)entry節(jié)點(diǎn)的prelen屬性從1個(gè)字節(jié)擴(kuò)展到5個(gè)字節(jié)，而且如果擴(kuò)展后又變成超過(guò)254字節(jié)，那么后面的節(jié)點(diǎn)也要進(jìn)行更新，最極端情況是每個(gè)節(jié)點(diǎn)都是接近254字節(jié)，修改頭部某一個(gè)導(dǎo)致超過(guò)254，導(dǎo)致后面所有字節(jié)都需要進(jìn)行更新，不過(guò)這種概率很低），所以不太合適存儲(chǔ)過(guò)多元素。針對(duì)ziplist的缺點(diǎn)，后續(xù)的版本后引入了listpack（緊湊列表）來(lái)解決ziplist的級(jí)聯(lián)更新問(wèn)題。

LINKEDLIST（雙向鏈表）

LINKEDLIST 其實(shí)就是一個(gè)雙向鏈表，如下圖

linkedlist

優(yōu)點(diǎn)

獲取頭尾節(jié)點(diǎn)時(shí)間復(fù)雜度O(1)
獲取上個(gè)和下個(gè)節(jié)點(diǎn)時(shí)間復(fù)雜度O(1)

缺點(diǎn)：

每個(gè)節(jié)點(diǎn)內(nèi)存不連續(xù)，不能很好利用CPU緩存
每個(gè)節(jié)點(diǎn)都需要存儲(chǔ)上個(gè)和下個(gè)節(jié)點(diǎn)的指針，占用內(nèi)存相對(duì)ZIPLIST多

QUICKLIST（快速列表）

redis 3.2 版本后，結(jié)合 ZIPLIST 和 LINKEDLIST 的優(yōu)缺點(diǎn)，設(shè)計(jì)出了 QUICKLIST。

如下圖

quicklist

如圖所示，其實(shí)整體還是 LINKEDLIST, 只是每個(gè)節(jié)點(diǎn)的VALUE底層不再是SDS，而是ZIPLIST?？梢岳蒙蟴iplist的優(yōu)點(diǎn)，同時(shí)，由于每個(gè)節(jié)點(diǎn)存儲(chǔ)的ziplist長(zhǎng)度相對(duì)全部用ziplist存儲(chǔ)要短，級(jí)聯(lián)更新的問(wèn)題會(huì)得到改善。

哈希(Hash)

哈希的編碼實(shí)現(xiàn)有2種，一個(gè)是ZIPLIST或LISTPACK（redis 7版本用這個(gè)替代ziplist），一個(gè)是HT(哈希表)。

ZIPLIST編碼結(jié)構(gòu)上面已經(jīng)講解了，不過(guò)在這里使用2個(gè)相鄰的entry來(lái)存儲(chǔ)kv，前面一個(gè)存儲(chǔ)k，后面一個(gè)存儲(chǔ)v. 如下圖：

hash_ziplist

LISTPACK(壓縮列表)

listpack

如上圖，對(duì)比ziplist，大部分幾乎完全一樣，主要有下面幾點(diǎn)不同：

LISTPACK 去掉了 ztail_offset字段
entry結(jié)果不在存儲(chǔ)上個(gè)節(jié)點(diǎn)長(zhǎng)度，而且通過(guò)lenth存儲(chǔ)本節(jié)點(diǎn)的長(zhǎng)度，這個(gè)是解決級(jí)聯(lián)更新的關(guān)鍵點(diǎn)。具體原因：ziplist出現(xiàn)級(jí)聯(lián)更新主要是因?yàn)榇娣派蟼€(gè)節(jié)點(diǎn)的 prelen 字段可能是1字節(jié)或者5字節(jié)，如果上個(gè)節(jié)點(diǎn)變成超過(guò)254字節(jié)，會(huì)影響到當(dāng)前節(jié)點(diǎn)的 prelen 字段從1字節(jié)改成5字節(jié)，后續(xù)的節(jié)點(diǎn)也會(huì)出現(xiàn)類似的級(jí)聯(lián)更新。而listpack的設(shè)計(jì)去掉了這個(gè)字段，而且通過(guò)lenth存儲(chǔ)本字節(jié)長(zhǎng)度，所以不會(huì)影響后續(xù)的節(jié)點(diǎn)，也就不會(huì)出現(xiàn)級(jí)聯(lián)更新的問(wèn)題。
encoding的設(shè)計(jì)更加復(fù)雜和緊湊，以節(jié)省內(nèi)存。主要是利用前面的幾bit表示編碼類型，剩余的bit表示content數(shù)據(jù)字段的長(zhǎng)度或者存儲(chǔ)實(shí)際的數(shù)值（比如整數(shù)，避免使用content存儲(chǔ)，以節(jié)省內(nèi)存）。下面是幾個(gè)例子：
- 0xxxxxxx 表示非負(fù)小整數(shù)，可以表示 0~127。前面0表示編碼，剩余的幾bit表示content數(shù)據(jù)的長(zhǎng)度
- 11110001 aaaaaaaa bbbbbbbb 表示 2 字節(jié)有符號(hào)整數(shù)。前一個(gè)字節(jié)表示編碼類型，后面存儲(chǔ)實(shí)際的整數(shù)，content為空

HT編碼（HASHTABLE、哈希表）

其實(shí)跟java的hashmap類似，主要是數(shù)組+鏈表（數(shù)組的每個(gè)元素）組成，不過(guò)考慮擴(kuò)容時(shí)性能，使用2個(gè)hashtable來(lái)是實(shí)現(xiàn)漸進(jìn)式rehash。

hashtable

如上圖，HT主要屬性如下：

table: 一個(gè)dictEntry數(shù)組，每個(gè)數(shù)組元素是一個(gè)鏈表。添加kv時(shí)，會(huì)對(duì)key進(jìn)行hash得到數(shù)組下標(biāo)，如果沒(méi)有元素直接插入，如果有存在的元素，則通過(guò)鏈表進(jìn)行串聯(lián)起來(lái)。
size: dictEntry數(shù)組長(zhǎng)度
sizemark：哈希表大小掩碼，用于計(jì)算數(shù)組下標(biāo)
used: 哈希表key的個(gè)數(shù)

疑問(wèn)：為啥使用2個(gè)hashtable來(lái)實(shí)現(xiàn)？

答：如果使用一個(gè)hashtable實(shí)現(xiàn)，在擴(kuò)容時(shí)，需針對(duì)所有數(shù)據(jù)進(jìn)行遷移，耗時(shí)較大，如果數(shù)據(jù)量比較大，影響響應(yīng)命令的耗時(shí)，因此設(shè)計(jì)2個(gè)hashtable時(shí)，可以某個(gè)下標(biāo)的鏈表，無(wú)需要遷移所有元素，可以更快響應(yīng)，減少阻塞。具體遷移步驟大概如下（ht[0]的容量到達(dá)擴(kuò)容條件時(shí)）：

為 ht[1] 分配空間
維護(hù)一個(gè)索引計(jì)數(shù)變量 rehashidx，初始為0，在rehash時(shí)，將ht[0]在 rehashidx 索引上的所有數(shù)據(jù)rehash到 ht[1]，遷移完 rehashidx += 1。同時(shí)，rehash期間，添加元素只會(huì)在ht[1]添加，保證待遷移的數(shù)據(jù)只會(huì)越來(lái)越少。
遷移完成后，釋放 ht[0] 空間，并且將 ht[1] 替換為 ht[0]

hashtable擴(kuò)容條件：

服務(wù)器沒(méi)有執(zhí)行BGSAVE和BGREWRITEAOF命令，并且哈希表負(fù)載因子大于等于1

服務(wù)器正在執(zhí)行BGSAVE和BGREWRITEAOF命令，負(fù)載因子大于等于5

負(fù)載因子：已保存的數(shù)據(jù)/哈希表大小(ht[0].used/ht[0].size)

PS: 如果遷移中時(shí)，沒(méi)有后續(xù)命令觸發(fā)剩余的元素遷移，會(huì)一直處于遷移狀態(tài)嗎？redis通過(guò)定時(shí)任務(wù)來(lái)對(duì)遷移中的字典進(jìn)行遷移，保證不然字典長(zhǎng)時(shí)間處于遷移中狀態(tài)。

集合(Set)

Set 的編碼有2種：INTSET 和 HASHTABLE(HT)。當(dāng)集合中所有的元素都是整數(shù)，并且個(gè)數(shù)不超過(guò)512時(shí)，采用 INTSET 編碼，否則采用 HASHTABLE(HT) 編碼（上面已經(jīng)講解過(guò)，這里不再展開(kāi)）。

INTSET編碼

intset

如上圖，特別說(shuō)明的是encoding字段，它會(huì)根據(jù)目前元素的最大值選擇最小的編碼類型，以節(jié)省內(nèi)存。如果有新的最大值，當(dāng)前的編碼類型不滿足時(shí)，會(huì)進(jìn)行升級(jí)，但是升級(jí)后不再支持降級(jí)。

有序集合(ZSet)

Zset和set都是不能存儲(chǔ)重復(fù)值的集合，不過(guò)Zset通過(guò)score屬性來(lái)對(duì)元素進(jìn)行排序，可以根據(jù)score進(jìn)行范圍查詢等操作，非常適用排行榜等場(chǎng)景。

Zset的編碼實(shí)現(xiàn)有2種：SKIPLIST(跳躍列表)+ HT(哈希表) 結(jié)合、ZIPLIST(壓縮列表，6版本之前)或LISTPACT(6版本之后) 。當(dāng)有序集合的元素個(gè)數(shù)小于128，每個(gè)元素都小于64字節(jié)時(shí)，采用ZIPLIST編碼，否則采用 ZIPLIST(壓縮列表)+ HT(哈希表) 結(jié)合的編碼。LISTPACK編碼上面已經(jīng)講解過(guò)，不做講解。

ZIPLIST的編碼跟上面講的一樣，不過(guò)一個(gè)zset元素+分值用2個(gè)entry節(jié)點(diǎn)進(jìn)行存儲(chǔ)，其中一個(gè)存儲(chǔ)元素值，另外一個(gè)存儲(chǔ)分值score，并且按照score從小到達(dá)大進(jìn)行排序。

zset_ziplist

SKIPLIST(跳躍列表)

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

skiplist

源碼結(jié)構(gòu)( tag 6.2.8)：

typedef struct zskiplistNode {
    sds ele;
    double score;
    struct zskiplistNode *backward;
    struct zskiplistLevel {
        struct zskiplistNode *forward;
        unsigned long span;
    } level[];
} zskiplistNode;

typedef struct zskiplist {
    struct zskiplistNode *header, *tail;
    unsigned long length;
    int level;
} zskiplist;

typedef struct zset {
    dict *dict;
    zskiplist *zsl;
} zset;

從結(jié)構(gòu)圖和源碼可知，每個(gè)kv對(duì)應(yīng) zskiplistNode 結(jié)構(gòu)，其實(shí) sds 存儲(chǔ)集合元素，score 表示分?jǐn)?shù)，backward 指向后向一個(gè)節(jié)點(diǎn)，通過(guò)這個(gè)可以反向遍歷，zskiplistLevel 數(shù)組，存儲(chǔ)多層的指向前向節(jié)點(diǎn)的指針以及跨度span（用于計(jì)算節(jié)點(diǎn)的排名）。

查找過(guò)程： 從 header的最高層開(kāi)始遍歷，找到最后一個(gè)比目標(biāo)節(jié)點(diǎn)小的節(jié)點(diǎn)，然后從這個(gè)節(jié)點(diǎn)降一層再開(kāi)始遍歷，找到最后一個(gè)比目標(biāo)節(jié)點(diǎn)小的節(jié)點(diǎn)，按次類推，直到降到最底層，遍歷找到目標(biāo)節(jié)點(diǎn)。遍歷期間經(jīng)過(guò)的節(jié)點(diǎn)稱為［搜索路徑］。插入節(jié)點(diǎn)時(shí)，也是根據(jù)這個(gè)搜索路徑來(lái)進(jìn)行插入的，但是插入的節(jié)點(diǎn)面臨一個(gè)問(wèn)題就是層數(shù)多少合適？redis 采用的是隨機(jī)算法。

插入過(guò)程： 通過(guò)上面的查找過(guò)程得到[搜索路徑]，然后根據(jù)隨機(jī)算法算出層數(shù)，再將搜索路徑上的節(jié)點(diǎn)跟這個(gè)新節(jié)點(diǎn)通過(guò)前后指針串起來(lái)。

計(jì)算層數(shù)的隨機(jī)算法： 如下面源碼所示，生成一個(gè)范圍 0~1的隨機(jī)數(shù)，如果小于0.25，那么層數(shù)加1，繼續(xù)循環(huán)，不滿足則退出循環(huán)，并且不超過(guò)最大層數(shù)32

int zslRandomLevel(void) {
    int level = 1;
    while ((random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF))
        level += 1;
    return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
}
//#define ZSKIPLIST_P 0.25 
//#define ZSKIPLIST_MAXLEVEL 32

刪除過(guò)程： 根據(jù)查找過(guò)程得到的【搜索路徑】，然后將刪除節(jié)點(diǎn)有關(guān)聯(lián)的相關(guān)節(jié)點(diǎn)重新處理一下前后指針即可，注意更新一下最高層數(shù) level

更新過(guò)程： 如果更新的score和value 帶來(lái)位置的改變，通過(guò)先刪除節(jié)點(diǎn)，再插入來(lái)調(diào)整位置

排序規(guī)則： 先根據(jù)score從小到達(dá)排序，如果score相等，通過(guò)value進(jìn)行字典排序（字符串比較排序）。

元素排名： 通過(guò)搜索路徑經(jīng)過(guò)的所有節(jié)點(diǎn)的跨度 span 進(jìn)行疊加

如上面的源碼zset數(shù)據(jù)結(jié)構(gòu)，還包含了dict（字典）的數(shù)據(jù)結(jié)構(gòu)，主要是為了根據(jù)元素找score可以O(shè)(1)的時(shí)間復(fù)雜度實(shí)現(xiàn)，如果使用跳躍列表則需要O(logN)的復(fù)雜度，有點(diǎn)利用空間換時(shí)間的設(shè)計(jì)，通過(guò)冗余加上dict，提升查詢?cè)豷core的性能。

本文由mdnice多平臺(tái)發(fā)布

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

圖解redis的5種數(shù)據(jù)類型底層原理

圖解redis的5種數(shù)據(jù)類型底層原理

redis的5種數(shù)據(jù)類型以及其底層實(shí)現(xiàn)

字符串(String)

SDS

列表(List)

ZIPLIST（壓縮列表）

LINKEDLIST（雙向鏈表）

QUICKLIST（快速列表）

哈希(Hash)

LISTPACK(壓縮列表)

HT編碼（HASHTABLE、哈希表）

集合(Set)

INTSET編碼

有序集合(ZSet)

SKIPLIST(跳躍列表)

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

圖解redis的5種數(shù)據(jù)類型底層原理

redis的5種數(shù)據(jù)類型以及其底層實(shí)現(xiàn)

字符串(String)

SDS

列表(List)

ZIPLIST（壓縮列表）

LINKEDLIST（雙向鏈表）

QUICKLIST（快速列表）

哈希(Hash)

LISTPACK(壓縮列表)

HT編碼（HASHTABLE、哈希表）

集合(Set)

INTSET編碼

有序集合(ZSet)

SKIPLIST(跳躍列表)

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av