文章目录
- listpack
- ziplist 的级联更新
- 设计图 PK
listpack
Stream 定制的数据结构有两个：listpack 和 rax。这篇我们先讲一下 listpack。
listpack 是对 ziplist 的优化。从5中率先在streams中引入listpack，直到6后作为t_hash御用底层数据结构，redis应该是发现极致的内存使用远远不如提高redis的处理性能。
ziplist 的级联更新
这个级联更新出现的概率极低，所以在ziplist的那篇我就没写。但是它一旦出现的话就是一场灾难，而 listpack 则是为了解决这一问题而生，所以在这一篇我补上这一个知识点。
级联更新是现有压缩列表构造的一个弊端。
这个弊端源于previous_entry_length属性的设定，这个属性可能占1字节，也可能占5字节，实际占用空间大小和前一个节点大小有关。如果在某个位置新插入一个较大的节点，或者删除一个大节点后的节点，可能就会导致后面节点的previous_entry_length属性由1字节变成5字节，而因为该属性的改变也会导致该entry大小的改变，从而可能引发该entry大于等于254字节，进而导致后面的entry大小继续改变。这个改变可能会波及到整个压缩列表，所以称之为级联更新。
级联更新在最坏情况下需要对压缩列表执行N次空间重分配操作，每次重分配的复杂度是ON，级联更新最坏复杂度为ON方。
虽然级联更新存在，但是出现概率很低，几乎可以忽略不计。
设计图 PK
整体上看，listpack少了一些。其实相比较ziplist，listpack中的优化在于entry中。
entry 的内容分布为：<encode><val><backlen>
encode：节点编码格式
val：节点元素
backlen：反向遍历时使用的节点长度
