![Redis数据结构](https://cdn.learnku.com/uploads/images/202103/03/50944/ZFQn0rM34w.png!large) ## String 字符串 ### 字符串常用操作 ```cmd SET key value # 存入字符串键值对 MSET key value [key value ...] # 批量存储字符串键值对 SETNX key value # 存入一个不存在的字符串键值对 GET key # 获取一个字符串键值 MGET key [key ...] # 批量获取字符串键值 DEL key [key ...] # 删除一个键 EXPIRE key seconds # 设置一个键的过期时间(秒) ``` ### 原子加减 ```cmd INCR key # 将key中储存的数字值加1 DECR key # 将key中储存的数字值减1 INCRBY key increment # 将key所储存的值加上increment DECRBY key decrement # 将key所储存的值减去decrement ``` ### SDS 结构定义 SDS（Simple Dynamic String 简单动态字符串）是 Redis 里面的一种结构，通过它对字符串的操作进行了很多的优化操作。 ```c struct stdhdr { int len // 记录 buff 数组中已使用字节的数量 int free // 记录 buff 数组中未使用字节的数量 char buff[] // 字节数组，用于保存字符串 } ``` ![Redis-SDS示例](https://cdn.learnku.com/uploads/images/202103/03/50944/IudXgFC0DZ.png!large) - len：值为4， 表示这个 SDS 保存一个四字节长的字符串。 - free：值为0，表示这个 SDS 没有分配任何未使用空间。 - buff：值为一个 char 类型数组，分别保存 `'L' 'i' 'n' 'k'` 4个字符，最后一个字节保存`'\0'`。 ### SDS 与 C 字符串的区别 1. 因为 C 字符串并没有记录字符串的长度信息，所以在获取 C 字符串长度的时候必须遍历整个 C 字符串（代表字符串结尾的空字符'\0'不计算进去），时间复杂度就是O(N)；SDS 有 len 属性记录了长度，所以获取长度的时间复杂度仅为O(1)。 2. C 字符串容易缓冲区溢出，而 SDS 的空间分配策略则不会。当需要操作字符串时，会先检测空间大小，如果不满足，则需要对空间做扩展。 3. C 在对字符串做修改时，因为没有记录长度信息，所以需要频繁对内存做分配，而 SDS 通过 free 属性来记录未使用的空间，实现空间预分配和惰性空间释放。 4. SDS 是二进制安全的，除了可以储存字符串以外还可以储存二进制文件（如图片、音频，视频等文件的二进制数据）；而 C 字符串是以空字符串作为结束符，一些图片中含有结束符，因此不是二进制安全的。 ### 空间预分配 空间预分配用于优化 SDS 的字符串增长操作，当对 SDS 字符做修改时，不仅会分配所需要的空间，还会为 SDS 分配额外的未使用空间。 > 分配未使用空间策略：当修改字符串后的长度 len 小于 1MB，就会预分配和 len 一样长度的空间；若是 len 大于 1MB，free 分配的空间大小就为 1MB ### 惰性空间释放 惰性空间释放用于优于 SDS 的字符串缩短操作，当缩短 SDS 字符串时，程序不立即使用内存重分配回收多出来的字节，而是用 free 属性记录，下次要用时，查看 free 的大小，避免重复分配了。 ## List 列表 Redis中的列表在3.2之前的版本是使用 ziplist 和 linkedlist 进行实现的。在3.2之后的版本就是引入了 quicklist。 linkedlist 和 quicklist 的底层实现是采用链表进行实现，Redis实现了自己的链表结构。 ### List 常用操作 ```cmd LPUSH key value [value ...] # 将一个或多个值value插入到key列表的表头(最左边) RPUSH key value [value ...] # 将一个或多个值value插入到key列表的表尾(最右边) LPOP key # 移除并返回key列表的头元素 RPOP key # 移除并返回key列表的尾元素 LRANGE key start stop # 返回列表key中指定区间内的元素，区间以偏移量start和stop指定 BLPOP key [key ...] timeout # 从key列表表头弹出一个元素，若列表中没有元素，阻塞等待timeout秒。如果timeout=0阻塞等待 BRPOP key [key ...] timeout # 从key列表表尾弹出一个元素，若列表中没有元素，阻塞等待timeout秒。如果timeout=0阻塞等待 ``` ### 使用 List 构造数据结构 - Stack（栈） = LPUSH + LPOP 左进左出 - Queue（队列） = LPUSH + RPOP 左进右出 - Blocking MQ（阻塞队列）= LPUSH + BRPOP 左进右出（阻塞） ## Hash 哈希表 Hash 对象的实现方式有两种分别是 ziplist、hashtable。 Redis 的数据库使用字典作为底层实现的，通过 key 和 value 的键值对形式，代表了数据库中全部数据。而且，所有对数据库的增删查改的命令都是建立在对字典的操作上。 ### Hash 常用操作 ```cmd HSET key field value # 存储一个哈希表key的键值 HSETNX key field value # 存储一个不存在的哈希表key的键值 HMSET key field value [field value ...] # 在一个哈希表key中存储多个键值对 HGET key field # 获取哈希表key对应的field键值 HMGET key field [field ...] # 批量获取哈希表key中多个field键值 HDEL key field [field ...] # 删除哈希表key中的field键值 HLEN key # 返回哈希表key中field的数量 HGETALL key # 返回哈希表key中所有的键值 HINCRBY key field increment # 为哈希表key中field键的值加上增量increment ``` ### 字典结构 字典类型的底层就是 hashtable 实现的，明白了字典的底层实现原理也就是明白了 hashtable 的实现原理。hashtable 在新增时会通过 key 计算出数组下标：hashtable 中计算出 hash 值后，还要通过 sizemask 属性和哈希值再次得到数组下标。 ![Redis-字典结构图](https://cdn.learnku.com/uploads/images/202103/03/50944/U1y3TyfegB.png!large) - dict 结构内部包含两个 hashtable，通常情况下只有一个 hashtable 是有值的。但是在 dict 扩容缩容时，需要分配新的 hashtable，然后进行渐进式搬迁，这时候两个 hashtable 存储的分别是旧的 hashtable 和新的 hashtable。待搬迁结束后，旧的 hashtable 被删除，新的 hashtable 取而代之。 ### hash 冲突 假如 hashtable 中不同的 key 通过计算得到同一个 index，就会形成单向链表（链地址法），如下图所示： ![Redis-hash冲突](https://cdn.learnku.com/uploads/images/202103/03/50944/WmeSINFrgL.png!large) ### rehash 在字典的底层实现中，value 对象（ht[0] 用来最开始存储数据的 和 ht[1]）以每一个dictEntry的对象进行存储，当 hash 表中的存放的键值对不断的增加或者减少时，需要对 hash表进行一个扩展或者收缩。 - 扩展操作：ht[1] 扩展的大小是比当前 ht[0].used 值的二倍大的第一个 2 的整数幂； - 收缩操作：ht[0].used 的第一个大于等于的 2 的整数幂。 ht[0] 是存放数据的 table，作为非扩容时容器。ht[1] 只有正在进行扩容时才会使用，它也是存放数据的 table，长度为ht[0]的两倍。当 ht[0] 上的所有的键值对都 rehash 到 ht[1] 中，会重新计算所有的数组下标值，当数据迁移完后ht[0]就会被释放，然后将ht[1]改为ht[0]，并新创建 ht[1]，为下一次的扩展和收缩做准备。 ### 渐进式 rehash 如果 hash 结构很大，一次完整 rehash 的过程就会耗时很长。采用了渐进式 rehash ，它会同时保留两个新旧 hash 结构，在后续的定时任务以及 hash 结构的读写指令中将旧结构的元素逐渐迁移到新的结构中。这样就可以避免因扩容导致的线程卡顿现象。如果这时有其他线程进行读操作，会先去 ht[0] 中找，找不到再去 ht[1] 中找。如果进行写操作，会直接写在 ht[1] 中。 ## Set 集合 Redis 中列表和集合都可以用来存储字符串，但是 Set 是不可重复的集合，而 List 列表可以存储相同的字符串。Set 的底层实现是 HashTable 和 intset。 ### Set 常用操作 ```cmd SADD key member [member ...] # 往集合key中存入元素，元素存在则忽略，若key不存在则新建 SREM key member [member ...] # 从集合key中删除元素 SMEMBERS key # 获取集合key中所有元素 SISMEMBER key member # 判断member元素是否存在于集合key中 SRANDMEMBER key [count] # 从集合key中选出count个元素 元素不从key中删除 SPOP key [count] # 从集合key中选出count个元素 元素从key中删除 ``` ### Set 运算操作 ```cmd SINTER key [key ...] # 交集运算 SINTERSTORE destination key [key ...] # 将交集结果存入新集合destination中 SUNION key [key ...] # 并集运算 SUNION destination key [key ...] # 将并集结果存入新集合destination中 SDIFF key [key ...] # 差集运算 SDIFFSTORE destination key [key ...] # 将差集结果存入新集合destination ``` ## ZSet 有序集合 ### ZSet 常用操作 ```cmd ZADD key score member [[score member] ...] # 往有序集合key中加入带分值元素 ZREM key member [member ...] # 从有序集合key中删除元素 ZScore key member # 返回有序集合key中元素member的分值 ZINCRBY key increment member # 为有序集合key中元素member的分值加上increment ZCARD key # 返回有序集合key中元素个数 ZRANGE key start stop [WITHSCORES] # 正序获取有序集合key从start下标到stop下标的元素 ZREVRANGE start stop [WITHSCORES] # 倒序获取有序集合key从start下标到stop下标的元素 ``` ### ZSet 运算操作 ```cmd ZUNIONSTORE destkey numkeys key [key ...] # 并集计算 destkey: 新生成集合 numkeys：后面所有key的集合数量 ZINTERSTORE destkey numkeys key [key ...] # 交集计算 ``` ### 编码选择 ![Redis-zset编码选择](https://cdn.learnku.com/uploads/images/202103/03/50944/x4BHnlNVod.png!large) 在通过 ZADD 命令添加第一个元素时， 通过检查输入的第一个元素来决定该创建什么编码的有序集。如果第一个元素符合以下条件的话， 就创建一个 `REDIS_ENCODING_ZIPLIST` 编码的有序集： - 服务器属性 `server.zset_max_ziplist_entries` 的值大于 `0` （默认为 `128` ）。 - 元素的 `member` 长度小于服务器属性 `server.zset_max_ziplist_value` 的值（默认为 `64` ）。 否则，程序就创建一个 `REDIS_ENCODING_SKIPLIST` 编码的有序集。 ### ziplist ziplist（压缩列表）是一组连续内存块组成的顺序的数据结构，能够节省空间（所以称为压缩列表）。压缩列表中使用多个节点来存储数据。结构图如下： ![Redis-ziplist结构图](https://cdn.learnku.com/uploads/images/202103/03/50944/z6x8oLXlBa.png!large) - zlbytes： 四个字节。用于存储压缩列表所占用的字节。当重新分配内存的时候使用，不需要遍历整个列表来计算内存大小。 - zltail： 四个字节。表示 ziplist 表中最后一个 entry 在 ziplist 中的偏移字节数。不用遍历整个 ziplist 也可以很方便地找到最后一个 entry ，从而可以在 ziplist 尾端快速地执行 push 或 pop 操作。 - zllen： 两个字节。表示 ziplist 中数据项 entry 的个数。 - entry：表示真正存放数据的数据项，长度不定。一个数据项 entry 也有它自己的内部结构。 - zlend， ziplist 最后1个字节，值固定等于 255，是一个结束标记。 - previous length（pre_entry_length）： 表示前一个数据节点占用的总字节数，这个字段的用处是为了让 ziplist 能够从后向前遍历。 - encoding（encoding&cur_entry_length）：表示当前数据节点 content 的内容类型以及长度。 - content（data）：表示当前节点存储的数据。 ### skiplist skiplist也叫做跳跃表，跳跃表是一种有序的数据结构，它通过每一个节点维持多个指向其它节点的指针，从而达到快速访问的目的。跳跃列表保存一个有序排列的链表，通过采用多层存储且保持每一层链表是其上一层链表的自己，从最稀疏的层开始搜索，从而达到比链表O(N)更优的查找和插入性能O(log(N))。 - [程序员小灰](https://zhuanlan.zhihu.com/p/53975333) - [知乎](https://juejin.cn/post/6844903446475177998) （1）查找路径： ![Redis-skiplist查找路径](https://cdn.learnku.com/uploads/images/202103/03/50944/V2NzVUBL7U.png!large) （2）插入操作： ![Redis-skiplist动画演示](https://cdn.learnku.com/uploads/images/202103/03/50944/Fe5n3yKtZ4.gif!large) 1. 新节点和各层索引节点逐一比较，确定原链表的插入位置。O（logN） 2. 把索引插入到原链表。O（1） 3. 利用抛硬币（coin flip）的随机方式，决定新节点是否提升为上一级索引。结果为“正”则提升并继续抛硬币，结果为“负”则停止。O（logN） 总体上，跳跃表插入操作的时间复杂度是O（logN），而这种数据结构所占空间是2N，即空间复杂度是 O（N）。 （3）删除操作 1. 自上而下，查找第一次出现节点的索引，并逐层找到每一层对应的节点。O（logN） 2. 删除每一层查找到的节点，如果该层只剩下1个节点，删除整个一层（原链表除外）。O（logN） 总体上，跳跃表删除操作的时间复杂度是O（logN）。