Redis Zset有序集合实现原理

╰半夏微凉° 2023-07-17 06:52 20阅读 0赞

## 概要：Redis 有序集合和集合一样也是string类型元素的集合，且不允许重复的成员。不同的是每个元素都会关联一个double类型的分数。redis正是通过分数来为集合中的成员进行从小到大的排序。有序集合的成员是唯一的，但分数(score)却可以重复。 ##

**一、Redis编码简介**  
Redis对象的底层实现数据结构由对象的encoding属性决定，该属性记录了对象的编码，即对象使用的底层实现的数据结构。这些编码可以是：

<table> 
 <thead> 
  <tr> 
   <th>编码格式</th> 
   <th>底层数据结构</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>REDIS_ENCODING_INT</td> 
   <td>long类型的整数</td> 
  </tr> 
  <tr> 
   <td>REDIS_ENCODING_ EMBSTR</td> 
   <td>embstr编码的简单动态字符串</td> 
  </tr> 
  <tr> 
   <td>REDIS_ENCODING_RAW</td> 
   <td>简单动态字符串</td> 
  </tr> 
  <tr> 
   <td>REDIS_ENCODING_HT</td> 
   <td>字典</td> 
  </tr> 
  <tr> 
   <td>REDIS_ENCODING_LINKEDLIST</td> 
   <td>双端链表</td> 
  </tr> 
  <tr> 
   <td>REDIS_ENCODING_ZIPLIST</td> 
   <td>压缩列表</td> 
  </tr> 
  <tr> 
   <td>REDIS_ENCODING_INTSET</td> 
   <td>整数集合</td> 
  </tr> 
  <tr> 
   <td>REDIS_ENCODING_SKIPLIST</td> 
   <td>跳跃表和字典</td> 
  </tr> 
 </tbody> 
</table>

**二、有序集合的编码可以是ziplist或者skiplist**

*  ziplist编码  
    ziplist编码的有序集合对象使用压缩列表作为底层实现，每个集合元素使用两个紧挨在一起的压缩列表节点来保存，第一个节点保存元素的成员，第二个元素保存元素的分值。  
    压缩列表内的集合元素按分值从小到大排序。
    
    <table> 
     <tbody> 
      <tr> 
       <td>zlbytes</td> 
       <td>zltail</td> 
       <td>zllen</td> 
       <td>"apple"</td> 
       <td>5.0</td> 
       <td>"pen"</td> 
       <td>6.0</td> 
       <td>zlend</td> 
      </tr> 
     </tbody> 
    </table>
    
    <table> 
     <thead> 
      <tr> 
       <th>属性</th> 
       <th>说明</th> 
      </tr> 
     </thead> 
     <tbody> 
      <tr> 
       <td>zlbytes</td> 
       <td>记录整个压缩列表占用的内存字节数；在对压缩列表进行内存重分配， 计算 zlend 的位置时使用。</td> 
      </tr> 
      <tr> 
       <td>zltail</td> 
       <td>记录压缩列表表尾节点距离压缩列表的起始地址有多少个字节：通过这个偏移量，程序无需遍历整个压缩列表就可以确定表尾节点的地址</td> 
      </tr> 
      <tr> 
       <td>zllen</td> 
       <td>记录了压缩列表包含的节点数量</td> 
      </tr> 
      <tr> 
       <td>zlend</td> 
       <td>特殊值oxFF(十进制255)，用于标记压缩列表的末尾</td> 
      </tr> 
     </tbody> 
    </table>
 *  skiplist编码  
    skiplist编码使用跳跃表和字典实现底层数据结构  
    字典（dict）为有序集合构造了一个成员和分值之间的映射，字典中的每个键保存了元素成员，字典的值保存了元素的分值。通过字典，可以以O(1)的时间复杂度查找成员对应的分值。  
    因为字典的键是唯一的，字典与跳跃表之间共享元素的指针，所以不会存在重复元素。排序是在跳跃表中实现的。
    
    跳跃表的相关内容参考：[跳跃表][Link 1]

> 参考：W3Cschool 和 Redis设计与实现（黄健宏）

[Link 1]: https://cloud.tencent.com/developer/article/1422115