redis数据结构-列表对象(List)

列表对象编码

列表对象可以是ziplist或者linkedlist两种。

编码转换条件

列表对象保存的所有字符串元素的长度都小于64字节
列表对象保存的元素数量小于512个

不能满足这两个条件的列表对象需要使用linkedlist编码

编码转换条件修改

list-max-ziplist-value: 用于修改能够保存的最大的字节数
list-max-ziplist-entries: 用于修改压缩列表在达到最大节点时, 就将压缩列表转换为链表

# Similarly to hashes, small lists are also encoded in a special way in order
# to save a lot of space. The special representation is only used when
# you are under the following limits:
list-max-ziplist-entries 512
list-max-ziplist-value 64

测试实例

redis> EVAL "for i = 1, 512 do redis.call('RPUSH', KEYS[1], i)end" 1 "integers"
(nil)

redis> OBJECT ENCODING integers
"ziplist"

redis> RPUSH integers 513
(integer) 513

redis> OBJECT ENCODING integers
"linkedlist"

列表命令

命令	ziplist编码的实现方法	linkedlist编码的实现方法
LPUSH	调用`ziplistPush`函数, 将新元素推入到压缩列表的表头(平均`O(N)`, 最坏 `O(N^2)`)	调用`listAddNodeHead`函数, 将新元素推入到双端链表的表头
RPUSH	调用`ziplistPush`函数, 将新元素推入到压缩列表表尾(平均`O(N)`, 最坏 `O(N^2)`)	调用`listAddNodeTail`函数, 将新元素推入到双端链表的表尾
LPOP	调用`ziplistIndex`函数定位压缩列表的表头节点, 在向用户返回节点所保存的元素之后, 调用`zipListDelete`函数删除表头节点(`O(N)`)	调用`listFirst`函数定位双端列表的表头节点, 在向用户返回节点所保存的元素之后, 调用`listDelNode`函数删除表头节点
RPOP	调用`ziplistIndex`函数点位压缩列表的表尾节点, 在向用户返回节点所保存的元素之后, 调用`ziplistDelete`函数删除表尾节点(`O(N)`)	调用`listLast`函数定位双端链表的表尾节点, 在向用户返回节点所保存的元素之后, 调用`listDelNode`函数删除表尾节点
LINDEX	调用`ziplistIndex`函数定位搜索列表中的指定节点, 然后返回节点所保存的元素(`O(N)`)(数量小于`65535`是为`O(1)`, 大于`65535`时为`O(N)`)	调用`listIndex`函数定位双端列表中的指定节点, 然后返回节点所保存的元素
LLEN	调用`ziplistLen`函数返回压缩列表的长度	调用`listLength`函数返回双端链表的长度
LINSERT	插入新节点到压缩列表表头或者表尾时, 使用`ziplistPush`函数;插入新节点到压缩类表的其他位置时, 使用`ziplistInsert`函数(平均`O(N)`, 最坏`O(N^2)`)	调用`listInsertNode`函数, 将新节点插入到双端类表指定位置
LREM	遍历压缩列表节点, 并调用`ziplistDelete`函数删除包含了给定元素的节点(平均`O(N)`, 最坏`O(N^2)`)	遍历双端链表节点, 并调用`listDelNode`函数删除包含了给定元素的节点
LTRIM	调用`ziplistDeleteRange`函数, 删除压缩列表中所有不在指定范围内的节点(平均`O(N)`, 最坏`O(N^2)`)	遍历双端链表节点, 并调用`listDelNode`函数删除链表中所有不在指定范围内的节点
LSET	调用`ziplistDelete`函数, 先删除压缩列表指定所以上的现有节点, 然后调用`ziplistInsert`函数, 将一个包含给定元素的新节点插入到相同索引上面(平均`O(N)`, 最坏`O(N^2)`)	调用`listInsert`函数, 定位到双端列表指定索引上的节点, 然后通过赋值操作更新节点的值