???? 作者简介：席万里
⚡ 个人网站：
文章目录
- LIst
- 1.简介
- 2.使用场景
- 3.常用操作
- 1.写操作
- 2.读操作
- 4.底层实现
- 5.压缩列表的优化
- 1.ZIPLIST结构
- 2.ziplist更新数据
- 3.LISTPACK优化
- 6.总结（重点）
LIst
1.简介
Redis List是一组连接起来的字符串集合。
List最大的元素个数是2的32次方-1，新版本4.0之后是64次方-1。
2.使用场景
List作为一个列表存储，属于比较底层的数据结构，比如存储一批任务数据、存储一批消息等。
3.常用操作
- 创建：LPUSH、RPUSH
- 查询：LLEN、LRANGE
- 更新：LPUSH、RPUSH、LPOP、RPOP、LREN
- 删除：DEL、UNLINK
1.写操作
1、LPUSH从左侧插入，RPSH从右侧插入
2、LPOP移出并获取列表的第一个元素；RPOP移出并获取列表最后一个元素
3、LREN key count value，移出值等于value的元素，当count=0，则移出素有等于value的元素，当count>0，则从左到右移出count个，当count<0，则从右到左移出count个。返回被移除元素的数量。
4、DEL和UNLINK，DEL是同步删除命令，UNLINK是异步删除命令不会阻塞客户端。
2.读操作
1、LLEN，查看list的长度
2、LRANGE，查看从start到stop的元素
4.底层实现
3.2版本之前，List对象有两种编码方式，ZIPLIST和LINKEDLIST。
ZIPLIST使用条件：
- 列表对象保存的所有字符串对象长度都小于64字节。
- 列表对象元素个数少于512个。
LinkedList：
ZIPLIST和LInkedList相比，ZIPLIST内存更加紧凑，所以只有在列表个数或节点数据比较大的时候，才会使用到LINKEDLIST编码。
所以，ZIPLIST是为了在数据较少时节约内存，LInkedList是为了数据多时提高更新效率，而ZIPLIST数据稍多时会导致很多内存复制。
后来，引入了QUICKLIST，其实就是ZIPLIST和LInkedLIST的结合体。
原来LInkedList是单个节点，只能存一个数据，现在单个节点存的是一个ZIPLIST，即多个数据。
5.压缩列表的优化
平常说的压缩列表一般是指ZIPLIST，一种是LISTPACK 5.0引入的，直到7.0完全替代了ZIPLIST。
1.ZIPLIST结构
- zlbytes：占用4个字节，记录了整个ziplist占用的总字节数。
- zltail：占用4个字节，指向最后一个entry偏移量，用于快速定位最后一个entry。
- zllen：占用2字节，记录entry总数。
- entry：列表元素。
- zlend：ziplist结束标志，占用1字节，值等于255。
ziplist节点结构
<prevlen> <encoding> <entry-data>
prevlen：表示上一个节点的数据长度。如果前一节点的长度，也就是entry的大小 小于254字节，那么prevlen需要用1字节长的空间来保存这个长度值，255是特殊字符，被zlend占用了。
encoding：编码类型，包含了一个entry的长度信息，可用于正向遍历。
entry-data：实际的数据。
2.ziplist更新数据
更新操作可能带来连锁更新。连锁更新是指这个后移，发生了不止一次，而是多次。
什么是连锁更新？
比如增加一个头部新节点，后面依赖它的节点，需要prevlen记录它的大小，原本只用1字节记录，因为更新可能膨胀为5字节，然后这个entry的大小就也膨胀了。所以，当这个新数据插入导致的后移完成之后，还需要逐步迭代更新。
3.LISTPACK优化
ziplist需要支持LIST，LIST是双端访问的结构，所以需要能从后向前遍历。
<prevlen> <encoding> <entry-data>
其中，prevlen就表示上一个节点的数据长度，通过这个字段可以定位上一个节点的数据。
那么，我们可不可以改为不记录这个prevlen，但是又能找到上一个节点的起始位置的办法？
<encoding-type> <element-data> <element-tot-len>
encoding-type：是编码类型；element-datt：是数据内容；element-tot-len：存储整个节点除它自身的长度。
要找到上一个节点的秘密就需要element-tot-len。
element-tot-len所占用的每个字节的第一个bit用于标识是否结束。0是结束，1是继续，剩下7个bit来存储数据大小。
当我们需要找到当前元素的上一个元素时，我们可以从后向前依次查找每个字节，找到上一个Entry的element-tot-len字段的结束标识。
6.总结（重点）
1、List对象底层编码方式是什么？
3.2版本之前，List底层的编码是ziplist和LInkedlist，当ziplist的节点数量或单个节点大小超过一定阈值时，就会转换成LINKLIST。在3.2版本，结合ziplist和linklist实现了quicklist作为list的新底层编码，而在更新的版本，ziplist优化成了listpack。
2、ziplist怎么压缩数据的？
ziplist采用紧凑的内存结构，节点之间的内存空间都是连续的。ziplist的结构大致可以分为三部分，结构头、数据部分、结尾标志；结构头包含了ziplist总字节大小、ziplist节点个数、ziplist最后一个节点的偏移量；数据部分有N个节点组成，单个节点包含节点编码类型，上一个节点的长度，节点实际数据。
3、ziplist下list可以从后向前遍历吗？
对于ziplist中的每一个节点，都记录了前一个节点的长度，我们可以用当前遍历节点的首地址减去这个长度，就能找到上一个节点的首地址。
4、ziplist的不足
当ziplist的元素个数变得很多之后，查找效率就会下降；而且因为ziplist内存是连续的，当其中一个节点需要更新，或者新增节点时，就需要重新分配内存；再者因为ziplist每一个节点记录了前一个节点的长度，当其中一个节点的长度发生变化时，会导致后面的节点都需要进行更新，引发连锁更新问题。