关于后端:Redis数据结构七之listpack和quicklist

本文首发于公众号：Hunter 后端
原文链接：Redis 数据结构七之 listpack 和 quicklist

本篇笔记介绍 listpack 和 quicklist 两种构造

依照程序，原本应该先介绍 quicklist 的构造，quicklist 在 7.0 之前的版本是由双向链表和压缩列表形成的，然而在 7.0 版本曾经变成了由双向链表和 listpack 实现，所以在这里咱们先介绍一下 listpack 的构造。

listpack 是替换 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 的起始地址了。

在 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

1、listpack

2、quicklist