Redis-01a数据结构

Redis是一个K-V的数据库，“V” 的数据类型分为：String、Hash、List、Set、Sorted Set。

String

String 数据结构是简单的 key-value 类型，value 不仅可以是 String，也可以是数字（当数字类型用 Long 可以表示的时候encoding 就是整型，其他都存储在 sdshdr 当做字符串）。

sds是在Redis中被广泛使用的字符串结构，它的全称是Simple Dynamic String。参考 Redis内部数据结构详解(2)——sds @ref

String相关命令包括 SET/GET类命令，对字符串的值APPEND/SETRANGE操作，还包括同时设置值和过期时间的原子操作SETEX，但是其他数据类型没有类似SETEX的原子操作。

SET key value：设置key关联的字符串
GET key：返回key关联的字符串
APPEND key value：在字符串后追加value
STRLEN key：返回字符串长度
SETRANGE key 0 "xxx"：把key对应的字符串从0开始，用“xxx”覆盖。时间复杂度O(M)， M 为 value 参数的长度。
INCR key：将 key 中储存的数字值+1，数字范围是有符号long
INCRBY key increment：将 key 所储存的值加上增量 increment
DECR key：将 key 中储存的数字值减一。
DECRBY by decrement：将 key 所储存的值减去减量 decrement 。

过期时间：

SETEX key seconds value：将值 value 关联到 key ，并将 key 的生存时间设为 seconds (以秒为单位)。 SETEX 是一个原子性(atomic)操作

批量操作：

MGET key1 key2：返回所有(一个或多个)给定 key 的值。时间复杂度O(N) ，N 为给定 key1..key2 的数量。
MSET key1 value2 key1 value2：设置key1…key2对应的字符串。时间复杂度：O(N)， N 为要设置的 key 数量。

BIT操作：

SETBIT key offset value：对key所储存的字符串值，设置或清除指定偏移量上的位(bit)，value只能是0或1，offset小于2^32（512MB）
GETBIT key offset：返回offset位上的值（0/1）
BITCOUNT key ：计算给定字符串中，被设置为 1 的比特位的数量。

HashMap

字典实现，key对应的内容是由field-value组成的键值对。

HSET key field value：将哈希表 key 中的域 field 的值设为 value，O(1)
HGET key field：返回哈希表 key 中给定域 field 的值。
HKEYS key：返回哈希表 key 中的所有域。时间复杂度：O(N)， N 为哈希表的大小。
HGETALL key ：返回哈希表 key 中所有的域和值。时间复杂度：O(N)， N 为哈希表的大小。
HVALS key：返回哈希表 key 中所有域的值。时间复杂度：O(N)， N 为哈希表的大小。
HEXISTS key field：查看哈希表 key 中，给定域 field 是否存在。
HSCAN key cursor：命令用于迭代哈希键中的键值对。具体信息请参考 SCAN 命令。
HDEL key field [field ...]：删除哈希表 key 中的一个或多个指定域，不存在的域将被忽略。时间复杂度：O(N)， N 为要删除的域的数量。
HLEN key：返回键值对数量
HINCRBY key field increment ：为哈希表 key 中的域 field 的值加上增量 increment 。

批量操作：

HMSET key field1 value1 field2 value2：同时将多个 field-value (域-值)对设置到哈希表 key 中。O(N)， N 为 field-value 对的数量。
HMGET field1 field2：返回哈希表 key 中，一个或多个给定域的值。O(N)， N 为 field-value 对的数量。

List

双向队列，队列的 L/R 端都可以进行 POP 和 PUSH 操作：

LPOP key ：移除并返回列表 key 的头元素。
LPUSH key value [value ...] ：将一个或多个值 value 插入到列表 key 的表头
RPUSH key value [value ...]：将一个或多个值 value 插入到列表 key 的表尾(最右边)。
RPOP key：移除并返回列表 key 的尾元素。
LLEN key ：返回列表 key 的长度。

随机查询 & 插入：

LINDEX key index ：返回列表 key 中，下标为 index 的元素。时间复杂度：O(N)， N 为到达下标 index 过程中经过的元素数量。
LINSERT key BEFORE|AFTER pivot value ：将值 value 插入到列表 key 当中，位于值 pivot 之前或之后。时间复杂度：O(N)， N 为寻找 pivot 过程中经过的元素数量。
- LINSERT mylist BEFORE "World" "There" ：会先在List寻找”World”，找到后在”World”之前插入”There”

阻塞L/R端弹出：

BLPOP key [key ...] timeout ：BLPOP 是列表的阻塞式(blocking)弹出原语。它是 LPOP 命令的阻塞版本，当给定列表内没有任何元素可供弹出的时候，连接将被 BLPOP 命令阻塞，直到等待超时或发现可弹出元素为止。
BRPOP key [key ...] timeout ：参考如上

Set

不重复元素的集合

SADD key v1 v2 ：添加多个值到集合key之中，时间复杂度：O(N)， N 是被添加的元素的数量。
SPOP key ：移除并返回集合中的一个随机元素。
SMEMBERS key：返回集合 key 中的所有成员。时间复杂度：O(N)， N 为集合的元素数量。
SSREM key member [member ...]：移除集合 key 中的一个或多个 member 元素，时间复杂度：O(N)， N 为给定 member 元素的数量。
SISMEMBER key member：判断 member 元素是否集合 key 的成员。时间复杂度：O(1)
SCARD key：返回集合中元素的数量。时间复杂度：O(1)
SSCAN key cursor：详细信息请参考 SCAN 命令。

交/并/差集：

SINTER key1 [key ...]：返回 key.. 对应集合的交集，时间复杂度为 O(N * M)， N 为给定集合当中基数最小的集合， M 为给定集合的个数。
SUNION key1 [key ...]：返回 key.. 对应集合的并集。时间复杂度为 O(N)， N 是所有给定集合的成员数量之和。
SDIFF key1 [key ...]：用第一个集合与第二个集合做差集，所得结果再与第三个集合做差集，依次向后类推。

➤ 交集的实现：

对各个集合按照元素个数由少到多进行排序。这个排序有利于后面计算的时候从最小的集合开始，需要处理的元素个数较少。
对排序后第一个集合（也就是最小集合）进行遍历，对于它的每一个元素，依次在后面的所有集合中进行查找。只有在所有集合中都能找到的元素，才加入到最后的结果集合中。

➤ 差集的实现：两种可能的算法，在计算差集的开始部分，会先分别估算一下两种算法预期的时间复杂度，然后选择复杂度低的算法来进行运算。

第一种算法：

对第一个集合进行遍历，对于它的每一个元素，依次在后面的所有集合中进行查找。只有在所有集合中都找不到的元素，才加入到最后的结果集合中。

这种算法的时间复杂度为 O(N*M)，其中N是第一个集合的元素个数，M是集合数目。

第二种算法：

将第一个集合的所有元素都加入到一个中间集合中。
遍历后面所有的集合，对于碰到的每一个元素，从中间集合中删掉它。
最后中间集合剩下的元素就构成了差集。

这种算法的时间复杂度为 O(N)，其中 N 是所有集合的元素个数总和；

Sorted Set

Sorted Sets是将 Set 中的元素增加了一个权重参数 score，使得集合中的元素能够按 score 进行有序排列

ZADD key score member [[score member] [score member] ...]：将一个或多个 member 元素及其 score 值加入到有序集 key 当中。时间复杂度：O(M*log(N))， N 是有序集的基数， M 为成功添加的新成员的数量。
ZSCORE key member：返回有序集 key中，成员 member的 score值。时间复杂度：O(1)
ZRANGE key start stop：返回有序集 key中指定区间内的成员。其中成员的位置按 score值递增(从小到大)来排序。复杂度：O(log(N)+M)， N 为有序集的基数，而 M 为结果集的基数。
ZINCRBY key increment member：为有序集 key的成员 member的 score值加上增量 increment。时间复杂度：O(log(N))
ZREVRANK key member：返回有序集 key中成员 member的排名，score 值最大的成员排名为 0 。复杂度O(log(N))
ZCOUNT key min max：返回有序集 key 中， score值在 min和 max之间(默认包括)的成员的数量。时间复杂度：O(log(N))， N 为有序集的基数。
ZCARD key：返回key对应的集合的长度。