redis数据结构(二)：各种列表

链表 list

就是传统意义上的链表

• 头尾指针
• 为了减轻计算长度的压力，维护了一个长度属性len
  没了

跳表 skiplist

跳表.png

说白了。就是空间换时间。把二分查找先用数据结构给实现了。根据索引（二分查找）直接就能定位了。时间复杂度O(logn)。

压缩列表 ziplist

压缩列表其实就是“数组”。
传统意义上的数组，申请好空间后，每个格的大小都是固定的，比如4字节。通过下标寻址，使用头指针地址 + index * 4，就算出了index的地址。
不好的地方就是，资源浪费：格大存的数据小。

数组.png

压缩列表，可以理解为每个格的大小不固定，存多大，格就多大。

那寻址就不能通过index * 固定大小了，怎么寻址的呢？？
先来看看数据结构

压缩列表.png

属性	类型	长度	用途
zlbytes	uint32_t	4字节	记录整个压缩列表占用的内存字节数；在对压缩列表进行内存重分配或者计算zlend位置的时候使用
zltail	uint32_t	4字节	记录压缩列表尾节点距离头节点有多少字节。通过这个偏移量能直接找到尾节点
zllen	uint16_t	2字节	记录了压缩列表包含的字节的数量
entryN	列表节点	节点多大就多大	压缩列表真正存储的数据
zlend	unt8_t	1字节	固定值oxFF（十进制255），用于标记压缩列表的末端

再具体讲下entry。除了entry，都是用来快速计算偏移量的。

还是先看数据结构

entry.png

• previous_entry_length:
  记录此节点前一个节点的长度。目的：为了从后向前遍历
• encoding
  记录此节点的数据类型和长度。一个字段怎么表示两个属性呢？很显然是高低位嘛。最高两位标识数据类型。后面表示长度。
  高位00表示字节
  高位11表示整数
• content
  记录此节点保存的具体值。

回答刚刚的问题，那寻址就不能通过index * 固定大小了，怎么寻址的呢？？
只能通过遍历来寻址了。不支持随机访问。因为redis是根据key取value。不会根据value去范围查询，所以查出来就可以了，也不需要去随机访问。

一个小知识点。压缩列表的数据是紧挨的，那扩容怎么办啊？？

没有办法。先扩一个，然后一个一个的扩，一个一个的挪。所以针对插入和删除，该数据结构不是很友好。那咋整，还有别的数据结构了。

快速列表 quicklist

那快速链表是什么呢？
官方解释是：

a double linked list of ziplists

是一个双向的链表，链表的节点都是压缩列表

ziplist本身是一个能维持先进先出的列表。一个包含3个节点的快速列表，每个节点的压缩列表又包含4个数据项，那么对外表现上，这个快速列表共包含12个数据项。

为什么要这样设计呢？？？？主要是为了空间和时间的折中。

• 双向链表便于在两端进行push和pop操作。但是内存开销比较大。1.保存头尾指针。2.内存地址不连续。
• 压缩列表没有内存开销的压力，但是修改的时候，每次变动都要触发一次realloc。

不过也带来的新的问题。到底快速列表包含多长的压缩列表才合适呢？？？

比如同样是存储12个数据，是quicklist包含3个节点，每个节点的ziplist包含4个数据项。还是quicklist包含6个节点，每个节点的ziplist包含2个数据项。

redis中可以自己配置

list-max-ziplist-size -2

• -5: 每个quicklist节点上的ziplist大小不能超过64 Kb。（注：1kb => 1024 bytes）
• -4: 每个quicklist节点上的ziplist大小不能超过32 Kb。
• -3: 每个quicklist节点上的ziplist大小不能超过16 Kb。
• -2: 每个quicklist节点上的ziplist大小不能超过8 Kb。（-2是Redis给出的默认值）
• -1: 每个quicklist节点上的ziplist大小不能超过4 Kb。

redis 快速列表的设计目标是能够用来存储很长的数据列表。当列表很长的时候，最容易被访问的很可能是两端的数据，中间的数据被访问的频率比较低（性能也低），所以redis还有一个配置

list-compress-depth 0

这个配置标识quicklist两端不被压缩的节点个数。

• 0: 是个特殊值，表示都不压缩。这是Redis的默认值。
• 1: 表示quicklist两端各有1个节点不压缩，中间的节点压缩。
• 2: 表示quicklist两端各有2个节点不压缩，中间的节点压缩。
• 3: 表示quicklist两端各有3个节点不压缩，中间的节点压缩。
• 依此类推…

redis对quicklist内存节点的压缩算法，采用的LZF ---一种无损压缩算法。