Pre
Algorithms_基础数据结构(03)_线性表之链表_双向链表
Redis 有 5 种基础数据结构，分别为：string (字符串)、list (列表)、set (集合)、hash (哈希) 和 zset (有序集合) 。
Redis 所有的数据结构都是以唯一的key 字符串作为名称，然后通过这个唯一 key 值来获取相应的 value 数据。不同类型的数据结构的差异就在于 value 的结构不一样。
list 列表
Redis 的列表相当于 Java 语言里面的 LinkedList，是链表而不是数组 。
这意味着list 的插入和删除操作非常快，时间复杂度为 O(1)，但是查找数据很慢，时间复杂度为 O(n) 。
当列表弹出了最后一个元素之后，该数据结构自动被删除，内存被回收。
Redis 的列表结构常用来做异步队列使用
将需要延后处理的任务结构体序列化成字符串塞进 Redis 的列表，另一个线程从这个列表中轮询数据进行处理
队列 O(1)
右边进左边出：队列
192.168.18.131:8001> rpush artisan art1 art2 art3 art4 (integer) 4 192.168.18.131:8001> llen artisan (integer) 4 192.168.18.131:8001> LRANGE artisan 0 999 1) "art1" 2) "art2" 3) "art3" 4) "art4" 192.168.18.131:8001> LPOP artisan "art1" 192.168.18.131:8001> LPOP artisan "art2" 192.168.18.131:8001> LPOP artisan "art3" 192.168.18.131:8001> LPOP artisan "art4" 192.168.18.131:8001> LPOP artisan (nil) 192.168.18.131:8001>
当然了，你也可以左边进，右边出，保证FIFO就行。
栈 O(1)
右边进右边出：栈
192.168.18.131:8001> rpush artisan art1 art2 art3 art4 (integer) 4 192.168.18.131:8001> RPOP artisan "art4" 192.168.18.131:8001> RPOP artisan "art3" 192.168.18.131:8001> RPOP artisan "art2" 192.168.18.131:8001> RPOP artisan "art1" 192.168.18.131:8001> RPOP artisan (nil) 192.168.18.131:8001>
查询 O(n)
lindex & ltrim
lindex 相当于 Java 链表的 get(int index)方法，它需要对链表进行遍历，性能随着参数index 增大而变差.
ltrim : 两个参数 start_index 和 end_index 定义了一个区间，在这个区间内的值， ltrim 要保留，区间之外统统砍掉。
我们可以通过 ltrim 来实现一个定长的链表，这一点非常有用。
index 可以为负数，index=-1 表示倒数第一个元素，同样 index=-2 表示倒数第二个元素。
192.168.18.131:8001> rpush artisan art1 art2 art3 art4 (integer) 4 192.168.18.131:8001> LINDEX artisan 0 # O(n) 慎用 "art1" 192.168.18.131:8001> LINDEX artisan 3 "art4" 192.168.18.131:8001> LTRIM artisan 0 2 OK 192.168.18.131:8001> LRANGE artisan 0 999 1) "art1" 2) "art2" 3) "art3" 192.168.18.131:8001> LRANGE artisan 0 -1 # 获取所有元素，O(n) 慎用 1) "art1" 2) "art2" 3) "art3" 192.168.18.131:8001> LTRIM artisan 1 -1 # O(n) 慎用 OK 192.168.18.131:8001> LRANGE artisan 0 -1 # 获取所有元素，O(n) 慎用 1) "art2" 2) "art3" 192.168.18.131:8001> 192.168.18.131:8001> LTRIM artisan 1 0 # 这其实是清空了整个列表，因为区间范围长度为负 OK 192.168.18.131:8001> LLEN artisan (integer) 0 192.168.18.131:8001>
快速列表 quicklist
Redis 底层存储的还不是一个简单的 linkedlist，而是称之为快速链表 quicklist 的一个结构。
首先在列表元素较少的情况下会使用一块连续的内存存储，这个结构是 ziplist ，即压缩列表 . 它将所有的元素紧挨着一起存储，分配的是一块连续的内存
当数据量比较多才会改成 quicklist.
因为普通的链表需要的附加指针空间太大，会比较浪费空间，而且会加重内存的碎片化 .
比如这个列表里存的只是 int 类型的数据，结构上还需要两个额外的指针 prev 和 next 。所以 Redis 将链表和 ziplist 结合起来组成了 quicklist。也就是将多个ziplist 使用双向指针串起来使用。这样既满足了快速的插入删除性能，又不会出现太大的空间冗余。
压缩列表 ziplist
Redis 为了节约内存空间使用，zset 和 hash 容器对象在元素个数较少的时候，采用压缩列表 (ziplist) 进行存储。
压缩列表是一块连续的内存空间，元素之间紧挨着存储，没有任何冗余空隙。
使用DEBUG OBJECT 查看内部存储结构
192.168.18.131:8001> ZADD artisan 1.0 java 2.0 go 3.0 python (integer) 3 192.168.18.131:8001> DEBUG OBJECT artisan # 查看内部存储结构 Value at:0x7f131e2ba5d0 refcount:1 encoding:ziplist serializedlength:36 lru:9895943 lru_seconds_idle:6 192.168.18.131:8001>
192.168.18.131:8001> HMSET artisan2 name ysw sex male -> Redirected to slot [6066] located at 192.168.18.132:8002 OK 192.168.18.132:8002> DEBUG OBJECT artisan2 Value at:0x7fb74eaba5f0 refcount:1 encoding:ziplist serializedlength:34 lru:9896028 lru_seconds_idle:9 192.168.18.132:8002>
观察 debug object 输出的 encoding 字段都是 ziplist，这就表示内部采用压缩列表结构进行存储。
ziplist 源码
struct ziplist<T> { int32 zlbytes; // 整个压缩列表占用字节数 int32 zltail_offset; // 最后一个元素距离压缩列表起始位置的偏移量，用于快速定位到最后一个节点 int16 zllength; // 元素个数 T[] entries; // 元素内容列表，挨个挨个紧凑存储 int8 zlend; // 标志压缩列表的结束，值恒为 0xFF }
压缩列表为了支持双向遍历，所以才会有 ztail_offset 这个字段，用来快速定位到最后一 个元素，然后倒着遍历。
entry
entry 块随着容纳的元素类型不同，也会有不一样的结构
struct entry { int<var> prevlen; // 前一个 entry 的字节长度 int<var> encoding; // 元素类型编码 optional byte[] content; // 元素内容 }
它的 prevlen 字段表示前一个 entry 的字节长度，当压缩列表倒着遍历时，需要通过这个字段来快速定位到下一个元素的位置。
它是一个变长的整数，当字符串长度小于254(0xFE) 时，使用一个字节表示；
如果达到或超出 254(0xFE) 那就使用 5 个字节来表示。
第一个字节是 0xFE(254)，剩余四个字节表示字符串长度。
用 5 个字节来表示字符串长度，是不是太浪费了?
我们可以算一下，当字符串长度比较长的时候，其实 5个字节也只占用了不到(5/(254+5))<2%的空间。
encoding 字段存储了元素内容的编码类型信息，ziplist 通过这个字段来决定后面的content 内容的形式。
增加元素
因为 ziplist 都是紧凑存储，没有冗余空间 (对比一下 Redis 的字符串结构)。意味着插入一个新的元素就需要调用 realloc 扩展内存。
取决于内存分配器算法和当前的 ziplist 内存大小，realloc 可能会重新分配新的内存空间，并将之前的内容一次性拷贝到新的地址，也可能在原有的地址上进行扩展，这时就不需要进行旧内容的内存拷贝。
如果 ziplist 占据内存太大，重新分配内存和拷贝内存就会有很大的消耗。所以 ziplist不适合存储大型字符串，存储的元素也不宜过多。
快速列表 quicklist
Redis 早期版本存储 list 列表数据结构使用的是压缩列表 ziplist 和普通的双向链表linkedlist，也就是元素少时用 ziplist，元素多时用 linkedlist。
// 链表的节点 struct listNode<T> { listNode* prev; listNode* next; T value; } // 链表 struct list { listNode *head; listNode *tail; long length; }
考虑到链表的附加空间相对太高，prev 和 next 指针就要占去 16 个字节 (64bit 系统的指针是 8 个字节)，另外每个节点的内存都是单独分配，会加剧内存的碎片化，影响内存管理效率。后续版本对列表数据结构进行了改造，使用 quicklist 代替了 ziplist 和 linkedlist。
192.168.18.132:8002> RPUSH test artisan1 artisan2 artisan3 (integer) 3 192.168.18.132:8002> DEBUG OBJECT test Value at:0x7fb74eaba610 refcount:1 encoding:quicklist serializedlength:36 lru:9897276 lru_seconds_idle:4 ql_nodes:1 ql_avg_node:3.00 ql_ziplist_max:-2 ql_compressed:0 ql_uncompressed_size:41 192.168.18.132:8002>
观察上面输出字段 encoding 的值。quicklist 是 ziplist 和 linkedlist 的混合体，它将 linkedlist 按段切分，每一段使用 ziplist 来紧凑存储，多个 ziplist 之间使用双向指针串接起来。
struct ziplist { ... } struct ziplist_compressed { int32 size; byte[] compressed_data; } struct quicklistNode { quicklistNode* prev; quicklistNode* next; ziplist* zl; // 指向压缩列表 int32 size; // ziplist 的字节总数 int16 count; // ziplist 中的元素数量 int2 encoding; // 存储形式 2bit，原生字节数组还是 LZF 压缩存储 ... } struct quicklist { quicklistNode* head; quicklistNode* tail; long count; // 元素总数 int nodes; // ziplist 节点的个数 int compressDepth; // LZF 算法压缩深度 ... }
上述代码简单地表示了 quicklist 的大致结构。为了进一步节约空间，Redis 还会对ziplist 进行压缩存储，使用 LZF 算法压缩，可以选择压缩深度。
ziplist 存多少元素?
quicklist 内部默认单个 ziplist 长度为 8k 字节，超出了这个字节数，就会新起一个ziplist。
ziplist 的长度由配置参数 list-max-ziplist-size 决定。
压缩深度
quicklist 默认的压缩深度是 0，也就是不压缩。压缩的实际深度由配置参数 list-compress-depth 决定.
为了支持快速的 push/pop 操作，quicklist 的首尾两个 ziplist 不压缩，此时深度就是 1。
如果深度为 2，就表示 quicklist 的首尾第一个 ziplist 以及首尾第二个 ziplist 都不压缩。
延伸
参考：《Redis深度历险：核心原理和应用实践》
