redis中的數(shù)據(jù)結(jié)構(gòu)和編碼：
背景：
源碼：
值對(duì)象redisObject：
typedef struct redisObject {
unsigned type:4; /* 對(duì)象類型 */
unsigned encoding:4; /* 內(nèi)部編碼 */
unsigned lru:LRU_BITS; /* lru time (relative to server.lruclock) */
int refcount; /* 引用計(jì)數(shù)器，內(nèi)存回收機(jī)制就是基于該值實(shí)現(xiàn)的 */
void *ptr; /* 若要存儲(chǔ)的是整數(shù)值則直接存儲(chǔ)數(shù)據(jù)，否則表示指向數(shù)據(jù)的指針 */
} robj;
類型type：
說明：查看當(dāng)前鍵的類型：type key
#define OBJ_STRING 0 /*字符串對(duì)象*/
#define OBJ_LIST 1 /*列表對(duì)象*/
#define OBJ_SET 2 /*集合對(duì)象*/
#define OBJ_ZSET 3 /*有序集合對(duì)象*/
#define OBJ_HASH 4 /*哈希對(duì)象*/
編碼encoding；
說明：查看當(dāng)前鍵的編碼：object encoding key
#define OBJ_ENCODING_RAW 0 /*Raw representation 簡(jiǎn)單動(dòng)態(tài)字符串*/
#define OBJ_ENCODING_INT 1 /*Encoded as integer long long類型整數(shù)*/
#define OBJ_ENCODING_HT 2 /* Encoded as hash table 字典*/
#define OBJ_ENCODING_ZIPMAP 3 /* Encoded as zipmap 壓縮map*/
#define OBJ_ENCODING_LINKEDLIST 4 /* Encoded as regular linked list 雙端鏈表*/
#define OBJ_ENCODING_ZIPLIST 5 /* Encoded as ziplist 壓縮列表*/
#define OBJ_ENCODING_INTSET 6 /* Encoded as intset 整數(shù)集合*/
#define OBJ_ENCODING_SKIPLIST 7 /* Encoded as skiplist 跳躍表*/
#define OBJ_ENCODING_EMBSTR 8 /* Embedded sds string encoding embstr編碼的簡(jiǎn)單動(dòng)態(tài)字符串*/
#define OBJ_ENCODING_QUICKLIST 9 /* 基于壓縮列表的雙端列表實(shí)現(xiàn)的 快速表*/
最后被訪問的時(shí)間lru：
概念：記錄對(duì)象最后一次被訪問的時(shí)間。
說明：
1>查看當(dāng)前鍵的空閑時(shí)間(該命令不會(huì)更新lru字段)；object idletime key 。可以通過scan + object idletime key 來收集長(zhǎng)時(shí)間未被訪問的數(shù)據(jù)，然后手動(dòng)清理。
2>當(dāng)配置了maxmemory和maxmemory-policy=volatile-lru或者allkeys-lru時(shí)，若內(nèi)存超過了上限(maxmemory)后，則優(yōu)先回收長(zhǎng)時(shí)間沒有被訪問的數(shù)據(jù)，從而回收內(nèi)存。
引用計(jì)數(shù)器refcount：
概念：記錄當(dāng)前對(duì)象被引用的次數(shù)，當(dāng)refcount=0時(shí)，可以安全回收當(dāng)前對(duì)象空間。
說明：獲取當(dāng)前對(duì)象引用：object refcount key
類型對(duì)應(yīng)的編碼：
字符串：
int：存放整形值的字符串。
embstr：存放字符的短字符串(大小不超過44個(gè)字節(jié))。
raw：存放字符的長(zhǎng)字符串(大小不超過44個(gè)字節(jié))。
embstr和raw的比較：
raw調(diào)用2次內(nèi)存分配函數(shù)，釋放時(shí)當(dāng)然也需要釋放兩次。
embstr調(diào)用1次內(nèi)存分配函數(shù)，分配一塊連續(xù)的內(nèi)存，釋放時(shí)只需釋放一次。
列表(list)：
壓縮列表(ziplist)：
結(jié)構(gòu)：所有數(shù)據(jù)都是采用線性連續(xù)的內(nèi)存結(jié)構(gòu)(大致可類比數(shù)組)，目的是為了減少內(nèi)存的占用，追求空間和時(shí)間的平衡。
1>以O(shè)(1)時(shí)間復(fù)雜度入隊(duì)和出隊(duì)。
2>讀寫操作涉及復(fù)雜的指針移動(dòng)，最壞時(shí)間復(fù)雜度為O(n2)，故列表的元素不易太多。
3>新增刪除操作涉及內(nèi)存重新分配，加大了操作的復(fù)雜性。
優(yōu)點(diǎn)：占用內(nèi)存較少，且占用的是一塊連續(xù)的內(nèi)存，故加載的速度相對(duì)更快一些。
缺點(diǎn)：當(dāng)元素的個(gè)數(shù)較大時(shí)，訪問元素的時(shí)間較長(zhǎng)。
應(yīng)用：
適合存儲(chǔ)小對(duì)象和長(zhǎng)度有限(即使O(n2)的復(fù)雜度也不會(huì)太大)的數(shù)據(jù)。
當(dāng)元素個(gè)數(shù)小于list-max-ziplist-entries(默認(rèn)512) 且 所有元素值的大小都小于list-max-ziplist-value(默認(rèn)64字節(jié))時(shí)，使用ziplist作為列表的內(nèi)部實(shí)現(xiàn)。
雙端鏈表(linkedlist)：
優(yōu)點(diǎn)：元素的個(gè)數(shù)較多時(shí)，訪問元素的時(shí)間比壓縮列表更快一些。
缺點(diǎn)：因?yàn)槭请p向鏈表，故維護(hù)了前置指針、后置指針等結(jié)構(gòu)，占用了更多的內(nèi)存，且內(nèi)存不是連續(xù)的，容易產(chǎn)生內(nèi)存碎片。
說明：當(dāng)無法滿足ziplist的條件時(shí)，使用linkedlist作為列表的內(nèi)部實(shí)現(xiàn)。
應(yīng)用：當(dāng)列表對(duì)象元素較多時(shí)，壓縮列表就會(huì)轉(zhuǎn)化為更適合存儲(chǔ)大量元素的雙端鏈表。
注意：只能小內(nèi)存編碼向大內(nèi)存編碼轉(zhuǎn)換。(若當(dāng)元素增刪頻繁時(shí)，數(shù)據(jù)向壓縮編碼轉(zhuǎn)換是非常消耗CPU的，得不償失)
快速列表(quicklist)：
結(jié)構(gòu)：一個(gè)雙向鏈表，鏈表的每一個(gè)節(jié)點(diǎn)都是一個(gè)ziplist，故quicklist結(jié)合了雙向鏈表和壓縮列表的優(yōu)點(diǎn)。
Redis3.2開始，列表采用quicklist進(jìn)行編碼。
哈希(hash)：
壓縮列表(ziplist)：
應(yīng)用：當(dāng)元素個(gè)數(shù)小于hash-max-ziplist-entries(默認(rèn)512) 且 所有元素value的大小都小于hash-max-ziplist-value(默認(rèn)64字節(jié))時(shí)，使用ziplist作為哈希的內(nèi)部實(shí)現(xiàn)。
哈希表(hashtable)：
優(yōu)點(diǎn)：讀寫時(shí)間復(fù)雜度O(1)
缺點(diǎn)：占用內(nèi)存較多。
應(yīng)用：當(dāng)無法滿足ziplist的條件時(shí)，hashtable作為哈希的內(nèi)部實(shí)現(xiàn)。
hash算法：與傳統(tǒng)hash算法類似，根據(jù)key計(jì)算得到在哈希表中的位置，采用單鏈表解決沖突，達(dá)到加載因子時(shí)進(jìn)行擴(kuò)展，進(jìn)而引發(fā)重哈希。
rehash：采用增量式重哈希：
概念：在擴(kuò)容時(shí)不會(huì)一次性對(duì)所有的key進(jìn)行rehash，而是將key的rehash操作分散延遲到其它操作(哈希表的查找、更新、刪除)中。
優(yōu)點(diǎn)：避免由于大量的key在同一時(shí)間段進(jìn)行rehash操作導(dǎo)致服務(wù)短暫無響應(yīng)的問題。
過程：在增量式的rehash過程中，會(huì)使用到兩張哈希表：
查找：先從老表中查找，再?gòu)男卤碇胁檎遥送膺€會(huì)對(duì)一些key進(jìn)行rehash操作。
新增：新增的鍵值對(duì)添加到新表中。
集合(set)：
整數(shù)集合(intset)：
結(jié)構(gòu)：有序、不重復(fù)的整數(shù)集。
1>查找時(shí)間復(fù)雜度為O(logn)
2>插入時(shí)間復(fù)雜度為O(n)
優(yōu)點(diǎn)：占用的內(nèi)存遠(yuǎn)小于hashtable，
應(yīng)用：當(dāng)元素都是整數(shù) 且 元素個(gè)數(shù)小于set-max-intset-entries(默認(rèn)512)時(shí)，使用intset作為集合的內(nèi)部實(shí)現(xiàn)。
哈希表(hashtable)：當(dāng)無法滿足intset的條件時(shí)，使用hashtable作為集合的內(nèi)部實(shí)現(xiàn)。
有序集合(zset)：
說明：redis給有序集合中的每個(gè)元素設(shè)置一個(gè)分?jǐn)?shù)(score)作為排序的依據(jù)。
壓縮列表(ziplist)：
應(yīng)用：當(dāng)元素個(gè)數(shù)小于zset-max-ziplist-entries(默認(rèn)128個(gè)) 且 每個(gè)元素的值都小于zset-max-ziplist-value(默認(rèn)64字節(jié))時(shí)，使用ziplist作為有序集合的內(nèi)部實(shí)現(xiàn)。
跳躍表(skiplist)：
結(jié)構(gòu)：跳躍表通過在每個(gè)節(jié)點(diǎn)中(基于層和跨度等)維持多個(gè)指向其它節(jié)點(diǎn)的指針來實(shí)現(xiàn)快速訪問。
查找時(shí)間復(fù)雜度平均O(logn)、最壞O(n)。
應(yīng)用：當(dāng)不滿足ziplist條件時(shí)，使用skiplist作為內(nèi)部實(shí)現(xiàn)。
內(nèi)存優(yōu)化：
場(chǎng)景：有海量key和value都比較小的數(shù)據(jù)，在redis中如何存儲(chǔ)才更省內(nèi)存。
原理：通過大幅減少key的數(shù)量來降低內(nèi)存的消耗。
實(shí)現(xiàn)：在客戶端通過分組將海量的key根據(jù)一定的策略映射到一組hash對(duì)象中，由于value較小，故hash類型的對(duì)象會(huì)使用占用內(nèi)存較小的ziplist編碼。
eg：如存在100萬個(gè)鍵，可以映射到1000個(gè)hash中，每個(gè)hash保存1000個(gè)元素。
以上就是redis中的數(shù)據(jù)結(jié)構(gòu)和編碼詳解的詳細(xì)內(nèi)容，更多關(guān)于redis中的數(shù)據(jù)結(jié)構(gòu)和編碼的資料請(qǐng)關(guān)注武林網(wǎng)其它相關(guān)文章！
新聞熱點(diǎn)
疑難解答
圖片精選
