Redis的基础数据结构

Reids 所有的数据结构都以唯一的 key 字符串作为名称，然后通过这个唯一的 key 值来获取相应的 value 数据。不同的数据结构差异就在于 value 的结构不一样。

# 一、Redis 五大数据类型

【1】String（字符串）：String 是Redis 最基本的类型，一个 key 对应一个value。String 类型是二进制安全的。意思是 Redis 的 String 可以包含任何数据。一个键最大能存储 512MB。
【2】Hash（哈希）：Hash 是一个键值对集合，类似 Java 里的 Map。Redis 的 Hash 是 一个 String 类型的 filed 和 value 的映射表，hash 特别适合存储对象。
【3】List（列表）：Redis 列表是简单的字符串列表，按照插入顺序排序，可以在列表的头部或者尾部插入新的节点。
【4】Set（集合）：Redis 的 Set 是 String 类型的无序集合。集合是通过哈希表（散列表）实现的，所有添加、删除、查找的效率都是一样的。一个集合最多可以包含2^32-1个元素。
【5】Zset（sorted set：有序集合）： Reids Zset 和 Set 一样也是 String 类型元素的结合，且不允许重复的成员。不同的是每个元素都会关联一个 double 类型的分数 score。Redis 正是通过分数来为集合中的成员进行从小到大的排序。Zset 的成员是唯一的，但是分数是可以重复的。
【获得 redis常见数据类型操作命令】：链接 (opens new window)

# 二、Redis 字符串String

字符串 String 是 Reids 中最简单的数据结构，如下图所示，它的内部就是一个字符数组。

Reids 的字符串是动态字符串，是可以修改的字符串，内部结构的实现类似于 Java 的 ArrayList，采用预分配冗余空间的方式来减少内存的频繁分配，如下图所示：内部为当前字符串分配的实际空间 capacity 一般要高于实际字符串长度 len。需要注意的是字符串最大长度为 512MB。

String 常用命令： 支持简单的增删改查操作；
● SET：将字符串值 value 关联到 key。如果 key 已经持有其它值， SET 就覆盖旧值【SET key value】；
● GET：获取某个 key 的 value 值【GET key】；
● MGET：一次获得多个 key 的数据【MGET key1 key2 ...】，节省网络耗时开销；
● MSET：一次设置多个 key 的数据【MSET key1 value1 key2 value2 ...】，节省网络耗时开销；
● EXISTS：判断一个键是否存在，存在返回 1；否则返回 0【EXISTS key】；
● DEL：删除某个 key 或者一些列 key【DEL key1 key2 ...】；
● KEYS：返回匹配的 key 列表（KEYS foo* 指查找 foo 开头的 keys）【KEYS *】；
● RENAME：更改 key 的名字，如果新名字已存在则更改失败【REMANE key1 key2】；
● DBSIZE：返回当前 key 的总数【DBSIZE】；
● EXPIRE：设置某个 key 的过期时间（单位：秒）【EXPIRE key 秒数】；
● TTL：查找某个 key 的过期时间【TTL key】；
● SETEX：设置过期时间，等价于 set+expire 【SETEX key time value】；
● SETNX：如果 key 不存在则执行 set 创建，返回 1。否则不创建返回 0【SETNX key value】；
● INCR/DECR/INCRBY/DECRBY：前两个是递增 1 和递减 1 【INCR key】，后两个是指定递增和递减的数字【INCRBY KEY 倍数】。前提是一定要是数字才能进行加减；

# 三、Redis列表List

Redis 的列表相当于 Java 语言里面的 LinkedList，注意它是链表而不是数组。这就意味着 list 的插入和删除操作非常快，时间复杂度为 ，但是索引定位很慢，时间复杂度为 ，这点让人非常意外，如下图所示，列表中的每个元素都使用双向指针顺序，串起来可以同时支持向前向后遍历。当列表弹出最后一个元素之后，该数据结构被自动删除，内存被回收。Redis 的列表结构常用来做异步队列使用。将需要延后处理的任务结构体序列化成字符串，塞进 Redis 列表，另一个线程从这个列表中轮询数据进行处理。

List 常用命令： 可以通过 push，pop 操作从链表的头部或者尾部添加删除元素。list 既可以用作栈，也可以用作队列。
1）、LPUSH：将一个或多个值插入到列表头部【lpush key value1 [value2 ...]】
2）、RPUSH：从尾部加入元素（队列）先进先出【rpush key value1 [value2 ...]】
3）、LPOP：移除并获取列表中的第一个元素【lpop key】
4）、RPOP：移除并获取列表中的最后一个元素【rpop key】
5）、LRANGE：获取列表中指定范围内的元素【lrange key start stop】
6）、LLEN：获取 List 的长度【llen key】

慢操作：lindex 相对于 Java 链表的 get(int index) 方法，它需要对链表进行遍历，性能会随着参数 index 增大而变差。 ltrim 的两个参数 start_index 和 end_index 定义了一个区间，在这个区间内的值，ltrim 保留，区间之外的统统丢弃掉。我们可以通过 ltrim 实现一个定长的链表，这一点非常有用。index 可以为负数，index=-1表示倒数第一个元素，同理index=-2表示倒数第二个元素。 1）、LINDEX KEY INDEX：获取下标为 index 的元素（ 慎用）； 2）、LRANG KEY START END：根据下标区间获取 value 值； 3）、LTRIM KEY START END：根据下标截取 list，通过 ltrim key 1 0 #表示清空这个列表，因为区间范围长度为负；

快速列表：如果更深入一点，会发现 Redis 底层存储的不是一个简单的 LinkedList，而是称之为 “快速链表”(QuickList)的一个结构。首先在列表元素较少的情况下，会使用一块连续的内存存储，这个结构是 ziplist，即压缩列表。它将所有的元素彼此紧挨着一起存储，分配的是一块连续的内存。当数据比较多的时候才会改成 QuickList。因为普通的链表需要的附加指针空间太大，会浪费空间，还会增加内存的碎片化，比如某个普通链表里面存的只是 int 类型的数据，结构上还需要两个额外的指针 prev 和 next。所以 Redis 将链表和 ziplist 结合起来组成了 quicklist，也就是将多个 ziplist 使用双向指针串起来使用。如下图所示，quicklist 即满足快速的插入删除特性，又不会出现太大的空间冗余。

# 四、Redis集合Set

Redis 的集合Set 相当于 Java 语言里面的 HashSet，它内部的键值对是无序的、唯一的。它的内部实现相当于一个特殊的HashMap，HashMap 中所有的 value 都是一个 NULL 值。当集合中最后一个元素被移除后，数据结构被自动删除，内存被回收。

Set 常用命令： Set 对外提供的功能与 List 类似是一个列表的功能，特殊之处在于 set 是可以自动排重的，并且 set 提供了判断某个成员是否在一个 Set 集合内的重要接口。Redis 还为集合提供了求 交集、并集、差集 等操作。基本命令操作如下：
【1】SADD：向集合添加一个或多个成员【sadd key value1[value2...]】
【2】SISMEMBER：判断集合中是否存在 key 的成员【sismember key value】
【3】SMEMBERS：返回集合中的所有成员【smembers key】
【4】SUNION：返回所有给定集合的并集【sunion key1 [key2...]】
【5】SINTER：返回所有给定集合的交集【sinter key1 [key2...]】
【6】SDIFF：返回所有给定集合的差集【sinter key1 [key2...]】

# 五、有序集合Sorted sets

Zset 可能是 Redis 提供的最有特色的数据结构，它也是在面试中面试官最爱问的数据结构。它类似于 Java 的 SortedSet 和 HashMap 的结合体，一方面它是一个 set，保证了内部的唯一性，另一方面它可以给每个 value 赋予一个 score，代表这个 value 的排序权重。它的内部实现使用 “跳跃列表” 的数据结构；zset 中最后一个 value 被移除后，数据结构被自动删除，内存被回收；Redis 有序集合非常适合与那些有序无重复数据的存储，例如：游戏开发中的排行榜、登记榜、经验榜等。如果沿用传统的方式，一般是通过后端的定时任务去跑数据来完成排行榜。这种方法一方面无法满足产品对功能实时性的要求，另一方面也消耗了服务器的资源。

ZSet 常用命令： 常用命令如下：
1）、ZADD：向集合中添加一个或多个元素，或者更新已存在的元素【zadd key score1 member1 [score2 member2]】；
2）、ZRANGE：通过索引区间返回有序集合指定的成员【zrange key start stop [WITHSCORES]】；
3）、ZRANK：返回集合中指定成员的索引(下标)【zrank key member】；
4）、ZREM：移除有序集合中一个或多个成员【zrem key member1 [member2 ...]】；
5）、ZREVRANGE：逆向返回有序集中指定区间的成员，通过索引分数从高到低【zrevrange key start stop [WITHSCORES]】；
6）、ZCARD：相当于 count()【zcard key】；
7）、ZSCORE：获取指定 value 的 score【zscore key value】；
8）、ZRANGBYSCORE：根据分值区间遍历 zset【zrangbyscore key start end】；

跳跃列表： zset 内部的排序功能是通过“跳跃列表”数据结构来实现，它的结构非常特殊，也比较复杂。因为 zset 要支持随机的插入和删除，所以它不宜使用数组来表示。我们先看一个普通的链表结构：

此链表将按照 score 进行排序，当我们插入一个新元素的时候，要定位到特定的位置，才可以继续保证链表是有序的。通常我们会通过二分查找来找到插入点，但是二分查找的对象必须是数组，只有数组才可以支持快速位置定位，链表做不到；因此就出现了跳跃列表数据结构； 跳跃列表就类似一个 B树（层级制），最下面一层所有的元素会串起来。然后每隔几个元素挑选一个代表，再将这几个代表使用另外一个指针串起来。然后在这些代表里再调出二级代表，再串起来。最终形成一个金字塔机构。“跳跃列表”之所以“跳跃”是因为内部元素可能“身兼数职”，比如如下图所示：中间这个元素，同时处于L0、L1和L2层中，可以快速在不同层次之间进行“跳跃”。

定位插入点时，现在顶层进行定位，然后下潜到下一级定位，一直下潜到最底层找到合适的位置，将新元素插进去。那么新元素如何才有机会“身兼数职”呢？跳跃列表采取一种随机策略决定新元素可以兼职到几层。首先位于 L0 层的概率为是 100%，而兼职L1 层的概率有 50%，到L2层的概率 25%，到L3层只有12.5%的概率，一次类推，一直随机到最顶层L31层。绝大多数元素都过不了几层，只有极少数元素可以深入到顶层。列表中的元素越多，够深入的层次就越深，元素能进入到顶层的可能性就会大。

# 六、哈希Hash

Redis 的字典（Hash）相当于Java 语言里面的 HashMap，它是无序字典，内部存储了很多键值对。实现结构与 Java 的 HashMap 是一样的，都是“数组+链表”（JDK1.7）。不同的是，Redis 的字典值只能是字符串，另外他们 rehash（扩容后需要重新计算hash值，分配地址）的方式不一样，因为 Java 的HashMap 在字典很大时，rehash 是个耗时的操作，需要一次性全部rehash。Redis 追求性能，不能堵塞服务，所以采用了渐进式 rehash 策略。渐进式 rehash 会在 rehash 时保留新旧两个 hash 结构，查询时会同时查询两个 hash 结构，然后在后续的定时任务以及 hash 操作指令中，循环渐进地将旧 hash 的内容一点点地迁移到新的 hash 结构中。当迁移完成了，就会使用新的 hash 结构取而代之。

Hash 常用命令： 当 hash 移除最后一个元素之后，该数据结构被自动删除，内存被回收。字典常用命令如下：
【1】HSET：将哈希表 key 中的字段 field 的值设为 value【hset key field value】；
【2】HGET：获取存储在哈希表中指定字段的值【hget key field】；
【3】HGETALL：获取哈希表中，指定 key 的所有字段和值【hgetall key】；
【4】HDEL：删除一个或多个哈希表字段【hdel key field1 [field2...]】；
【5】HMSET：同时将多个 field-value（域-值）设置到哈希表 key【hmset key field value [field1 value1 ...]】；
【6】HLEN：获取 key 中存储的元素个数【hlen key】；

# 七、Hyperloglog

当需要做计数统计场景，都可以使用 hyperloglog，只要允许容错，它有 0.81%的错误率，如果不允许容错，就可以使用 set或者自己的数据类型即可。优点是节省内存：占用的内存是固定的,如果要存数据，hyperloglog存 2^64的数据只需要占用 12kb内存。