Redis - 列表

Redis 是键值对数据库，值支持几种数据结构，列表是其中一种。和其他语言或者中间件中的数据结构在功能上并没有特殊支持，只是 Redis 专门对存储的数据结构进行了内存优化，这一点可能不太一样。

基本数据结构

说到列表，总得来说有两种实现方式：基于数组和基于链表。

这两者之间主要区别为内存分布的设计，从而也带来 CRUD 的不同侧重。

内存

数组的每个元素占用内存空间一定是相同的，也一定是连续分配的。带来几点结果：

1、每个元素的地址很容易通过首地址 + N * SIZE 计算出来

2、内存连续，不易导致内存碎片

3、需要为元素预分配内存，才能保证内存连续；元素个数超过预分配需要扩展时，往往需要重新整个分配内存，再把原来的元素拷贝过来

链表元素的内存空间没有要求连续，往往是分离的，通过前后元素地址指针形成一个列表。带来几点结果：

1、要找到某个元素不太容易，需要从首/尾元素开始遍历才能找到

2、内存不连续，容易导致内存碎片；需保存指针，占多余内存

3、不需要预分配内存，扩展很方便，在当前的列表继续扩展即可。

CRUD 侧重

上述不同的内存特性，带了两种结果在 CRUD 操作时的不同侧重或者说优劣。

Redis 的选择

Redis 在 3.2 版本之前有两种列表实现：ziplist 和 linkedlist。

初始化创建时，会使用 ziplist，但当达到以下条件时会切换为 linkedlist 结构。

1、某元素字符串长度大于 64 字节；

2、列表元素个数大于 512

为什么有两种实现？为什么有切换的需求？实质都是为了内存，在内存占用比较小时，ziplist 比较省内存，但内存占用较大时，增删元素的复杂度太高，不得已要切换到 linkedlist，以降低复杂度。

ziplist

ziplist 实际是一种特殊的双向链表，特殊在哪里？内存是连续分配的，但每个元素的大小是变化的。

ziplist 的结构如下，entry 是实际存放数据的地方，可以存放一个数值或者字符串。

非空 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*/

<zlbytes> 是一个无符号整数，保存着 ziplist 使用的内存数量。

<zltail> 保存着到达列表中最后一个节点的偏移量。

<zllen> 保存着列表中的节点数量。

<zlend> 的长度为 1 字节，值为 255 ，标识列表的末尾。

entry 的结构体如下：

/* * 保存 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;
} zlentry;

这里需要强调下，上述结构体并不是真正的内存存储结构，只是某些场景方便计算，会将 entry 转换成上述的结构。真正的内存结构实际上就是一堆字节

unsigned int prevrawlensize, prevrawlen；表示的意思实际就是要用少个字节表示长度，长度是多少

ziplist 这种结构既没有享受到快速查询的好处（因为元素变长）也没有享受到增删的快捷（因为内存连续），唯一的好处就是省内存，时间换空间。

所以当元素规模上升到一定程度，那么时间这一点将会变得非常严峻，所以 redis 此时的应对策略就是切换成 linkedlist。

linkedlist

普通的双端列表，不再详说。

quicklist

ziplist 有些缺点，linkedlist 也有缺点，总得解决这个问题。那最终 3.2 版本后出来了个 quicklist，实际就是基于 ziplist 和 linkedlist 的折中，取代了 ziplist 和 linkedlist，作为列表的底层实现。

quicklist 大致思路：

ziplist 省内存增删慢

linkedlist 不省内存增删快

那就建一个链表，但其中元素是一个 ziplist（可以存多个字符串或者数值），这样既一定程度上得到了链表的好处，也一定程度得到了 ziplist 省内存的好处