02 Redis数据结构

蔚落 2023-07-25 09:58 31阅读 0赞

#### Redis所有的数据结构都是以唯一的key字符串作为名称，然后通过这个唯一的key来获取响应的value数据。value有5种基础数据结构，分别是string（字符串）、list（列表）、set（集合）、hash（字典）、zset（有序集合）。 ####

[字符串][Link 1]  
[列表 哈希][Link 1]  
[集合 有序集合][Link 2]

<table> 
 <thead> 
  <tr> 
   <th>Redis基础数据类型</th> 
   <th>底层数据结构</th> 
   <th>应用背景</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>字符串（String）</td> 
   <td>数组</td> 
   <td>计数器，粉丝数量 统计在线人数，存储图片或视频</td> 
  </tr> 
  <tr> 
   <td>列表（List）</td> 
   <td>双向链表</td> 
   <td>实现消息队列 存储关注列表、粉丝列表</td> 
  </tr> 
  <tr> 
   <td>哈希（字典）</td> 
   <td>数组 + 链表二维结构</td> 
   <td>存储对象的基本属性信息，比如用户信息，商品信息</td> 
  </tr> 
  <tr> 
   <td>集合（set）</td> 
   <td>hash</td> 
   <td>去重，例如用户名不能重复；交集并集功能，查找元素的共同点 计算出两个人的共同关注</td> 
  </tr> 
  <tr> 
   <td>有序集合（zset）</td> 
   <td>Hash+跳跃表</td> 
   <td>范围查找，排行榜功能或者topN功能</td> 
  </tr> 
 </tbody> 
</table>

*  String（字符串）SDS结构
 *  List（列表） 链表
 *  Hash（字典） 哈希表
 *  Set（集合）
 *  Sorted Set（有序集合）跳跃表

#### string（字符串） ####

1.  Redis字符串是动态字符串，是可以修改的字符串，结构上类似于Java中的ArrayList，采用预分配冗余空间的方式来减少内存的频繁分配。Redis 的字符串是一种简单动态字符串（SDS），因为普通的 String 字符串不记录长度信息，如果想知道它的长度，需要遍历整个字符串来得到，时间复杂度为 O(n)，而 redis 的简单动态字符串中的 len 属性记录了长度信息，取得长度的时间复杂度仅为 O(1)，这样确保了获取字符串长度的操作不会成为 redis 的性能瓶颈。
2.  操作语句
    
     *  set 进行写：set name test（mset name1 test1 name2 test2 name3 test3）
     *  get 进行读：get name（mget name1 name2 name3）
     *  expire 设置过期时间：expire name 5（表示5秒后过期）
     *  setex 同时写和设置过期时间：setex name 5 test
     *  setnx 表示 name不存在时才进行set：setnx name test
3.  如果value的值是一个整数，name可以对它进行自增操作，如果整数超过Long的最大最小值，会报错
    
     *  incr 表示自增1：incr age
     *  incrby 表示自增指定值：incrby age 5

#### list（列表） ####

1.  用来储存多个有序的字符串，列表中的每个字符串成为元素，在 Redis 中，可以队列表两端插入和弹出，还可以获取指定范围的元素列表、获取指定索引下的元素等，列表是一种比较灵活的数据结构，它可以充当栈和队列的角色。
2.  使用场景：可以用来做异步队列：将需要延后处理的任务序列化成字符串，存到Redis的list列表中，另一个线程从这个列表中轮询数据进行处理。Redis 的 lpush + brpop 命令组合即可实现阻塞队列，生产者客户端是用 lpush 从列表左侧插入元素，多个消费者客户端使用 brpop 命令阻塞式的“抢”列表尾部的元素，多个客户端保证了消费的负载均衡和高可用性。
    
     *  rpush 表示右边进，lpop 表示左边出，构成的是一个队列。
     *  rpush 表示右边进，rpop表示右边出，构成的是一个栈。
3.  list底层结构：
    
     *  Redis 底层存储的并不是一个简单的LinkedList，而是快速链表quickList。
     *  在列表元素较少时，使用一块连续的内存来储存，这个结构叫做zipList，也就是压缩链表，它将所有的元素紧挨着一起存储。
     *  当数据量较多时，改为quickList，这么做的原因是：普通的链表需要附加指针会占用空间，而且加重了内存的碎片化。所以Redis将链表和zipList结合组成了quickList，它将多个zipList通过双向指针串起来，这样既能满足快速插入删除性能，又不会出现严重的空间碎片化。

#### set（集合） ####

1.  Redis 的集合相当于Java 中的HashSet，它的内部实现相当于一个特殊的字典，字典中所有的value都是NULL。
2.  set集合中的元素无序且不能重复，可以用来存储活动中奖的用户id，可以保证同一个用户不会中奖两次。
3.  Redis 除了支持集合内的增删改查，同时还支持多个集合取交集、并集、差集。合理的使用好集合类型，能在实际开发中解决很多实际问题。
4.  使用场景：如：一个用户对娱乐、体育比较感兴趣，另一个可能对新闻感兴趣，这些兴趣就是标签，有了这些数据就可以得到同一标签的人，以及用户的共同爱好的标签，这些数据对于用户体验以及曾强用户粘度比较重要。
5.  操作：
    
     *  sadd book java（添加元素）
     *  spop book（弹出一个元素）
     *  scard book（获取长度，类似count）
     *  smembers book（查看所有元素）

#### hash（字典） ####

1.  Redis的字典相当于Java中的HashMap。
2.  **Redis的字典和HashMap的异同点**：
    
     *  相同点：无序，采用数组+链表结构。数组位置碰撞时，就会将碰撞的元素使用链表串接起来。
     *  不同点：
        
         *  Redis 字典的值只能是字符串，而HashMap的值可以是多种类型。
         *  rehash的方式不一样，因为HashMap采用了一次性全部rehash。Redis为了高性能，不能阻塞服务，采用了渐进式rehash策略。渐进式 rehash 就是同时保留旧数组和新数组，在后续对 hash 的操作中渐渐的将旧数组中的数据迁移到新数组中，所以在操作处于 rehash 过程的字典时，需要同时访问新旧两个哈希表，如果在旧哈希表中找不到元素，就需要去新哈希表中查找。
3.  Redis中的每个字典都带有两个哈希表：ht\[0\]和ht\[1\]，一个作为平时使用，一个在rehash时使用。
4.  Redis的哈希表示如何解决哈希冲突的：采用链地址法来解决键冲突问题，每个节点都有一个next指针指向另一个节点，通过指针将索引值相同的节点连接起来。
5.  rehash 当哈希表保存的键值对数量太多或者太少时，需要对哈希表的大小进行相应的扩展或者收缩。**渐进式rehash**步骤：
    
     *  为ht\[1\]分配空间，让字典同时持有ht\[0\]和ht\[1\]两个表。
     *  在字典中维持一个索引计数器rehashidx，值设为0，表示rehash工作正式开始。
     *  在rehash进行期间，每次对字典执行添加、删除、查找或者更新操作时，程序就会顺带将ht\[0\]哈希表在rehashidx索引上所有的键值对rehash到ht\[1\]，并将rehashidx的值加1。
     *  随着字典操作的不断执行，最终ht\[0\]的所有键值对都会被rehash到ht\[1\]，这时程序将rehashidx的值设为-1，表示rehash操作已完成。然后将ht\[0\]的空间释放掉，将ht\[1\]设置为ht\[0\]。

#### zset（有序集合） ####

1.  一方面它是一个set，保证了元素的唯一性。
2.  另一方面它给每个元素赋予一个score，代表这个value的排序权重。可以根据score对元素进行排序。
3.  **使用场景**：排行榜是有序集合经典的使用场景；存学术成绩（学生id，成绩）
4.  操作：
    
     *  zadd test 99 math
     *  zrange test 60 100（区间查找60到100分的元素）
     *  zrank test math 看排名
     *  zcard test 相当于count
5.  zset底层数据结构
    
     *  zset底层数据结构包括ziplist和skiplist，当有序集合保存的元素数量小于128个并且所有元素的长度都小于64字节时，使用ziplist，否则使用zskiplist和dict。
     *  ziplist 作为zset底层数据结构时，每个集合元素使用两个紧挨在一起的压缩列表节点来保存，第一个节点保存元素的成员，第二个节点保存元素的分值。
     *  zskiplist和dict作为zset底层存储结构时，dict保存key/value，便于通过key获取score；zskiplist保存有序的元素列表，便于按照分值对元素排序，便于执行range之类的命令。

跳跃表

1.  跳跃表是一种链表加多层索引的结构，支持快速插入、删除、查找操作，平均查找复杂度是O(logN)，空间复杂度是O(n)。

2.跳表的查找过程：从最顶层开始查找，查找到最后一个小于被查找元素的位置，就跳到下一层继续查找，直到最底层。由于根据索引可以一次跳过多个元素，所以跳查找的查找速度也就变快了。

1.  跳跃表由zskiplist和zskiplistNode两个结构构成。zskiplist结构用于保存跳跃节点相关的信息，比如节点的数量、表头表尾节点的指针等；zskiplistNode结构用于表示跳跃表节点。跳跃表节点中有一个level数组，代表层，数组中每个元素都包含一个指向其他节点的指针，可以通过这些层来加快访问其他节点的速度。节点中还保存了元素的引用和分值，跳跃表中所有的节点都按照分值从小到大排序。
2.  为什么要使用跳表而不是红黑树来实现zset：
    
     *  zset支持的操作有插入、删除、查找、有序输出所有元素、查找区间内所有元素。前面4项，两者效率差不多，但是最后一项，红黑树没有跳表效率高。
     *  在跳表中，要查找区间的元素，只需定位到两个区间端点在最底层的位置，然后顺序遍历元素即可，非常高效。而红黑树定位到端点后，每次都要查找后续节点，比较耗时。
3.  为什么有序集合zset需要同时使用跳跃表和字典来实现
    
     *  如果只用字典实现有序集合，它可以以O(1)的复杂度查找元素的分值，但是对于zrank、zrange命令，都需要对所有元素排序，完成这种排序至少需要O(NlogN)的时间复杂度，以及O(N)的空间内存（因为要创建一个数组来保存排序后的元素）。
     *  如果只用跳跃表来实现有序集合的话，有高效执行范围操作的优点，但是根据成员查找分值这一操作的复杂度将从O(1)上升为O(N)。因此，为了让有序集合的查找分值和范围查找操作都尽可能快，redis选择同时使用字典和跳跃表来实现有序集合。两种数据结构通过指针共享元素，不会浪费内存
4.  Redis只在两个地方用到了跳跃表，一个是实现有序集合键，另一个是集群节点中用作内部数据结构。跳表是可以实现二分查找的有序链表（链表加上多级索引的结构，就是跳表）
5.  **跳跃表的时间复杂度为O(logn)**：标准化的跳表每两个元素提取出一个元素作为上一级的索引，也就是开始是1/2，然后1/4，1/8 … ，每一级索引减少上一级一半的元素，那么最后一级只有一个元素，也就是总元素个数 n/(2h) = 1 ，得到高度 h = logn，所以跳表的时间复杂度为 O(logn)。
    
    **跳跃表的空间复杂度为O(n)**：如果每两个元素向上提取一个元素的索引，那么最后额外需要的空间是一个等比数列，为：n/2 + n/4 + n/8 … + 8 + 4 + 2 = n - 2 ，所以，跳表的空间复杂度为 O(n)。每三个节点抽取一个索引的话，额外需要的空间是n-1/2。

[Link 1]: https://blog.csdn.net/dl674756321/article/details/102480007
[Link 2]: https://blog.csdn.net/dl674756321/article/details/102501627