Redis数据结构和内部编码--列表(list)
Redis数据结构和内部编码--列表(list)
一.概念
列表用来存储多个有序的字符串，列表中的每个字符串成为元素，一个列表最多可以存储2^32-1个元素。列表是一种比较灵活的数据结构，它可以充当栈和队列的角色。
列表类型有两个特点：
1. 列表中的元素是有序的，这就意味着可以通过下表获取某个元素或者某个范围内的元素。
2. 列表中的元素可以是重复的
二. 命令
2.1 从右边插入元素
命令：rpush key value1 value2..
例如：rpush list v1 v2
返回：2，代码列表当前的长度。
lrange list 0 -1
返回：v1
V2
2.2 从左边插入元素
命令：lpush key value1 value2..
例如：lpush list v1 v2
lrange list 0 -1
返回：v2
V1
2.3 向某个元素前或者后插入元素
命令： linsert key before|after select value
例如： lpush list v1 v2 v3 v4 v5
linsert list before v3 insert1
返回：6，返回结果代表当前命令的长度
lrange list 0 -1
返回：
1) "v5"
2) "v4"
3) "insert1"
4) "v3"
5) "v2"
6) "v1"
2.4 获取指定范围内的元素列表
命令：lrange key start end
start和end代表索引下标，从左向右是0到N-1，从右向左是-1到-N
例如：lpush list v1 v2
lrange list 0 -1
返回：v2
V1
2.5 获取列表指定索引下标的元素
命令：lindex key index
例如：lpush list v1 v2 v3 v4 v5
Lindex list 3
返回：v3
2.6 获取列表长度
命令：llen key
例如：lpush list v1 v2 v3 v4 v5
llen list
返回：5
2.7 从列表左侧弹出元素
命令：lpop key
例如：lpush list v1 v2 v3 v4 v5
rpop list
返回：v1，返回被删除的元素
再次查看list中的元素，lrange list 0 -1
返回：v2
v3
v4
v5
2.8 从列表右侧弹出元素
命令：rpop key
例如：lpush list v1 v2 v3 v4 v5
rpop list
返回：v5，返回被删除的元素
再次查看list中的元素，lrange list 0 -1
返回：v1
v2
v3
v4
2.9 删除指定元素
命令：lerm key count value 从列表中找到等于value的元素进行删除，根据count的不同分三种情况：
（1） count>0,从左向右删除最多count个值等于value的元素
（2） count<0,从右向左删除最多count绝对值个值等于value的元素
（3） count=0,删除所有
例如：lpush list v1 v2 v3 v2 v5
lrem list 0 v2
返回：2
再次查看list中的元素，lrange list 0 -1
返回：v1
v3
v5
2.10 按照索引范围修剪列表
命令：ltrim key start end
例如：lpush list v1 v2 v3 v4 v5
ltrim list 1 3
返回：ok
再次查看list中的元素，lrange list 0 -1
返回：v2
v3
v4
2.11 修改指定索引下标的元素
命令：lset key index value
例如：lpush list v1 v2 v3 v4 v5
lset list 3 v8
返回：ok
再次查看list中的元素，lrange list 0 -1
返回：v1
v2
v3
v8
v5
2.12 阻塞式弹出
（1）命令：blpop key[key1 …] timeout 从列表左侧弹出元素，阻塞时间为timeout秒，超过timeout秒则客户端返回，如果timeout为0，则始终阻塞。
（2）命令：brpop key[key1 …] timeout 从列表右侧弹出元素，阻塞时间为timeout秒，超过timeout秒则客户端返回，如果timeout为0，则始终阻塞。
例如：blpop list 3
返回：此时由于列表list中没有任何元素，客户端阻塞3秒，如果三秒钟内有其他客户端向list列表中加入元素，则此客户端立即返回。否则阻塞3秒钟，然后返回nil
注：如果多个客户端执行blpop list，最先执行命令的客户端率先返回数值。
三.list类型命令的时间复杂度
四.内部编码
hash类型的内部编码有两种：
（1） ziplist（压缩列表）
当列表的元素个数小于list-max-ziplist-entries配置（默认512个），同时所有值都小于list-maxziplist-value配置（默认为64字节），Redis会使用ziplist做为哈希的内部实现。Ziplist可以使用更加紧凑的结构来实现多个元素的连续存储，所以在节省内存方面更加优秀。
压缩列表的优点：
压缩列表ziplist结构本身就是一个连续的内存块，由表头、若干个entry节点和压缩列表尾部标识符zlend组成，通过一系列编码规则，提高内存的利用率，使用于存储整数和短字符串。
压缩列表的缺点：
每次插入或删除一个元素时，都需要进行频繁的调用realloc()函数进行内存的扩展或减小，然后进行数据”搬移”，甚至可能引发连锁更新，造成严重效率的损失。
（2） linkedlist（链表）
当列表类型无法满足ziplist要求时，redis会采用linkedlist做为列表的内部实现。
（3）quicklist（快速列表）
quicklist结构是在Redis 3.2版本中新加的数据结构，用在列表的底层实现
quicklist宏观上是一个双向链表，因此，它具有一个双向链表的有点，进行插入或删除操作时非常方便，虽然复杂度为O(n)，但是不需要内存的复制，提高了效率，而且访问两端元素复杂度为O(1)。
quicklist微观上是一片片entry节点，每一片entry节点内存连续且顺序存储，可以通过二分查找以 log2(n) 的复杂度进行定位。
quicklist的结构为什么这样设计呢？总结起来，大概又是一个空间和时间的折中：
· 双向链表便于在表的两端进行push和pop操作，但是它的内存开销比较大。首先，它在每个节点上除了要保存数据之外，还要额外保存两个指针；其次，双向链表的各个节点是单独的内存块，地址不连续，节点多了容易产生内存碎片。
· ziplist由于是一整块连续内存，所以存储效率很高。但是，它不利于修改操作，每次数据变动都会引发一次内存的realloc。特别是当ziplist长度很长的时候，一次realloc可能会导致大批量的数据拷贝，进一步降低性能。
在quicklist表头结构中，有两个成员是fill和compress，其中” : “是位域运算符，表示fill占int类型32位中的16位，compress也占16位。
fill和compress的配置文件是redis.conf。
- fill成员对应的配置：list-max-ziplist-size -2
- 当数字为负数，表示以下含义：
- -1 每个quicklistNode节点的ziplist字节大小不能超过4kb。（建议）
- -2 每个quicklistNode节点的ziplist字节大小不能超过8kb。（默认配置）
- -3 每个quicklistNode节点的ziplist字节大小不能超过16kb。（一般不建议）
- -4 每个quicklistNode节点的ziplist字节大小不能超过32kb。（不建议）
- -5 每个quicklistNode节点的ziplist字节大小不能超过64kb。（正常工作量不建议）
- 当数字为正数，表示：ziplist结构所最多包含的entry个数。最大值为 215。
- compress成员对应的配置：list-compress-depth 0
- 后面的数字有以下含义：
- 0 表示不压缩。（默认）
- 1 表示quicklist列表的两端各有1个节点不压缩，中间的节点压缩。
- 2 表示quicklist列表的两端各有2个节点不压缩，中间的节点压缩。
- 3 表示quicklist列表的两端各有3个节点不压缩，中间的节点压缩。
- 以此类推，最大为 216。
五. 列表的使用场景及方案
（1）lpush+lpop=栈
（2）lpush+rpop=队列
（3）lpush+ltrim=有限集合
（4）lpush+brpop=消息队列