面試官：Redis數(shù)據(jù)結(jié)構(gòu)與內(nèi)部編碼，你知道多少？

介紹

Redis是一個基于內(nèi)存的數(shù)據(jù)庫，所有的數(shù)據(jù)都存儲在內(nèi)存中，所以如何優(yōu)化存儲，減少內(nèi)存空間占用對成本控制來說是非常重要的。精簡鍵名和鍵值是最直觀的減少內(nèi)存占用的方式，而Redis則是通過內(nèi)部編碼規(guī)則來節(jié)省更多的內(nèi)存空間。

Redis為每種數(shù)據(jù)類型都提供了兩三種內(nèi)部編碼方式，以散列類型為例，散列類型是通過散列表實現(xiàn)的，這樣就可以實現(xiàn)0(1)時間復(fù)雜度的查找、賦值操作，然而當(dāng)鍵中元素很少的時候，0(1)的操作并不會比0(n)有明顯的性能提高，所以這種情況下Redis會采用一種更為緊湊但性能稍差（獲取元素的時間復(fù)雜度為0(n)）的內(nèi)部編碼方式。內(nèi)部編碼方式的選擇對于開發(fā)者來說是透明的，Redis會根據(jù)實際情況自動調(diào)整。當(dāng)鍵中元素變多時Redis會自動將該鍵的內(nèi)部編碼方式轉(zhuǎn)換成散列表。

一、Redis DB數(shù)據(jù)結(jié)構(gòu)

Redis中是有16個redisDB庫，默認是使用第一個。我們先來看下redisDB的數(shù)據(jù)結(jié)構(gòu)：

• dict：字典

• dictht：就是一個hashtable，以o(1)時間復(fù)雜度獲取size，used當(dāng)前數(shù)組里面用掉了多少空間

• dictEntry：數(shù)組里面的元素，**table指針指向數(shù)組，redis中所有的key都是存在dictEntry中

• *var：存儲key的值，也是一個指針，指向redisObject結(jié)構(gòu)進行數(shù)據(jù)存儲，這個指針指向真實的數(shù)據(jù)存儲

• next：當(dāng)key發(fā)生hash沖突時（比如都是數(shù)組0），通過next指針建立一個單向的鏈表解決hash沖突
  

robj字段介紹：

• type：對外的數(shù)據(jù)類型，string，list，hash，set，zset等

• encoding：內(nèi)部編碼，raw，int，ziplist等，對內(nèi)存利用率極致追求

• LRU_BITS：內(nèi)存淘汰策略

• refcount：redis內(nèi)存管理需要

• *ptr：指向真實的數(shù)據(jù)存儲結(jié)構(gòu)，ziplist等，最終指向數(shù)據(jù)編碼的對象

二、內(nèi)部編碼方式

下面是Redis數(shù)據(jù)結(jié)構(gòu)與內(nèi)部編碼的關(guān)系：

查看一個鍵的內(nèi)部編碼方式：

127.0.0.1:6379>?set?foo barOK127.0.0.1:6379> object encoding foo"raw"

Redis的每個鍵值都是使用一個redisObject結(jié)構(gòu)體保存的，在redis.h中聲明的redisObj定義的如下：

typedef struct redisObject { ??unsigned?type:4;?/**?4?bit?*/?  unsigned encoding:4; /** 4 bit */ ??unsigned?lru:LRU_BITS;?/**?24 bit?*/??int?refcount;??/**?4?byte?*/??void?*?ptr;??/**?8?byte?*/}robj;

其中type字段表示的是鍵值的數(shù)據(jù)類型，取值可以是如下內(nèi)容：

#define REDIS_STRING 0 #define REDIS_LIST 1 #define REDIS_SET 2 #define REDIS_ZSET 3 #define REDIS_HASH 4

encoding字段表示的就是Redis鍵值的內(nèi)部編碼方式，取值可以是：

#define?REDIS_ENCODING_RAW?0?/**?Raw?representation?*/?#define REDIS_ENCODING_INT 1 /** ed as integer */ #define?REDIS_ENCODING_EMBSTR?2?/**?cpu cache line?*/?#define?REDIS_ENCODING_HT?3?/**?Encoded?as?hash?table?*/?#define?REDIS_ENCODING_ZIPMAP?4?/**?Encoded?as?zipmap?*/?#define?REDIS_ENCODING_QUICKEDLIST?5?/**?Encoded?as?regular?quicked?list?*/?#define?REDIS_ENCODING_ZIPLIST?6?/**?Encoded?as?ziplist?*/?#define?REDIS_ENCODING_INTSET?7?/**?Encoded?as?intset?*/?#define?REDIS_ENCODING_SKIPLIST?8?/**?Encoded?as?skiplist?*/

各個數(shù)據(jù)類型可能采用的內(nèi)部編碼方式以及相應(yīng)的OBJECT ENCODING命令執(zhí)行結(jié)果如下：

下面針對每種數(shù)據(jù)類型分別介紹其內(nèi)部編碼規(guī)則及優(yōu)化方式。

二、字符串類型優(yōu)化方式

127.0.0.1:6379> set a_string aOK127.0.0.1:6379> set a_int 1OK127.0.0.1:6379> set a_long_string aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaOK127.0.0.1:6379> type a_stringstring127.0.0.1:6379> type a_intstring127.0.0.1:6379> type a_long_stringstring127.0.0.1:6379> object encoding a_string"embstr"127.0.0.1:6379> object encoding a_int"int"127.0.0.1:6379> object encoding a_long_string"raw"127.0.0.1:6379>

Redis使用一個sdshdr類型的變量來存儲字符串，而redisObject的ptr字段指向的是該變量的地址。sdshdr的定義如下：

//?redis3.2之前版本struct sdshdr { ??int?len;?/* 表示的是字符串的長度 */  int free; /* 表示buf中的剩余空間 */  char buf[]; /* 字符串的內(nèi)容 */};
//?redis3.2之后版本typedef char *sds;
struct?sdshdr5?{???unsigned?char?flags;?/*3?lsb?of?type,?and?5?msb?of?string?length*/  char buf[]; };
struct?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?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?sdshdr32?{?
  ... };
struct?sdshdr64?{?
  ...};

redis根據(jù)字符串大小選擇合適的數(shù)據(jù)存儲結(jié)構(gòu)：

#define SDS_TYPE_5 0#define?SDS_TYPE_8?1#define?SDS_TYPE_16?2#define?SDS_TYPE_32?3#define?SDS_TYPE_64?4
static inline char sdsReqType(size_t_string_size) {??if?(string_size?32)????return?SDS_TYPE_5;??if?(string_size?0xff) // 2^8 - 1????return?SDS_TYPE_8;??if?(string_size?0xffff)?//?2^16?-?1????return?SDS_TYPE_16;??if?(string_size?0xffffffff)?//?2^32?-?1????return?SDS_TYPE_32;??return?SDS_TYPE_64;}

3.2之前：

• 可以動態(tài)擴容的數(shù)據(jù)結(jié)構(gòu)

• free代表可用空間，分配空間可以分配稍微大一點的空間，下次進行數(shù)據(jù)修改的時候就不用每次都分配內(nèi)存，提升整體性能

3.2之后：

• 變得豐富多樣

• 節(jié)省存儲空間，比如就存一個字符串【i】，使用sdshdr數(shù)據(jù)結(jié)構(gòu)需要len+free=4+4=8字節(jié)

• sdshdr5只會使用一個字節(jié)flags，表示數(shù)據(jù)特性。如下：

  

• flags+buf，一個flags字節(jié)的低3位表示類型type，len表示數(shù)據(jù)長度（2^5-1 < 32）

• buf表示真實數(shù)據(jù)

缺點是無法動態(tài)擴容，沒有free字段，所以redis也沒有使用sdshdr5這種數(shù)據(jù)結(jié)構(gòu)，never used，所以通常情況下，使用下面sdshdr8：

• type定義的0，1，2表示type占用的bit位，可以減少空間占用
  

接下來我們分別介紹下string類型的raw、int和embstr。

embstr

比如當(dāng)執(zhí)行SET key foobar時，在64位linux系統(tǒng)下，存儲鍵值需要占用的空間是?sizeof(redisObject)+sizeof(sdshdr8)+strlen("foobar")=16字節(jié)+4字節(jié)+6字節(jié)=26字節(jié)。存儲結(jié)構(gòu)如下：

在linux操作系統(tǒng)，cpu緩存行大小占64byte，而redisObject和sdshdr8正好占用20個字節(jié)，所以當(dāng)業(yè)務(wù)數(shù)據(jù)大小在64-20=44字節(jié)之內(nèi)的話，可以利用cpu緩存行特性：linux分配內(nèi)存的時候，就會挨著redisObject進行分配，開辟一塊連續(xù)的空間存儲，利用cpu的緩存行一次讀取到數(shù)據(jù)，減少內(nèi)存IO，這樣數(shù)據(jù)整合就在cpu緩存行范圍內(nèi)，這樣在進行數(shù)據(jù)讀取的時候，cpu第一次尋址到var，通過var找到redisObject，通過redisObject我們可以直接拿到值，而不用通過指針再一次尋址去拿數(shù)據(jù)，這就是embstr做的事情。

raw類型是和redisObject不在一塊連續(xù)的內(nèi)存空間，如下：

我們可以對embstr進行驗證：

127.0.0.1:6379> set a_string_short aaaaaaaaaa-aaaaaaaaaa-aaaaaaaaaa-aaaaaaaaaa-OK127.0.0.1:6379> STRLEN a_string_short(integer) 44127.0.0.1:6379> object encoding a_string_short"embstr"127.0.0.1:6379> set b_string_short aaaaaaaaaa-aaaaaaaaaa-aaaaaaaaaa-aaaaaaaaaa-aOK127.0.0.1:6379> STRLEN b_string_short(integer) 45127.0.0.1:6379> object encoding b_string_short"raw"127.0.0.1:6379>?

• 當(dāng)字符串長度大于44時就變成了raw
  

使用append追加字符串方式說明：

127.0.0.1:6379> set a aOK127.0.0.1:6379> object encoding a"embstr"127.0.0.1:6379> APPEND a b(integer) 2127.0.0.1:6379> object encoding a"raw"127.0.0.1:6379>?

• 使用append等命令會修改redis內(nèi)部編碼，就不適用cpu緩存行優(yōu)化的方式了
  

int

當(dāng)鍵值內(nèi)容可以用一個64位有符號整數(shù)表示時，Redis會將鍵值轉(zhuǎn)換成long類型來存儲。如SET key 123456，實際占用的空間是sizeof(redisObject)=16字節(jié)，比存儲"foobar"節(jié)省了 一半的存儲空間，如下所示：

redisObject中的refcount字段存儲的是該鍵值被引用數(shù)量，即一個鍵值可以被多個鍵引用。Redis啟動后會預(yù)先建立10000個分別存儲從0到9999這些數(shù)字的redisObject類型變量作為共享 對象，如果要設(shè)置的字符串鍵值在這10000個數(shù)字內(nèi)（如SET key1 123）則可以直接引用共享對象而不用再建立一個redisObject了，也就是說存儲鍵值占用的空間是0字節(jié)，如下所示：

由此可見，使用字符串類型鍵存儲對象ID這種小數(shù)字是非常節(jié)省存儲空間的，Redis只需存儲鍵名和一個對共享對象的引用即可。?雖然整形底層存儲encoding是int類型，但是在獲取長度計算時會轉(zhuǎn)換為字符串計算長度。

注意：當(dāng)通過配置文件參數(shù)maxmemory設(shè)置了Redis可用的最大空間大小時，Redis不會使用共享對象，因為對于每一個鍵值都需要使用一個redisObject來記錄其LRU信息。

字符串?dāng)U容的原理：

• 當(dāng)字符串大小小于1M時，每次擴容一倍

• 大于1M時，每次增加1M，比如現(xiàn)在5M，擴容后就是6M

三、散列類型優(yōu)化方式

散列類型的內(nèi)部編碼方式可能是REDIS_ENCODING_HT或REDIS_ENCODING_ZIPLIST。當(dāng)數(shù)據(jù)量比較小或者單個元素比較小時，底層用ziplist存儲。可以在配置文件中可以定義使用REDIS_ENCODING_ZIPLIST方式編碼散列類型的時機：

hash-max-ziplist-entries 512 hash-max-ziplist-value 64

當(dāng)散列類型鍵的字段個數(shù)少于hash-max-ziplist-entries參數(shù)值且每個字段名和字段值的長度都小于hash-max-ziplist-value參數(shù)值（單位為字節(jié)）時，Redis就會使用REDIS_ ENCODING_ZIPLIST來存儲該鍵，否則就會使用REDIS_ENCODING_HT。轉(zhuǎn)換過程是透明的，每當(dāng)鍵值變更后Redis都會自動判斷是否滿足條件來完成轉(zhuǎn)換。如下演示：

127.0.0.1:6379> hset user name duan age 27 f1 v1 f2 v2 f3 v3(integer) 5127.0.0.1:6379> HGETALL user 1) "name" 2) "duan" 3) "age" 4) "27" 5) "f1" 6) "v1" 7) "f2" 8) "v2" 9) "f3"10) "v3"127.0.0.1:6379> hset user f4 vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv(integer) 1127.0.0.1:6379> HGETALL user 1) "f3" 2) "v3" 3) "name" 4) "duan" 5) "f4" 6) "vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv" 7) "f1" 8) "v1" 9) "f2"10) "v2"11) "age"12) "27"127.0.0.1:6379>?

超過64個字節(jié)變成hash，hash是無序的。

REDIS_ENCODING_HT編碼即散列表，可以實現(xiàn)O(1)時間復(fù)雜度的賦值取值等操作，其字段和字段值都是使用redisObject存儲的，所以前面講到的字符串類型鍵值的優(yōu)化方法同樣適用于散列類型鍵的字段和字段值。

注意：Redis的鍵值對存儲也是通過散列表實現(xiàn)的，與REDIS_ENCODING_HT編碼方式類似，但鍵名并非使用redisObject存儲，所以鍵名"123456"并不會比"abcdef"占用更少的空間。之所以不對鍵名進行優(yōu)化是因為絕大多數(shù)情況下鍵名都不會是純數(shù)字。

Redis支持多數(shù)據(jù)庫，每個數(shù)據(jù)庫中的數(shù)據(jù)都是通過結(jié)構(gòu)體redisDb存儲的。redisDb的定義如下：

typedef struct redisDb { dict?*?dict;?/**?The?keyspace?for?this?DB?*/?dict?* expires;?/**?Timeout?of?keys?with?a?timeout?set?*/?dict?*?blocking_keys;?/**?Keys?with?clients?waiting?for?data?(BLPOP)?*/?dict?*?ready_keys;?/**?Blocked?keys?that?received?a?PUSH?*/?dict?*?watched_keys;?/**?WATCHED?keys?for?MULTI/EXEC?CAS?*/?int id; } redisDb;

• dict類型就是散列表結(jié)構(gòu)

• expires存儲的是數(shù)據(jù)的過期時間

當(dāng)Redis啟動時會根據(jù)配置文件中databases參數(shù)指定的數(shù)量創(chuàng)建若干個redisDb類型變量存儲不同數(shù)據(jù)庫中的數(shù)據(jù)。

REDIS_ENCODING_ZIPLIST編碼類型是一種緊湊的編碼格式，它犧牲了部分讀取性能以換取極高的空間利用率，適合在元素較少時使用。該編碼類型同樣還在列表類型和有序集合類型中使用。REDIS_ENCODING_ZIPLIST編碼結(jié)構(gòu)如下所示：

• zlbytes是uint32_t類型， 表示整個結(jié)構(gòu)占用的空間

• zltail也是uint32_t類型，表示到最后一個元素的偏移，記錄zltail使得程序可以直接定位到尾部元素而無需遍歷整個結(jié)構(gòu)，執(zhí)行從尾部彈出（對列表類型而言）等操作時速度更快

• zllen是uint16_t類型，存儲的是元素的數(shù)量

• zlend是一個單字節(jié)標(biāo)識，標(biāo)記結(jié)構(gòu)的末尾，值永遠是255

散列類型的ziplist數(shù)據(jù)結(jié)構(gòu)如下圖所示：

在REDIS_ENCODING_ZIPLIST中每個元素由4個部分組成：

• 第一個部分用來存儲前一個元素的大小以實現(xiàn)倒序查找，當(dāng)前一個元素的大小小于254字節(jié)時第一個部分占用1個字節(jié)，否則會占用5個字節(jié)

• 第二、三個部分分別是元素的編碼類型和元素的大小，當(dāng)元素的大小小于或等于63個字 節(jié)時，元素的編碼類型是ZIP_STR_06B（即0＜＜6），同時第三個部分用6個二進制位來記錄元素的長度，所以第二、三個部分總占用空間是1字節(jié)。當(dāng)元素的大小大于63且小于或等于16383字節(jié)時，第二、三個部分總占用空間是2字節(jié)。當(dāng)元素的大小大于16383字節(jié)時，第二、三個部 分總占用空間是5字節(jié)

• 第四個部分是元素的實際內(nèi)容，如果元素可以轉(zhuǎn)換成數(shù)字的話Redis會使用相應(yīng)的數(shù)字類型來存儲以節(jié)省空間，并用第二、三個部分來表示數(shù)字的類型（int16_t、int32_t等）

使用REDIS_ENCODING_ZIPLIST編碼存儲散列類型時元素的排列方式是：元素1存儲字段1，元素2存儲字段值2，依次類推，如下所示：

例如，當(dāng)執(zhí)行命令HSET hkey foo bar命令后，hkey鍵值的內(nèi)存結(jié)構(gòu)如下所示：

下次需要執(zhí)行HSET hkey foo anothervalue時Redis需要從頭開始找到值為foo的元素（查找 時每次都會跳過一個元素以保證只查找字段名），找到后刪除其下一個元素，并將新值 anothervalue插入。刪除和插入都需要移動后面的內(nèi)存數(shù)據(jù)，而且查找操作也需要遍歷才能完 成，可想而知當(dāng)散列鍵中數(shù)據(jù)多時性能將很低，所以不宜將hash-max-ziplist-entries和hash-max- ziplist-value兩個參數(shù)設(shè)置得很大。

四、列表類型優(yōu)化方式

列表類型內(nèi)部編碼方式是REDIS_ENCODING_QUICKLIST或REDIS?ENCODINGZIPLIST。

127.0.0.1:6379> lpush queue-task a b c(integer) 3127.0.0.1:6379> type queue-tasklist127.0.0.1:6379> object encoding queue-task"quicklist"127.0.0.1:6379>?

同樣在配置文件中可以設(shè)置每個ziplist的最大容量和quickList的數(shù)據(jù)壓縮范圍，提升數(shù)據(jù)存取效率。

list-max-ziplist-size -2list-compress-depth 0

• 0默認不壓縮

• list不關(guān)注中間數(shù)據(jù)，1表示不壓縮頭尾節(jié)點，壓縮中間數(shù)據(jù)

• 2表示頭尾節(jié)點和頭尾相鄰的一個節(jié)點不壓縮，壓縮初次之外中間的
  

注意：列表類型實現(xiàn)阻塞隊列使用的是redisDb結(jié)構(gòu)中的字段blocking_keys，維護的是key與客戶端的關(guān)系，不會阻塞redis進程。如下：

typedef struct redisDb {   dict *dict;   ...  dict *blocking_keys;   ...}redisDb

ZIPLIST數(shù)據(jù)結(jié)構(gòu)

ziplist數(shù)據(jù)結(jié)構(gòu)說明：

• zlbytes:32bit表示ziplist占用的字節(jié)總數(shù)

• zltail:32bit表示ziplist表中最后一項entry在ziplist中的偏移字節(jié)數(shù)。通過zltail我們可以很方便地找到最后一項，從而可以在ziplist尾端快速地執(zhí)行push或pop操作

• zlen:16bit表示ziplist中數(shù)據(jù)項entry的個數(shù)

• entry：表示真正存放數(shù)據(jù)的數(shù)據(jù)項，長度不定

• zlend：ziplist最后一個字節(jié)，是一個結(jié)束標(biāo)記，值固定等于255

• prerawlen：前一個entry的數(shù)據(jù)長度

• len：entry中數(shù)據(jù)的長度

• data：真實數(shù)據(jù)存儲
  

根據(jù)len字段的第一個字節(jié)分的9種情況：

• 00xxxxxx：len字段前2個高位 bit為0，剩余的6個bit用來表示長度，即最大長度可以到2^6 - 1

• 01xxxxxx xxxxxxxx：len字段的前2個高位是01，則len字段占2個byte，共有14個bit表示，數(shù)據(jù)長度最多2^14 - 1

• 10xxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx：len字段前2個高位bit是10，則len字段占5個byte，共有32個bit表示，數(shù)據(jù)長度最多2^32 - 1，第一個字節(jié)的剩余6個bit舍棄不用

• 11000000：len字段前2個高位bit是11，值為OXC0，則len字段占1個byte，后面的data為2字節(jié)的int16_t類型

• 11010000：len字段前4個高位bit是1101，值為OXD0，則len字段占1個byte，后面的data為4字節(jié)的int32_t類型

• 11100000：len字段前4個高位bit是1110，值為OXE0，則len字段占1個byte，后面的data為8字節(jié)的int64_t類型

• 11110000：len字段前4個高位bit是1111，值為OXF0，則len字段占1個byte，后面的data為3字節(jié)的整數(shù)

• 11111110：len字段前7個高位bit是1111111，值為OXFE，則len字段占1個byte，后面的data為1字節(jié)的整數(shù)

• 1111xxxx：len字段前4個字節(jié)是1111，后4個bit的范圍是（0001-1101），這時xxxx從1到13，一共13個值，這時就用這13個值來表示data的數(shù)據(jù)，真正的數(shù)值大小為對應(yīng)的bit位數(shù)值-1，代表真實的業(yè)務(wù)數(shù)據(jù)
  

ziplist是非常緊湊的一種數(shù)據(jù)類型，為了節(jié)省內(nèi)存空間。而非常緊湊的數(shù)據(jù)結(jié)構(gòu)的缺點是：

• 空間必須是連續(xù)的

• 數(shù)據(jù)量非常大的時候往里面加元素，數(shù)據(jù)遷移很麻煩

• 頻繁的內(nèi)存分配與釋放是不劃算的，所以redis針對這個問題進行了優(yōu)化，quicklist

QUICKLIST數(shù)據(jù)結(jié)構(gòu)

quicklist的優(yōu)化是后續(xù)有數(shù)據(jù)修改，都是在一個小的ziplist中。

五、集合類型優(yōu)化方式

集合類型的內(nèi)部編碼方式可能是REDIS_ENCODING_HT或REDIS_ENCODING_INTSET。

127.0.0.1:6379> sadd aset a b c d e f(integer) 6127.0.0.1:6379> sadd bset 1 2 3 4 5 6(integer) 6127.0.0.1:6379> object encoding aset"hashtable"127.0.0.1:6379> object encoding bset"intset"127.0.0.1:6379> sadd bset a(integer) 1127.0.0.1:6379> SMEMBERS bset1) "a"2) "5"3) "3"4) "1"5) "6"6) "4"7) "2"127.0.0.1:6379>?

當(dāng)集合中的所有元素都是整數(shù)且元素的個數(shù)小于配置文件中的set-max-intset-entries參數(shù)指定值（默認是512）時Redis會使用REDIS_ENCODING_INTSET編碼存儲該集合，否則會使用 REDIS_ENCODING_HT來存儲。?REDIS_ENCODING_INTSET編碼存儲結(jié)構(gòu)體intset的定義是：

typedef struct intset { uint32_t encoding; uint32_t length; int8_t contents[]; } intset;

其中contents存儲的就是集合中的元素值，根據(jù)encoding的不同，每個元素占用的字節(jié)大小 不同。默認的encoding是INTSET_ENC_INT16（即2個字節(jié)），當(dāng)新增加的整數(shù)元素?zé)o法使用2個字節(jié)表示時，Redis會將該集合的encoding升級為INTSET_ENC_INT32（即4個字節(jié)）并調(diào)整之前所有元素的位置和長度，同樣集合的encoding還可升級為INTSET_ENC_INT64（即8個字節(jié)）。?并且contents[]內(nèi)存儲的整數(shù)元素是順序存儲的。

REDIS_ENCODING_INTSET編碼以有序的方式存儲元素（所以使用SMEMBERS命令獲得的結(jié)果是有序的），使得可以使用二分算法查找元素。但是無論是添加還是刪除元素，Redis都需要調(diào)整后面元素的內(nèi)存位置，所以當(dāng)集合中的元素太多時性能較差。當(dāng)新增加的元素不是整數(shù)或集合中的元素數(shù)量超過了set-max-intset-entries參數(shù)指定值時，Redis會自動將該集合的存儲結(jié)構(gòu)轉(zhuǎn)換成REDIS_ENCODING_HT。

注意?：當(dāng)集合的存儲結(jié)構(gòu)轉(zhuǎn)換成REDIS_ENCODING_HT后，即使將集合中的所有非整數(shù)元素刪除，Redis也不會自動將存儲結(jié)構(gòu)轉(zhuǎn)換回REDIS_ENCODING_INTSET。因為如果要支持自動回轉(zhuǎn)，就意味著Redis在每次刪除元素時都需要遍歷集合中的鍵來判斷是否可以轉(zhuǎn)換回原來的編碼，這會使得刪除元素變成了時間復(fù)雜度為0(n)的操作。

六、有序集合類型優(yōu)化方式

有序集合類型編碼方式可能是REDIS_ENCODING_SKIPLIST或REDIS_ENCODING_ZIPLIST。

當(dāng)數(shù)據(jù)比較少時采用ziplist編碼結(jié)構(gòu)存儲，同樣在配置文件中可以定義使用REDIS_ENCODING_ZIPLIST方式編碼的時機：

 zset-max-ziplist-entries 128  zset-max-ziplist-value 64 

有序集合的ziplist數(shù)據(jù)結(jié)構(gòu)如下圖：

當(dāng)數(shù)據(jù)大小超過128字節(jié)，使用跳表存儲，單個元素大小超多64個字節(jié)也是跳表結(jié)構(gòu)。有序集合的跳表結(jié)構(gòu)如下圖：

• *forward：前進指針

• span：跨越元素，比如rank操作就是通過span跨越元素來計算的

• 頭結(jié)點不存儲數(shù)據(jù)，起到索引的作用，中間和尾結(jié)點存儲數(shù)據(jù)

• L2找到了120，如果找150，下降一層，找到了200，則數(shù)據(jù)就在150就在120~200之間

具體規(guī)則和散列類型及列表類型一樣。當(dāng)編碼方式是REDIS_ENCODING_SKIPLIST時，Redis使用散列表和跳躍列表（skiplist）兩種數(shù)據(jù)結(jié)構(gòu)來存儲有序集合類型鍵值，其中散列表用來存儲元素值與元素分數(shù)的映射關(guān)系以實現(xiàn)0(1)時間復(fù)雜度的ZSCORE等命令。跳躍列表用來存儲元素的分數(shù)及其到元素值的映射以實現(xiàn)排序的功能。

Redis對跳躍列表的實現(xiàn)進行了幾點修改，其中包括允許跳躍列表中的元素（即分數(shù)）相同，還有為跳躍鏈表每個節(jié)點增加了指向前一個元素的指針以實現(xiàn)倒序查找。 采用此種編碼方式時，元素值是使用redisObject存儲的，所以可以使用字符串類型鍵值的優(yōu)化方式優(yōu)化元素值，而元素的分數(shù)是使用double類型存儲的。 使用REDIS_ENCODING_ZIPLIST編碼時有序集合存儲的方式按照"元素1的值，元素1的分數(shù)，元素2的值，元素2的分數(shù)"這樣的順序排列，并且分數(shù)是有序的。