August's Box

Redis设计与实现笔记-章5.跳表

跳表(skiplist)是一种有序的数据结构,通过在每个节点中维护多个指向其他节点的指针来实现快速查找。实现简单,平均复杂度为O(logN),效率可媲美平衡树。Redis使用跳表来作为有序集合键的底层实现之一(有序集合包含元素比较多或元素是比较长的字符串时)和集群节点的内部数据结构。

跳表的实现

zskiplist

redis.h/zskiplistNode,zskiplistlink
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
typedef struct zskiplistNode {// 跳表节点
robj *obj;// 成员对象
double score;// 分值
struct zskiplistNode *backward;// 后退指针,指向前一个节点,从尾往头遍历可用
struct zskiplistLevel {// 层
struct zskiplistNode *forward;// 前进指针
unsigned int span;// 跨度,前进指针和当前指针的距离
} level[];
} zskiplistNode;
typedef struct zskiplist {// 跳表
struct zskiplistNode *header, *tail;// 头尾节点
unsigned long length;// 表中节点的数量(不包含头节点,头节点不含数据)
int level;// 表中层数最大的节点的层数(不包含头结点)
} zskiplist;

  1. 由图和定义可知,跳表level数组可以包含多个指向后续节点的指针,通过这些指针可以加速访问其他节点。
  2. 当每次创建一个新的跳表节点时,程序会根据幂次定律(power law,越大的数出现概率越小)随机生成一个介于1~32的值作为节点level数组的大小,即节点层的高度。
  3. 跨度span可以用来计算查找的节点的rank,在查找过程中,访问过的所有层span的和即查找节点的rank。另外,从头节点开始,依次访问level数组中span为1(L1/level[0])的前进指针直到结束,可以顺序遍历到所有节点。
  4. 后退指针可以从tail开始顺序遍历到header。
  5. 跳表中所有节点按照score从小到大排序(score相同的节点按照obj的字典序排序),obj是一个成员对象,指向一个字符串对象(SDS)。
  6. 跳表可以在O(1)时间内获取头尾节点、跳表长度。

跳表相关API

跳表相关的函数定义在redis.h中,函数实现在t_zset.c里面,主要的函数及说明如下:

函数 作用和代码逻辑 时间复杂度
zslCreate/zslCreateNode 创建新的跳表(包括head节点,层数为ZSKIPLIST_MAXLEVEL-32)/跳表节点 O(1)
zslFree/zslFreeNode 释放给定跳表,含所有跳表节点(释放过程中减少obj的引用计数,引用计数为0时会被自动释放decrRefCount O(N),N为跳表长度
zslInsert 插入节点到跳表:1. 查找节点插入位置,自上而下查找比较,并记录每层插入位置的pre节点及其rank,供后面更新使用 2. zslRandomLevel随机一个层高给当前节点,如果随机的newlevel大于当前最大level,更新头节点level~newlevel的level数组和跳表level属性 3. 创建新节点,并更新新节点level数组pre的指针和span、level~newlevel的span,新节点的backward 平均O(logN),最坏O(N),N为跳表长度
zslDelete 删除指定节点: 1. 查找指定节点位置,自上而下查找比较,并记录每层查找位置的pre节点,供后面更新使用 2. 更新每层查找的pre节点的forward和span、删除节点后一个节点的backward 3.更新跳表length属性并删除节点 平均O(logN),最坏O(N),N为跳表长度
zslGetRank 返回节点在跳表中的rank:逻辑同查找,查找过程中span加起来 同上
zslGetElementByRank 返回给定rank的节点:自上而下,和查找类似,仅判断逻辑不一样 同上
zslIsInRange 判断给定range是否在跳表范围内 O(1),直接比较(header.score, tail.score)
zslFirstInRange 找出符合给定range在跳表里的第一个节点:同查找类似,判断逻辑不同,先调用zslIsInRange 平均O(logN),最坏O(N),N为跳表长度
zslLastInRange 找出符合给定range在跳表里的最后一个节点:同查找类似,判断逻辑不同,先调用zslIsInRange 平均O(logN),最坏O(N),N为跳表长度
zslDeleteRangeByScore 删除score在给定range的所有节点:同删除,定位pre的判断逻辑不一样 O(N),N跳表长度
zslDeleteRangeByRank 删除rank在给定range的所有节点:同删除,定位pre的判断逻辑不一样 O(N),N跳表长度