数据结构
是一个双向链表,每一个节点是一个ziplist。
如何平衡空间和时间
ziplist是一个长度不限的数据结构,链表可以无限扩展。那么有限个element,如何安排到quicklist中,才能获取存储和读写的效率平衡呢?
比如有12个元素,每个ziplist包含3个,四个节点。也可以每个ziplist包含6个,两个节点。
不同的存储方式,带来的空间影响也不一样
当每个ziplist存储元素个数很少时,带来的内存碎片也就越多,极限情况下只存储一个element,那么quicklist就退化成了一个链表。
当每个ziplist存储元素个数很多时,为一个ziplist寻找连续空间就越难,极限情况下存储所有的element,那么quicklist就退化成了一个ziplist。
redis为了将存储和读取进行平衡,开放了相应的配置
list-max-ziplist-size N
当N>0时,表示一个ziplist可存储N个元素。
当N<0时,表示一个ziplist只能存储小于等于2的-N次方kb的容量
内部节点压缩
quicklist用做list数据结构的底层实现,目的是来存储数量较多的元素。
当list很长时,最被频繁访问的是两端的数据,所以为了节省内存空间,中间的节点可以被压缩。
redis开放了相应的配置
list-compress-depth N
N表示两端不被压缩的节点个数。
其中的压缩算法为LZF,一种无损压缩算法。