Redis系列之底层数据结构具体实现（压缩列表）
今天说一下Redis 列表、哈希、有序集合类型的底层实现压缩列表。
Redis有三种数据类型都使用了压缩列表实现，压缩列表最好的优点就是节省内存，由一系列特殊编码的连续内存块组成的顺序型数据结构
压缩列表结构（ziplist）
一个 ziplist 可以包含多个节点（entry）， 每个节点可以保存一个长度受限的字符数组或者整数
zlbytes：记录整个压缩列表占用的内存字节数，程序可以直接对ziplist的内存大小进行调整，无须为了计算ziplist的内存大小而遍历整个列表。zltail：记录压缩列表表尾节点距离压缩列表的起始地址有多少字节： 通过这个偏移量，程序无须遍历整个压缩列表就可以确定表尾节点的地址。zllen：记录了压缩列表包含的节点数量, 当压缩列表的元素数目超过2^16 - 2的时候，zllen会设置为2^16-1,当程序查询到值为2^16-1，就需要遍历整个压缩列表才能获取到元素数目。entryX：压缩列表包含的各个节点，节点的长度由节点保存的内容决定。zlend：特殊值0xFF（十进制255），用于标记压缩列表的末端。
虽然ziplist通过紧凑的内存布局来保存数据，节省了内存空间，但是ziplist也有一些问题需要注意。
ziplist的查找复杂度比较高
ziplist的 ZIPLIST_HEADER_SEZE的大小是固定的10字节，里面又记录了最后一个元素的偏移量，因此在ziplist中查找第一个和最后一个元素很快。
但是如果查找中间其他元素的话，需要遍历整个ziplist。
ziplist里面保存的元素越多，查找元素的时间就越多。
因此ziplist适合保存数据量比较小的数据。
ziplist有连锁更新问题
ziplist必须用一块连续的内存保存数据，所以当需要插入数据时，就会计算需要空间大小，重新申请相应的内存。如果频繁的插入数据，就会导致不断的申请新的连续的内存，影响ziplist性能问题。
上面的是其中一种，另外一种是存储真实数据的节点中有一个存储上一个节点大小的属性导致。
ziplist中 entry 的结构
<prevlen> <encoding> <entry-data>
prevlen：前一个entry的大小，用于反向遍历。encoding：编码，由于ziplist就是用来节省空间的，所以ziplist有多种编码，用来表示不同长度的字符串或整数。data：用于存储entry真实的数据；
节点的 prevlen 属性以字节为单位，编码长度可以是 1 字节或者 5 字节。
当前面节点长度小于 254 的时候，长度为 1 个字节。
当前面节点长度大于 254 的时候，1 个字节不够存了。前面第一个字节就设置为 254，后面 4 个字节才是真正的前面节点的长度。
当插入的数据大小超过下一个元素prevlen存储字节数所需空间时，就会重新申请内存。重新申请完成后，由于字节数变大，可能超过下下一个元素prevlen存储字节数所需空间。
就这样一旦插入位置后续的所有元素，都会因为前序元素的 prevlenszie 增加，而引起自身空间也要增加，这种每个元素的空间都需要增加的现象，就是连锁更新。
连锁更新一旦发生，就会导致 ziplist 占用的内存空间要多次重新分配，这就会直接影响到ziplist 的访问性能。
如果删除ziplist中某一个节点时，也有可能发生连锁更新。
结尾
既然ziplist有上面这两个问题，那么有没有其他的可以代替呢？
答案是 有。
Redis实现了ziplist的进化版quicklist（快速列表）。
作者：这可还行
链接：https://juejin.cn/post/7026360145844109349