前面我们使用list实现过队列 , 现在就来看一下list的底层结构
list有两种实现方式:
1. 压缩链表
压缩列表(ziplist)是Redis为了节省内存而开发的,是由一系列特殊编码的连续内存块组成的顺序型数据结构,一个压缩列表可以包含任意多个节点(entry),每个节点可以保存一个字节数组或者一个整数值。重点是内存连续
2.双端链表
prev和next两个指针 , 重点是可以从前往后也可以从后往前 , 这就可以实现lpush rpush这些指令了
因为用的链表 , 所以这也就导致了lindex指令 , 获取某个索引值的元素 , 需要遍历链表才可以获取到 , 时间复杂度是 O(n)
当列表对象可以同时满足下列两个条件时,列表对象采用压缩链表编码:
(1)列表对象保存的所有字符串元素的长度都小于64字节;
(2)列表元素保存的元素数量小于512个;
以上两个条件的上限值可以在配置文件中修改 list-max-ziplist-value选项和 list-max-ziplist-entries选项
否则采用双端链表编码
redis3.2版本以后采用的快速列表
quicklist 是一个双向链表,并且是一个ziplist的双向链表,也就是说quicklist的每个节点都是一个ziplist。结合了两者的优点
本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:[Redis] list底层的数据结构 - Python技术站