Redis两种结构 listpack 和 quicklist
1、listpack
2、 quicklist
Redis两种结构 listpack 和 quicklist按照顺序,本来应该先介绍 quicklist 的结构,quicklist 在 7.0 之前的版本是由双向链表和压缩列表构成的,但是在 7.0 版本已经变成了由双向链表和 listpack 实现,所以在这里我们先介绍一下 listpack 的结构。
1、listpacklistpack 是替换 ziplist 的数据结构,所以在结构上两者是有些相似的,listpack 的结构如下:
| 总字节长度 | entry个数 | entry1 | entry2 | ... | entryN | end |
相比 ziplist,listpack 去除了到尾部节点,也就是到 entryN 的偏移量,但保留了其他属性。
对于单个 entry 元素,其结构如下:
| encoding | content | length |
encoding 表示 content 的编码,endocing 表示实际存储的内容,length 表示该 entry 的长度
避免连锁更新
使用 listpack 替代 ziplist 的一个好处是避免了连续更新的问题。
因为 ziplist 的每个元素都有一个属性用于保存前一个节点元素的长度,因此前一个节点修改后会可能需要修改后一个节点的属性,但是 listpack 没有这个关联关系,从而避免了影响后续元素的长度,也因此避免了连锁更新的问题。
获取最后一个节点
虽然 listpack 没有了指向尾部节点的偏移量,但是同样可以快速找到 listpack 的尾部节点,方式是通过 总字节长度属性的值,可以直接获取到 listpack 的尾部,然后根据 entry 元素尾部的 length 属性,就可以找到尾部 entry 的起始地址了。
2、 quicklist在 Redis 3.2 版本,列表对象的底层实现变成了由 quicklist 实现,quicklist 实际上是压缩列表和双向链表的组合结构,因为 quicklist 就是一个链表,而链表中每一个元素就是压缩列表。
而在 Redis 7.0 版本,quicklst 变成了由双向链表和 listpack 构成的结构。
这里直接介绍 quicklist 由双向链表和 listpack 构成的结构。
quicklist 的结构和双向链表的结构类似:
typedef struct quicklist {
quicklistNode *head;
quicklistNode *tail;
unsigned long count;
unsigned long len;
...
} quicklist;
对于一个 quicklist,它也有指向 quicklist 的头节点和尾节点的指针,如结构中的 head 和 tail。
count 属性统计每个 quicklist 节点的 listpack 总数量的属性
len 则是统计 quicklist 中 quicklistNode 的数量的属性。
typedef struct quicklistNode {
struct quicklistNode *prev;
struct quicklistNode *next;
unsigned char *entry;
size_t sz;
unsigned int count : 16;
...
} quicklistNode;
对于一个 quicklistNode,拥有指向前置节点和后置节点的指针,还有指向其下 listpack 的 entry,以及 sz 表示该 listpack 的总字节长度,count 属性则表示该 listpack 中包含的元素个数。
以上就是Redis数据结构之listpack和quicklist使用学习的详细内容,更多关于Redis数据结构listpack quicklist的资料请关注软件开发网其它相关文章!