前提常识🧀
后面几个文章里咱们介绍到了字典 dict 和跳表 skiplist，它们都是 redis 为了谋求性能而开发的根本数据结构，外面或多或少都借助了一些辅助的元素；例如字典 dict 在 rehash 时会同时存在两个哈希表，又或者跳表 skiplist 里节点多了层的构造，这些设计都是为了 谋求性能而就义了内存空间。
如果你多多少少理解 HashMap 的底层原理的话，你就晓得：
在 JDK1.8 中，随着元素越来越多，HashMap 产生 hash 抵触，桶中元素大于等于 8 个，并且容量大于等于 64 时，会由链表模式转化为红黑树结构；而当桶中元素降到 6 时又会转换回链表。
为什么有这样的变动呢？因为这体现了工夫和空间均衡的思维，元素刚开始并不多时，链表的空间占用是比拟少的，并且因为链表短，查问须要的工夫也没有太大问题；可是随着链表越来越长，查问的须要的工夫也就越来越长，就须要用占用空间大然而查问更高效的红黑树来帮忙了。
工夫 or 空间，看来所有的数据结构都离不开这个命题。
而咱们明天要说的 压缩列表 ziplist 就是 redis 为了节约内存而设计开发的数据结构，并且作为列表键和哈希键的底层实现之一。
压缩列表 ziplist 的“退场机会”
-
hash（上面条件满足其一，hash 会由压缩列表 ziplist 构造转成字典 dict 构造）
- 键值对数目超过 512。
- 插入一个 value 长度超过 64 的键值对。
-
sorted set（上面条件满足其一，sorted set 会由压缩列表 ziplist 构造转成 zset 构造——蕴含一个 dict 和一个 skiplist）
- 键值对数目超过 128。
- 插入一个 value 长度超过 64 的键值对。
PS：在 ziplist 转成其余数据结构后，不会再退为 ziplist 构造。
压缩列表的构造
各个局部在内存是间断的，对应的含意如下：
- <zlbytes>：4 字节；用来记录整个压缩列表占用的内存字节数。
- <zltail>：4 字节，用来记录压缩列表表尾节点（最初一个 entry）距起始地址有多少字节，即偏移字节数。
- <zllen>：2 字节，记录了蕴含的节点数量，即 entry 的个数。当 entry 个数小于 2^16-1（65535）时，这个属性值就是压缩列表蕴含的节点个数；而当这个值等于 2^16- 1 时（该字段只有 2 字节，16bit，即能示意的最大值，所有位数都为 1），节点数量须要遍历整个压缩列表能力得出。
- <entry>：长度不定，用来寄存理论要存储的数据项，有对应的构造，上面会再介绍。
- <zlend>：1 字节，固定为 255，用来标记压缩列表的末端。
- <previous_entry_length>：1 字节或 5 字节；用来记录前一个节点的长度，前一个节点长度小于 2^8-2（254）字节时，那么该属性长度为 1 字节，前节点的长度就保留在这一个字节中；如果前一个节点长度大于等于 254 字节，那么该属性长度为 5 字节，第 1 字节固定为 0xFE（十进制 254），而前面 4 个字节则用来存储前节点长度。（1 字节 8 位，最高不是能用来代表 255 吗？为啥是 254？因为 <zlend> 属性固定值为 255，要与其辨别开）
- <encoding>：1 字节、2 字节或 5 字节；用来记录节点 content 属性所保留数据的类型以及长度。
- <content>：长度不定；负责保留节点的值，能够是字节数组，也能够是整数。
压缩列表？“内存间断的双向链表”！
看到了下面这些属性，你可能不是很懂，但它其实算是一个“内存间断的双向链表”。
（本人试着演绎，如有谬误还请评论区纠正~）
为什么这么说？你想想看双向链表的几个属性：
- 头节点 head
- 尾节点 tail
- 节点 next 指针
- 节点 last 指针
而这些咱们依据下面的属性都能够得进去：
- 头节点：元素前三个属性一共固定占 10 字节，马上能找到第一个节点的地址。
- 尾节点：依据 <zltail> 属性，即尾结点的偏移字节数，间接能够失去最初一个节点的起始地位。
- entry 的 next 节点：因为内存间断，又晓得 <previous_entry_length> 和 <encoding> 的属性值，<encoding> 又蕴含 <content> 的长度，所以能够失去下一节点的起始地位。
- entry 的 last 节点：因为内存间断，又晓得 <previous_entry_length> 属性值，即前一节点的长度，所以能够失去上一个节点的起始地位。
为什么要用“内存间断的双向链表”啊？当然是为了实现压缩的特点了。
压缩体现在哪里？
- 首先能够明确压缩列表用间断内存来实现，不会造成数据之间闲暇的内存碎片，曾经体现了压缩的概念。
- 还有的就是下面属性值的长度，比方 <previous_entry_length> 属性，曾经尽可能占用起码的内存来存储长度了，当 1 字节不够时才用 5 字节来存储数据，像这样灵便的属性长度，外面还有许多。
连锁更新
既然是内存间断的，那必定又牵扯到一个老问题：牵一动员全身
如果我要新增加一个节点，必定要执行空间重调配操作，而且因为 <previous_entry_length> 属性用来记录上一个节点的长度，阈值是 254 字节，如果咱们的节点都是 250 字节到 253 字节；那么当咱们增加一个长度大于 254 字节的新节点时，就会引起“蝴蝶效应”。
删除操作也会引发这样的连锁更新，在最坏的状况下须要对压缩列表执行 N 次空间重调配操作。
但要留神的事，只管连锁更新的耗时很长，但其实实在产生的概率是很低的：
下面咱们是假如每个节点都在 250~253 字节之间，实际上，这种状况简直没有。
因为这些，ziplist 的一些操作命令的复杂度仅为 O(N)，咱们能够放心使用，不必过分放心上述假如引起的性能问题。
写在最初的最初
我是苏易困，大家也能够叫我易困，一名 Java 开发界的小学生，文章可能不是很优质，但肯定会很用心。
又一个转瞬，清明假期过来了，作为一个假期就躺着的社畜，示意本人的内驱力还是不够，不过我当初想得还是能进来转转，以前始终期盼着居家办公，但真的居家办公后还是闷得发慌，而且加上最近产生一些不开心的事件，的确须要工夫来整顿情绪。
但一码归一码，博文更新还是不能落下，redis 的根本数据结构不晓得前面还会不会持续，因为还有两个数据结构 quicklist 和 intset 我感觉没什么特地的中央，可能会从 redis 别的方面再动手写一点货色吧，也有可能会开启新的篇章吧~ 当初还不好说，大家就一起加油吧~💪
本文参加了 SegmentFault 思否征文「如何“反杀”面试官？」，欢送正在浏览的你也退出。