前言

• 在之前我们已经学习了 redis 五大数据结构中的 list 结构。其内部是 linkedList 和 zipList 两种结构。这是我们已经学习的内容。之前我没有结合操作具体查看。事实上在两者中还存在一种结合体 quickList

结构演变

• 在上面我们添加了一个 key 为 zlist 的数据。通过 object encoding zlist 查看底层就是通过 quicklist 来构建的。之前在 ziplist 章节汇总我们了解到在 redis 中 hash 和 list 基本数据结构都使用了 ziplist 存储数据的。在 list 中我们确实 quicklist。这里我们提前说明下 quicklist 内部就是基于 ziplist 来实现的。

linkedList

• 在开场 quicklist 之前我们简单梳理下之前学过的 linkedList ，他是一种常见的双线链表。通过两个指针完成我们链表的构建。

C++指针

• redis 是基于内存运行的，而内存有十分的宝贵所以 redis 在设计了双线链表后觉得有点耗内存。因为指针本身也是需要开辟空间的。根据系统的不同指针占位不同。这里我总结了一下一个指针占位就是一个系统操作的基本位

• 这里基本位是什么意思呢？加入你是 64 位系统那么一个指针就是 64 位即 8 个字节。如果你是 32 位系统那么一个指针就是 32 位即 4 个字节

• 也就是说如果我在 redis 中向双向链表中存储 N 个英文字母，我们又知道一个应为字母占 1 个字节。那么这 N 个元素就是 N 的 listNode . 那么维持着 N 个 listNode 中间就需要 2*(N-1)个指针。在 64 位系统中也就是我们需要开辟将近 129 倍的空间来存储内容。上述情况我们只有 N 个字节的内容，却需要2*(N-1)*8+N个字节来构建 listNode。

• 随着节点的递增我们浪费程度越离谱。所以 redis 在双向链表的基础上结合了 ziplist 进行改良。

过渡原因

ziplist

• 在 ziplist 章节中我们知道 ziplist 是一块连续内存，是 redis 对内存的一种改良结构。ziplist 实现了内存的高使用率！

linkedlist+ziplist 好处

quicklist 引入

• quicklist 是在 redis3.2 之后引入的，笔者这里使用的是 redis6.4 方便源码好像并没有 quicklist 源码。

• 后来翻阅了之后 redis6.4 好像取消了 quicklist . 结构。所以我又特别下了一个 3.2 的版本。这里具体的是 redis3.2.4 版本！！！

庐山真面目

quicklist

• 通过他的源码我们很清晰的看出他的内部数据结构！这个大家应该很熟悉了。quicklist 可以说就是我们之前的 linkedList 结构。内部就是双向链表只不过里面的属性稍微多了点

• 通过图示是不是感觉和 linkedList 一样。

• 接下来我们看看 quicklist 中各个属性的含义吧

quicklistNode

• quicklist 只是一个抽象的概念，真正负责数据的存储的是组成 quicklist 的成员 quicklistNode 。

• 各个属性的作用

• 通过上面的属性介绍，我们也可以了解了解到 node 节点中的数据结构就是 ziplist 。在 ziplist 基础上会在进行压缩达到内存更高的使用效率！

• 关于压缩这里我们不用太去了解！主要目的就是一种编码，这种编码是无法真正使用的在使用期间 redis 会进行解码操作。在解码操作期间就是通过 recompress 属性来标记的。

insert

• 在了解 quicklist 基本结构之后我们在看看 insert 时结构会发生哪些变化！上面我们也提到了在 redis.conf 配置文件中list-max-ziplist-size属性是用来设置 quicklist 中每个节点中的 ziplist 存储的大小设置的。

两端插入

• 第一种情况就是我们需要插入的数据是在两端的。如上图所示我们在 redis.conf 配置文件中设置的list-max-ziplist-size: 2 。表示内部节点 ziplist 中 entry 个数最大为 2 。此时我们 head 头部节点中已经存储了两个内容，tail 尾部节点存储的是 1 个节点！

• 这个时候如果我们想头部添加一个元素是 obj1 。 可想而知我们是无法加入的，这个时候 redis 会重新创建一个 ziplist 结构并包含 obj1 ，将新创建的 ziplist 加入到链表的头部之后

• 而 obj2 加入尾结点时，因为尾结点的节点数是 1 还未达到峰值 2，所以直接就加入了。最终的效果图如下

中间插入

st=>start: InsertziplistInsert=>operation: 向ziplist中插入subziplistInsert=>operation: 将该ziplist拆分两个ziplist， 在对应位置加入insertNear=>operation: 插入相邻的ziplist中newZipInsert=>operation: 新建ziplist插入cond=>condition: ziplist是否可以容纳headtailCond=>condition: 插入位置在ziplist两端nearheadtailCond=>condition: 相邻ziplist是否可以容纳e=>end: 快乐的一天
st->condcond(yes)->ziplistInsertcond(no)->headtailCond(yes)->nearheadtailCondheadtailCond(no)->subziplistInsertnearheadtailCond(yes)->insertNearnearheadtailCond(no)->newZipInsert

总结

参考文献

[lzf 压缩算法](