新购 续费 升级
超多折扣优惠
阿里云服务器限时两折起
年付每月仅需24元,低至0.73元/天起
阿里云服务器ECS    
弹性可伸缩的计算服务,助您降低 IT 成本,提升运维效率,使您更专注于核心业务创新 [咨询更多]
阿里云存储OSS
简单易用、多重冗余、数据备份高可靠、多层次安全防护安全性更强、低成本 [咨询更多]
阿里云数据库RDS
稳定可靠、可弹性伸缩、更拥有容灾、备份、恢复、监控、迁移等方面的全套解决方案 [咨询更多]
阿里云安全产品
DDoS高防IP、web应用防火墙、安骑士、sll证书、态势感知众多阿里云安全产品热销中 [咨询更多]
阿里云折扣优惠    
云服务器ECS、数据库、负载均衡等产品新购、续费、升级联系客服获取更多专属折扣 [咨询更多]
Redis中的跳跃表是如何实现
2020-9-7
  跳跃表由多个节点构成,每个节点由很多层构成,每层都有指向本层下个节点的指针。跳跃表节点与结构,那么,Redis中的跳跃表是如何实现的呢? 

  跳跃表节点下面我们来看跳跃表节点的zskiplistNode结构体。

       typedef struct zskiplistNode {

  sds ele;    double score;
  
  struct zskiplistNode *backward;
  
  struct zskiplistLevel {
  
  struct zskiplistNode *forward;
  
  unsigned int span;
  
  } level[];} zskiplistNode;

  
  该结构体包含如下属性。
  
  1)ele:用于存储字符串类型的数据。
  
  2)score:用于存储排序的分值。
  
  3)backward:后退指针,只能指向当前节点最底层的前一个节点,头节点和第一个节点——backward指向NULL,从后向前遍历跳跃表时使用。
  
  4)level:为柔性数组。每个节点的数组长度不一样,在生成跳跃表节点时,随机生成一个1~64的值,值越大出现的概率越低。
  
  level数组的每项包含以下两个元素。
  
  ·forward:指向本层下一个节点,尾节点的forward指向NULL。·span:forward指向的节点与本节点之间的元素个数。span值越大,跳过的节点个数越多。
  
  跳跃表是Redis有序集合的底层实现方式之一,所以每个节点的ele存储有序集合的成员member值,score存储成员score值。所有节点的分值是按从小到大的方式排序的,当有序集合的成员分值相同时,节点会按member的字典序进行排序。
  
  跳跃表结构
  
  除了跳跃表节点外,还需要一个跳跃表结构来管理节点,Re-dis使用zskiplist结构体,定义如下:
  
  typedef struct zskiplist {
  
  struct zskiplistNode *header, *tail;
  
  unsigned long length;
  
  int level;} zskiplist;

  
  该结构体包含如下属性。
  
  1)header:指向跳跃表头节点。头节点是跳跃表的一个特殊节点,它的level数组元素个数为64。头节点在有序集合中不存储任何member和score值,ele值为NULL,score值为0;也不计入跳跃表的总长度。头节点在初始化时,64个元素的for-ward都指向NULL,span值都为0。
  
  2)tail:指向跳跃表尾节点。
  
  3)length:跳跃表长度,表示除头节点之外的节点总数。
  
  4)level:跳跃表的高度。通过跳跃表结构体的属性我们可以看到,程序可以在O(1)的时间复杂度下,快速获取到跳跃表的头节点、尾节点、长度和高度。
联系客服免费领取更多阿里云产品新购、续费升级折扣,叠加官网活动折上折更优惠