链表 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 ---一种无损压缩算法。
网友评论