本文和大家分享的主要是redis數(shù)據(jù)類型中的list相關(guān)內(nèi)容，一起來看看吧，希望對(duì)大家學(xué)習(xí)redis有所幫助。

　  list即鏈表，它是一個(gè)能維持?jǐn)?shù)據(jù)先后順序的列表，便于在表的兩端追加和刪除數(shù)據(jù)，中間位置的存取具有O(N)的時(shí)間復(fù)雜度，是一個(gè)雙向鏈表。

　　一、內(nèi)部原理

　　redis內(nèi)部實(shí)現(xiàn)代碼在quicklist.c（注釋：A doubly linked list of ziplists）中，它確實(shí)是一個(gè)雙向鏈表，并且是一個(gè)ziplist雙向列表。

　　ziplist是什么？

　　一個(gè)經(jīng)過特殊編碼的的雙向鏈表，它的設(shè)計(jì)目的是為了提高存儲(chǔ)效率。ziplist可以用于存儲(chǔ)字符串或整數(shù)，其中整數(shù)是真正的二進(jìn)制進(jìn)行編碼的，而不是編碼成字符串序列。普通的雙向鏈表每一項(xiàng)都獨(dú)立的占用一塊內(nèi)存，各項(xiàng)之間用地址指針連接起來。這中方式會(huì)帶來大量的內(nèi)存碎片，而且地址指針也會(huì)占用額外的內(nèi)存。而ziplist將列表的每一項(xiàng)存放在前后連續(xù)的地址空間內(nèi)，一個(gè)大的ziplist整體占用一大塊內(nèi)存，它是一個(gè)列表，但不是一個(gè)鏈表。ziplist為了在細(xì)節(jié)上節(jié)省內(nèi)存，對(duì)于值的存儲(chǔ)采用了變長的編碼方式，對(duì)于大的整數(shù)，就多一些字節(jié)來存儲(chǔ)，對(duì)于小的少一些字節(jié)來存儲(chǔ)。

　　ziplist的數(shù)據(jù)結(jié)構(gòu)如下：

　　...

　　含義：

　?。?/span>32字節(jié)，表示ziplist占用的字符總數(shù)（本身占用4個(gè)字節(jié)）。

　　: 32字節(jié)，表示ziplist表中最后一項(xiàng)（entry）在ziplist中的偏移字節(jié)數(shù)。的存在，使得我們可以很方便地找到最后一項(xiàng)，從而可以在ziplist尾端快速地執(zhí)行push或pop操作。

　　: 16字節(jié)， 表示ziplist中數(shù)據(jù)項(xiàng)（entry）的個(gè)數(shù)。zllen字段因?yàn)橹挥?/span>16bit，所以可以表達(dá)的最大值為2^16-1。這里需要特別注意的是，如果ziplist中數(shù)據(jù)項(xiàng)個(gè)數(shù)超過了16bit能表達(dá)的最大值，ziplist仍然可以來表示。那怎么表示呢？這里做了這樣的規(guī)定：如果小于等于2^16-2（也就是不等于2^16-1），那么就表示ziplist中數(shù)據(jù)項(xiàng)的個(gè)數(shù)；否則，也就是等于16bit全為1的情況，那么就不表示數(shù)據(jù)項(xiàng)個(gè)數(shù)了，這時(shí)候要想知道ziplist中數(shù)據(jù)項(xiàng)總數(shù)，那么必須對(duì)ziplist從頭到尾遍歷各個(gè)數(shù)據(jù)項(xiàng)，才能計(jì)數(shù)出來。

　　: 表示真正存放數(shù)據(jù)的數(shù)據(jù)項(xiàng)，長度不定。一個(gè)數(shù)據(jù)項(xiàng)（entry）也有它自己的內(nèi)部結(jié)構(gòu)。

　　: ziplist最后1個(gè)字節(jié)，是一個(gè)結(jié)束標(biāo)記，值固定等于255。

　　entry的數(shù)據(jù)結(jié)構(gòu)：

　　

　　: 表示前一個(gè)數(shù)據(jù)項(xiàng)占用的總字節(jié)數(shù)。這個(gè)字段的用處是為了讓ziplist能夠從后向前遍歷（從后一項(xiàng)的位置，只需向前偏移prevrawlen個(gè)字節(jié)，就找到了前一項(xiàng)）。這個(gè)字段采用變長編碼。

　　。它有兩種可能，或者是1個(gè)字節(jié)，或者是5個(gè)字節(jié)：

　　1. 如果前一個(gè)數(shù)據(jù)項(xiàng)占用字節(jié)數(shù)小于254，那么就只用一個(gè)字節(jié)來表示，這個(gè)字節(jié)的值就是前一個(gè)數(shù)據(jù)項(xiàng)的占用字節(jié)數(shù)。

　　2. 如果前一個(gè)數(shù)據(jù)項(xiàng)占用字節(jié)數(shù)大于等于254，那么就用5個(gè)字節(jié)來表示，其中第1個(gè)字節(jié)的值是254（作為這種情況的一個(gè)標(biāo)記），而后面4個(gè)字節(jié)組成一個(gè)整型值，來真正存儲(chǔ)前一個(gè)數(shù)據(jù)項(xiàng)的占用字節(jié)數(shù)。

　　: 表示當(dāng)前數(shù)據(jù)項(xiàng)的數(shù)據(jù)長度（即部分的長度）。也采用變長編碼。根據(jù)第一個(gè)字節(jié)的不同分為下面九種方式

　　|00pppppp| - 1 byte  String value with length less than or equal to 63 bytes (6 bits).

　　|01pppppp|qqqqqqqq| - 2 bytes  String value with length less than or equal to 16383 bytes (14 bits).

　　|10______|qqqqqqqq|rrrrrrrr|ssssssss|tttttttt| - 5 bytes  String value with length greater than or equal to 16384 bytes.

　　|11000000| - 1 byte  Integer encoded as int16_t (2 bytes).

　　|11010000| - 1 byte  Integer encoded as int32_t (4 bytes).

　　|11100000| - 1 byte  Integer encoded as int64_t (8 bytes).

　　|11110000| - 1 byte  Integer encoded as 24 bit signed (3 bytes).

　　|11111110| - 1 byte  Integer encoded as 8 bit signed (1 byte).

　　|1111xxxx| - (with xxxx between 0000 and 1101) immediate 4 bit integer. Unsigned integer from 0 to 12. The encoded value is actually from 1 to 13 because 0000 and 1111 can not be used, so 1 should be  subtracted from the encoded 4 bit value to obtain the right value.

　　|11111111| - End of ziplist.

　　quicklist是什么？

　　雙向鏈表都是有多個(gè)node組成，而quicklist的每個(gè)節(jié)點(diǎn)都是一個(gè)ziplist。ziplist本身也是一個(gè)能維持?jǐn)?shù)據(jù)項(xiàng)先后順序的列表，而且內(nèi)存是緊湊的，例如一個(gè)包含2個(gè)node的quicklist，如果每個(gè)節(jié)點(diǎn)的ziplist包含了四個(gè)數(shù)據(jù)項(xiàng)

　　那么對(duì)外表現(xiàn)就是8個(gè)數(shù)據(jù)項(xiàng)。quicklist的設(shè)計(jì)是一個(gè)空間和時(shí)間的折中,雙向鏈表便于在表的兩端進(jìn)行push和pop操作，但是它的內(nèi)存開銷很大。開銷如下

　　1.每個(gè)節(jié)點(diǎn)上除了要保存數(shù)據(jù)之外，還要額外的保存兩個(gè)指針。

　　2.各個(gè)節(jié)點(diǎn)是單獨(dú)的內(nèi)存塊，地址不連續(xù)，節(jié)點(diǎn)多了容易產(chǎn)生內(nèi)存碎片。

　　ziplist是一塊連續(xù)的內(nèi)存，所以存儲(chǔ)效率很高。但是，它不利于修改操作，每次數(shù)據(jù)變動(dòng)都會(huì)引發(fā)內(nèi)存的realloc。一次realloc可能會(huì)導(dǎo)致大量的數(shù)據(jù)拷貝，進(jìn)一步降低性能。

　　quicklist結(jié)合了雙向鏈表和ziplist的優(yōu)點(diǎn)，但是同樣也存在一個(gè)問題，一個(gè)quicklist包含多長的ziplist合適呢？需要找到一個(gè)平衡點(diǎn)

　　1.ziplist太短，內(nèi)存碎片越多。

　　2.ziplist太長，分配大塊連續(xù)內(nèi)存空間的難度就越大。

　　如果保持ziplist的合理長度，取決于具體的應(yīng)用場(chǎng)景。redis提供了默認(rèn)配置

　　list-max-ziplist-size -2

　　參數(shù)的含義解釋，取正值時(shí)表示quicklist節(jié)點(diǎn)ziplist包含的數(shù)據(jù)項(xiàng)。取負(fù)值表示按照占用字節(jié)來限定quicklist節(jié)點(diǎn)ziplist的長度。

　　-5: 每個(gè)quicklist節(jié)點(diǎn)上的ziplist大小不能超過64 Kb。

　　-4: 每個(gè)quicklist節(jié)點(diǎn)上的ziplist大小不能超過32 Kb。

　　-3: 每個(gè)quicklist節(jié)點(diǎn)上的ziplist大小不能超過16 Kb。

　　-2: 每個(gè)quicklist節(jié)點(diǎn)上的ziplist大小不能超過8 Kb。（默認(rèn)值）

　　-1: 每個(gè)quicklist節(jié)點(diǎn)上的ziplist大小不能超過4 Kb。

　　list設(shè)計(jì)最容易被訪問的是列表兩端的數(shù)據(jù)，中間的訪問頻率很低，如果符合這個(gè)場(chǎng)景，list還有一個(gè)配置，可以對(duì)中間節(jié)點(diǎn)進(jìn)行壓縮（采用的LZF——一種無損壓縮算法），進(jìn)一步節(jié)省內(nèi)存。配置如下

　　list-compress-depth 0

　　含義：

　　0: 是個(gè)特殊值，表示都不壓縮。這是Redis的默認(rèn)值。

　　1: 表示quicklist兩端各有1個(gè)節(jié)點(diǎn)不壓縮，中間的節(jié)點(diǎn)壓縮。

　　2: 表示quicklist兩端各有2個(gè)節(jié)點(diǎn)不壓縮，中間的節(jié)點(diǎn)壓縮。

　　以此類推

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

　　/* quicklistNode is a 32 byte struct describing a ziplist for a quicklist.

　　* We use bit fields keep the quicklistNode at 32 bytes.

　　* count: 16 bits, max 65536 (max zl bytes is 65k, so max count actually < 32k).

　　* encoding: 2 bits, RAW=1, LZF=2.

　　* container: 2 bits, NONE=1, ZIPLIST=2.

　　* recompress: 1 bit, bool, true if node is temporarry decompressed for usage.

　　* attempted_compress: 1 bit, boolean, used for verifying during testing.

　　* extra: 12 bits, free for future use; pads out the remainder of 32 bits */typedef struct quicklistNode {

　　struct quicklistNode *prev; /*指向鏈表前一個(gè)節(jié)點(diǎn)的指針*/

　　struct quicklistNode *next; /*指向鏈表后一個(gè)節(jié)點(diǎn)的指針*/

　　unsigned char *zl;/*數(shù)據(jù)指針。如果當(dāng)前節(jié)點(diǎn)的數(shù)據(jù)沒有壓縮，那么它指向一個(gè)ziplist結(jié)構(gòu)；否則，它指向一個(gè)quicklistLZF結(jié)構(gòu)。*/

　　unsigned int sz; /*表示zl指向的ziplist的總大?。ò?/span>zlbytes, zltail, zllen, zlend和各個(gè)數(shù)據(jù)項(xiàng)）。需要注意的是：如果ziplist被壓縮了，那么這個(gè)sz的值仍然是壓縮前的ziplist大小。/*

　　unsigned int count : 16;     /*  表示ziplist里面包含的數(shù)據(jù)項(xiàng)個(gè)數(shù)。 */

　　unsigned int encoding : 2;   /* RAW==1(未壓縮) or LZF==2 （壓縮了并采用LZF壓縮算法）*/

　　unsigned int container : 2;  /* 使用的容器 NONE==1 or ZIPLIST==2（默認(rèn)值） */

　　unsigned int recompress : 1; /* 我們使用類似lindex這樣的命令查看了某一項(xiàng)本來壓縮的數(shù)據(jù)時(shí)，需要把數(shù)據(jù)暫時(shí)解壓，這時(shí)就設(shè)置recompress=1做一個(gè)標(biāo)記，等有機(jī)會(huì)再把數(shù)據(jù)重新壓縮 */

　　unsigned int attempted_compress : 1; /* node can't compress; too small */

　　unsigned int extra : 10; /* 其他擴(kuò)展字段（未使用） */

　　} quicklistNode;

　　/* quicklistLZF is a 4+N byte struct holding 'sz' followed by 'compressed'.

　　* 'sz' is byte length of 'compressed' field.

　　* 'compressed' is LZF data with total (compressed) length 'sz'

　　* NOTE: uncompressed length is stored in quicklistNode->sz.

　　* When quicklistNode->zl is compressed, node->zl points to a quicklistLZF */typedef struct quicklistLZF {

　　unsigned int sz; /* 表示壓縮后的ziplist大小*/

　　char compressed[]; /*是個(gè)柔性數(shù)組（flexible array member），存放壓縮后的ziplist字節(jié)數(shù)組/*

　　} quicklistLZF;

　　/* quicklist is a 32 byte struct (on 64-bit systems) describing a quicklist.

　　* 'count' is the number of total entries.

　　* 'len' is the number of quicklist nodes.

　　* 'compress' is: -1 if compression disabled, otherwise it's the number

　　*                of quicklistNodes to leave uncompressed at ends of quicklist.

　　* 'fill' is the user-requested (or default) fill factor. */typedef struct quicklist {

　　quicklistNode *head; ？/*指向頭節(jié)點(diǎn)（左側(cè)第一個(gè)節(jié)點(diǎn)）的指針。*/

　　quicklistNode *tail; /*指向尾節(jié)點(diǎn)（右側(cè)第一個(gè)節(jié)點(diǎn)）的指針。*/

　　unsigned long count;        /* quicklist節(jié)點(diǎn)的個(gè)數(shù) */

　　unsigned int len;           /* number of quicklistNodes */

　　int fill : 16;              /* ziplist大小設(shè)置，存放list-max-ziplist-size參數(shù)的值 */

　　unsigned int compress : 16; /* 節(jié)點(diǎn)壓縮深度設(shè)置，存放list-compress-depth參數(shù)的值 */

　　}

　　二：相關(guān)命令

　　lpush key value[value...]將一個(gè)或多個(gè)value插入到列表的表頭，如果有多個(gè)   value  值，那么各個(gè)   value  值按從左到右的順序依次插入到表頭： 比如說，對(duì)空列表   mylist  執(zhí)行命令   LPUSH mylist a b c ，列表的值將是   c b a  ，這等同于原子性地執(zhí)行   LPUSH mylist a  、   LPUSH mylist b  和   LPUSH mylist c  三個(gè)命令。 如果   key  不存在，一個(gè)空列表會(huì)被創(chuàng)建并執(zhí)行  lpush  操作。 當(dāng)   key  存在但不是列表類型時(shí)，返回一個(gè)錯(cuò)誤。

　　lpushx key value將值   value  插入到列表   key  的表頭，若key不存在，不執(zhí)行任何操作。

　　lpop key移除并返回列表key的頭元素（后進(jìn)先出），若key不存在返回nil。

　　blpop key[key...] timeoutlpop的阻塞版本，若給定列表中沒有任何元素可供彈出時(shí)，鏈接會(huì)被blpop命令阻塞，直到等待超時(shí)（單位：秒）或發(fā)現(xiàn)可彈出元素時(shí)為止，若發(fā)現(xiàn)其中任何一個(gè)列表中有值則返回列表key和第一個(gè)元素的值。

　　rpush key value[value...]將一個(gè)或多個(gè)值   value  插入到列表   key  的表尾(最右邊)， 如果有多個(gè)   value  值，那么各個(gè)   value  值按從左到右的順序依次插入到表尾：比如對(duì)一個(gè)空列表   mylist  執(zhí)行   RPUSH mylist a b c  ，得出的結(jié)果列表為   a b c  ，等同于執(zhí)行命令  RPUSH mylist a  、   RPUSH mylist b  、   RPUSH mylist c  。 如果   key  不存在，一個(gè)空列表會(huì)被創(chuàng)建并執(zhí)行  Rpush  操作。 當(dāng)   key  存在但不是列表類型時(shí)，返回一個(gè)錯(cuò)誤。

　　rpushx key value將值   value  插入到列表   key  的表尾，若key不存在，不執(zhí)行任何操作。

　　rpop key移除并返回列表的末尾，若key不存在則返回nil。

　　brpop key[key...] timeout它是   rpop 命令的阻塞版本，當(dāng)給定列表內(nèi)沒有任何元素可供彈出的時(shí)候，連接將被  brpop  命令阻塞，直到等待超時(shí)或發(fā)現(xiàn)可彈出元素為止。 當(dāng)給定多個(gè)   key  參數(shù)時(shí)，按參數(shù)   key  的先后順序依次檢查各個(gè)列表，彈出第一個(gè)非空列表的尾.

　　rpoplpush source destination命令  rpoppush  在一個(gè)原子時(shí)間內(nèi)，執(zhí)行以下兩個(gè)動(dòng)作： 將列表  source  中的最后一個(gè)元素(尾元素)彈出，并返回給客戶端。 將   source  彈出的元素插入到列表  destination  ，作為   destination  列表的的頭元素。 如果   source  不存在，值   nil  被返回，并且不執(zhí)行其他動(dòng)作。 如果   source  和   destination  相同，則列表中的表尾元素被移動(dòng)到表頭，并返回該元素，可以把這種特殊情況視作列表的旋轉(zhuǎn)(rotation)操作。

　　brpoplpush source destinationbrpoplpush 是  rpoplpush 的阻塞版本，當(dāng)給定列表   source  不為空時(shí)，  brpoplpush  的表現(xiàn)和  rpoplpush  一樣。 當(dāng)列表   source  為空時(shí)，  brpoplpush  命令將阻塞連接，直到等待超時(shí)，或有另一個(gè)客戶端對(duì)   source  執(zhí)行   lpush 或   rpush  命令為止。 超時(shí)參數(shù)   timeout  接受一個(gè)以秒為單位的數(shù)字作為值。超時(shí)參數(shù)設(shè)為   0  表示阻塞時(shí)間可以無限期延長(block indefinitely)

　　lset key index value將列表   key  下標(biāo)為   index  的元素的值設(shè)置為   value  。 當(dāng)   index  參數(shù)超出范圍，或?qū)σ粋€(gè)空列表(   key  不存在)進(jìn)行  lset 時(shí)，返回一個(gè)錯(cuò)誤。

　　linsert key before|after pivot value將值   value  插入到列表   key  當(dāng)中，位于值   pivot  之前或之后。 當(dāng)   pivot  不存在于列表   key  時(shí)，不執(zhí)行任何操作。 當(dāng)   key  不存在時(shí)，   key  被視為空列表，不執(zhí)行任何操作。 如果   key  不是列表類型，返回一個(gè)錯(cuò)誤。

　　llen key返回列表   key  的長度。 如果   key  不存在，則   key  被解釋為一個(gè)空列表，返回   0  .如果   key  不是列表類型，返回一個(gè)錯(cuò)誤。

　　lindex key index返回列表   key  中，下標(biāo)為   index  的元素。 下標(biāo)(index)參數(shù)   start  和   stop  都以   0  為底，也就是說，以   0  表示列表的第一個(gè)元素，以   1  表示列表的第二個(gè)元素，以此類推。 你也可以使用負(fù)數(shù)下標(biāo)，以   -1  表示列表的最后一個(gè)元素，   -2  表示列表的倒數(shù)第二個(gè)元素，以此類推。 如果   key  不是列表類型，返回一個(gè)錯(cuò)誤。

　　lrange key start stop返回列表   key  中指定區(qū)間內(nèi)的元素，區(qū)間以偏移量   start  和   stop  指定。 下標(biāo)(index)參數(shù)   start  和   stop  都以   0  為底，也就是說，以   0  表示列表的第一個(gè)元素，以   1  表示列表的第二個(gè)元素，以此類推。 你也可以使用負(fù)數(shù)下標(biāo)，以   -1  表示列表的最后一個(gè)元素，   -2  表示列表的倒數(shù)第二個(gè)元素，以此類推。

　　ltrim key start stop對(duì)一個(gè)列表進(jìn)行修剪(trim)，就是說，讓列表只保留指定區(qū)間內(nèi)的元素，不在指定區(qū)間之內(nèi)的元素都將被刪除。下標(biāo)(index)參數(shù)   start  和   stop  都以   0  為底，也就是說，以   0  表示列表的第一個(gè)元素，以   1  表示列表的第二個(gè)元素，以此類推。 你也可以使用負(fù)數(shù)下標(biāo)，以   -1  表示列表的最后一個(gè)元素，   -2  表示列表的倒數(shù)第二個(gè)元素，以此類推。 當(dāng)   key  不是列表類型時(shí)，返回一個(gè)錯(cuò)誤。

　　lrem key count value移除列表中與value相等的元素，若count>0從左到右移除與count個(gè)與value相等的元素；若count<0從右向左移除count個(gè)與value相等的元素；若count==0移除所有與value相等的元素。

 

 

來源：博客園