阿里云代理商-阿里云服务器-阿里云数据库-重庆典名科技

Redis中的跳跃表是如何实现

发布时间: 2020-09-07 10:51:49文章作者: 网站编辑阅读量: 450
  跳跃表由多个节点构成,每个节点由很多层构成,每层都有指向本层下个节点的指针。跳跃表节点与结构,那么,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)的时间复杂度下,快速获取到跳跃表的头节点、尾节点、长度和高度。
联系客服免费领取更多阿里云产品新购、续费升级折扣,叠加官网活动折上折更优惠