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

29 3 月, 2021 166点热度 0人点赞 0条评论

列表对象编码

列表对象可以是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函数, 定位到双端列表指定索引上的节点, 然后通过赋值操作更新节点的值

专注着

一个奋斗在编程路上的小伙

文章评论