redislist底层数据结构
redis list数据结构
 redis list数据结构底层采⽤压缩列表ziplist或linkedlist两种数据结构进⾏存储，⾸先以ziplist进⾏存储，在不满⾜ziplist的存储要求后转换为linkedlist列表。
 当列表对象同时满⾜以下两个条件时，列表对象使⽤ziplist进⾏存储，否则⽤linkedlist存储。
列表对象保存的所有字符串元素的长度⼩于64字节
列表对象保存的元素数量⼩于512个。
redis list元素添加过程
 list的数据添加根据传⼊的变量个数⼀个个顺序添加，整个顺序如下：
创建list对象并添加到db的数据结构当中
针对每个待插⼊的元素添加到list当中
void pushGenericCommand(redisClient *c, int where) {
int j, waiting = 0, pushed = 0;
// 取出列表对象
robj *lobj = lookupKeyWrite(c->db,c->argv[1]);
// 如果列表对象不存在，那么可能有客户端在等待这个键的出现
int may_have_waiting_clients = (lobj == NULL);
if (lobj && lobj->type != REDIS_LIST) {
addReply(c,shared.wrongtypeerr);
return;
}
// 将列表状态设置为就绪
if (may_have_waiting_clients) signalListAsReady(c,c->argv[1]);
/
/ 遍历所有输⼊值，并将它们添加到列表中
for (j = 2; j < c->argc; j++) {
// 编码值
c->argv[j] = tryObjectEncoding(c->argv[j]);
// 如果列表对象不存在，那么创建⼀个，并关联到数据库
if (!lobj) {
lobj = createZiplistObject();
dbAdd(c->db,c->argv[1],lobj);
}
// 将值推⼊到列表
listTypePush(lobj,c->argv[j],where);
pushed++;
}
// 返回添加的节点数量
addReplyLongLong(c, waiting + (lobj ? listTypeLength(lobj) : 0));
// 如果⾄少有⼀个元素被成功推⼊，那么执⾏以下代码
if (pushed) {
char *event = (where == REDIS_HEAD) ? "lpush" : "rpush";
// 发送键修改信号
signalModifiedKey(c->db,c->argv[1]);
// 发送事件通知
notifyKeyspaceEvent(REDIS_NOTIFY_LIST,event,c->argv[1],c->db->id);    }
server.dirty += pushed;
}
 list的每个元素的插⼊过程中，我们会对是否需要进⾏转码作两个判断：对每个插⼊元素的长度进⾏判断是否进⾏ziplist->linkedlist的转码。
对list总长度是否超过ziplist最⼤长度的判断。
* 将给定元素添加到列表的表头或表尾。
*
* 参数 where 决定了新元素添加的位置：
*
*  - REDIS_HEAD 将新元素添加到表头
*
*  - REDIS_TAIL 将新元素添加到表尾
redis八种数据结构
*
*
* 调⽤者⽆须担⼼ value 的引⽤计数，因为这个函数会负责这⽅⾯的⼯作。
*/
void listTypePush(robj *subject, robj *value, int where) {
// 是否需要转换编码？
listTypeTryConversion(subject,value);
// #define REDIS_LIST_MAX_ZIPLIST_ENTRIES 512
if (subject->encoding == REDIS_ENCODING_ZIPLIST &&
ziplistLen(subject->ptr) >= server.list_max_ziplist_entries)
listTypeConvert(subject,REDIS_ENCODING_LINKEDLIST);
/
/ ZIPLIST
if (subject->encoding == REDIS_ENCODING_ZIPLIST) {
int pos = (where == REDIS_HEAD) ? ZIPLIST_HEAD : ZIPLIST_TAIL;
// 取出对象的值，因为 ZIPLIST 只能保存字符串或整数
value = getDecodedObject(value);
subject->ptr = ziplistPush(subject->ptr,value->ptr,sdslen(value->ptr),pos);
decrRefCount(value);
// 双端链表
} else if (subject->encoding == REDIS_ENCODING_LINKEDLIST) {
if (where == REDIS_HEAD) {
listAddNodeHead(subject->ptr,value);
} else {
listAddNodeTail(subject->ptr,value);
}
incrRefCount(value);
// 未知编码
} else {
redisPanic("Unknown list encoding");
}
}
判断ziplist中单个元素的长度是否超过64的长度，如果超过了长度那么就需要转编码格式为linkedlist编码。
* 对输⼊值 value 进⾏检查，看是否需要将 subject 从 ziplist 转换为双端链表，
* 以便保存值 value 。
*
* 函数只对 REDIS_ENCODING_RAW 编码的 value 进⾏检查，
* 因为整数编码的值不可能超长。
*/
void listTypeTryConversion(robj *subject, robj *value) {
// 确保 subject 为 ZIPLIST 编码
if (subject->encoding != REDIS_ENCODING_ZIPLIST) return;
if (sdsEncodedObject(value) &&
// 看字符串是否过长，#define REDIS_LIST_MAX_ZIPLIST_VALUE 64
sdslen(value->ptr) > server.list_max_ziplist_value)
/
/ 将编码转换为双端链表
listTypeConvert(subject,REDIS_ENCODING_LINKEDLIST);
}
redis ziplist数据结构
 ziplist⼜叫压缩列表，整体的数据格式如下，暂时可以临时看⼀看，后⾯会针对数据结构专门的⽂章来解释。
/*
空⽩ ziplist ⽰例图
area        |<---- ziplist header ---->|<-- end -->|
size          4 bytes  4 bytes 2 bytes  1 byte
+---------+--------+-------+-----------+
component  | zlbytes | zltail | zllen | zlend    |
|        |        |      |          |
value      |  1011  |  1010  |  0  | 1111 1111 |
+---------+--------+-------+-----------+
^
|
ZIPLIST_ENTRY_HEAD
&
address                        ZIPLIST_ENTRY_TAIL
&
ZIPLIST_ENTRY_END
⾮空 ziplist ⽰例图
area        |<---- ziplist header ---->|<----------- entries ------------->|<-end->|
size          4 bytes  4 bytes  2 bytes    ?        ?        ?        ?    1 byte
+---------+--------+-------+--------+--------+--------+--------+-------+
component  | zlbytes | zltail | zllen | entry1 | entry2 |  ...  | entryN | zlend |
+---------+--------+-------+--------+--------+--------+--------+-------+
^                          ^        ^
address                                |                          |        |
ZIPLIST_ENTRY_HEAD                |  ZIPLIST_ENTRY_END
|
ZIPLIST_ENTRY_TAIL
*/
* 保存 ziplist 节点信息的结构
*/
typedef struct zlentry {
// prevrawlen ：前置节点的长度
// prevrawlensize ：编码 prevrawlen 所需的字节⼤⼩
unsigned int prevrawlensize, prevrawlen;
// len ：当前节点值的长度
// lensize ：编码 len 所需的字节⼤⼩
unsigned int lensize, len;
// 当前节点 header 的⼤⼩
// 等于 prevrawlensize + lensize
unsigned int headersize;
// 当前节点值所使⽤的编码类型
unsigned char encoding;
// 指向当前节点的指针
unsigned char *p;
}
redis linkedlist数据结构
 双向列表的格式是通⽤的数据结构，不⽤过多解释⼤家都能理解了。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。