基于Redis7
Redis中的zset（有序集合）是使用跳表来实现的
结构体的定义
跳表节点的定义
//如果score相等，再按照ele排序
typedef struct zskiplistNode {
sds ele;//节点存储的具体的值
double score;//存储的分值，我们就是按照这个分值来进行排序的
struct zskiplistNode *backward;//后退指针，用于指向前一个节点，进行反向遍历（zrerange）
struct zskiplistLevel {
struct zskiplistNode *forward;//用于指向当前层后一个节点，如果他指向nullptr，说明后面没有节点
//span实际上是用来计算rank（排位的），当前值在zset中的排位，
//计算排名就是从到开始到当前节点的路径的一个累加
unsigned long span;//到(同一层级)到下一个节点的跨度,用来记录两个节点之间的距离，跨度很大说明离得很远
} level[];//这个是一个柔性数组，层数不固定
} zskiplistNode;
跳表的定义
//跳表的结构
typedef struct zskiplist {
struct zskiplistNode *header, *tail;//头指针，这个是实实在在的一个节点，但是没有存储有效的元素，尾节点，指nullptr
unsigned long length;//所建立跳表的长度
int level;//当前有多少层数
} zskiplist;
区间的定义
//用于表示有序集合的数值范围，包括最大值和最小值
typedef struct {
double min, max;//最小值和最大值
int minex, maxex; /* are min or max exclusive? *///minex和maxex表示最大值和最小值是否不包含在范围内（是否是开闭区间）
//minex表示最小值不包含在范围内，maxex表示最大值不包含在里面
} zrangespec;
跳表的实现
- 创建一个跳表的节点
/* Create a skiplist node with the specified number of levels.
* The SDS string 'ele' is referenced by the node after the call. */
//创建一个跳表中的节点，level设置为最大的层数，score就是对应的节点的分数，ele就是该节点存储的value
zskiplistNode *zslCreateNode(int level, double score, sds ele) {
zskiplistNode *zn =
zmalloc(sizeof(*zn)+level*sizeof(struct zskiplistLevel));//动态分配一个节点
zn->score = score;
zn->ele = ele;
return zn;
}
- 创建出一个跳表
//创建一个跳表
zskiplist *zslCreate(void) {
int j;
zskiplist *zsl;
zsl = zmalloc(sizeof(*zsl));
zsl->level = 1;//一开始就只建立一层
zsl->length = 0;//此时一个节点都没有
zsl->header = zslCreateNode(ZSKIPLIST_MAXLEVEL,0,NULL);//给头分配了一个头节点，这里设置默认最高的一个层数
for (j = 0; j < ZSKIPLIST_MAXLEVEL; j++) {
//32层都要给尾指针建立连接关系
zsl->header->level[j].forward = NULL;
zsl->header->level[j].span = 0;//后面没有节点，所以跨度为0
}
zsl->header->backward = NULL;//给头节点的前驱也要设置为null
zsl->tail = NULL;
return zsl;
}
- 释放跳表中的节点
/* Free the specified skiplist node. The referenced SDS string representation
* of the element is freed too, unless node->ele is set to NULL before calling
* this function. */
void zslFreeNode(zskiplistNode *node) {
sdsfree(node->ele);
zfree(node);
}
- 释放整个跳表
/* Free a whole skiplist. */
void zslFree(zskiplist *zsl) {
zskiplistNode *node = zsl->header->level[0].forward, *next;
zfree(zsl->header);
while(node) {
next = node->level[0].forward;
zslFreeNode(node);
node = next;
}
zfree(zsl);
}
- 随机获得一个层数
int zslRandomLevel(void) {
static const int threshold = ZSKIPLIST_P*RAND_MAX;//这个地方是2^64次方，才能到达32层
int level = 1;
while (random() < threshold)//一个随机数
level += 1;
return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
}
- 增加一个节点
/* Insert a new node in the skiplist. Assumes the element does not already
* exist (up to the caller to enforce that). The skiplist takes ownership
* of the passed SDS string 'ele'. */
zskiplistNode *zslInsert(zskiplist *zsl, double score, sds ele) {
zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x;//这个地方也需要记录所有的下层节点，他们的span需要加一,最大层数是32
unsigned long rank[ZSKIPLIST_MAXLEVEL];//查找时每一层跨越节点的排名
int i, level;
serverAssert(!isnan(score));
x = zsl->header;
for (i = zsl->level-1; i >= 0; i--) {
/* store rank that is crossed to reach the insert position ,获得需要插入的位置*/
rank[i] = i == (zsl->level-1) ? 0 : rank[i+1];//如果不是最顶层，该层的起始值就是上一层的树
while (x->level[i].forward &&
(x->level[i].forward->score < score ||
(x->level[i].forward->score == score &&
sdscmp(x->level[i].forward->ele,ele) < 0)))
//往后走
{
rank[i] += x->level[i].span;//当前的rank需要加少这个x的rank
x = x->level[i].forward;//x需要往后走
}
update[i] = x;//记录下层前的节点
}
/* we assume the element is not already inside, since we allow duplicated
* scores, reinserting the same element should never happen since the
* caller of zslInsert() should test in the hash table if the element is
* already inside or not. */
//
level = zslRandomLevel();//随机生成新节点所需要建立索引的树的高度
if (level > zsl->level) {
//如果获得的level比已经建立好的索引还要大
for (i = zsl->level; i < level; i++) {
//从当前的level到获得的随机的level都需要建立一个索引
rank[i] = 0;//后面需要添加元素
update[i] = zsl->header;//update需要成为头节点
update[i]->level[i].span = zsl->length;//跨度就是整个链表的长度
}
zsl->level = level;//更新最大的层数
}
x = zslCreateNode(level,score,ele);//创建一个新的节点
//增加节点的时候，重新建立连接关系
for (i = 0; i < level; i++) {
//链表的插入算法
x->level[i].forward = update[i]->level[i].forward;
update[i]->level[i].forward = x;
/* update span covered by update[i] as x is inserted here */
//更新span值
x->level[i].span = update[i]->level[i].span - (rank[0] - rank[i]);//更新节点的span值
update[i]->level[i].span = (rank[0] - rank[i]) + 1;
}
/* increment span for untouched levels */
for (i = level; i < zsl->level; i++) {
update[i]->level[i].span++;//从level到最高层的span都需要增加
}
x->backward = (update[0] == zsl->header) ? NULL : update[0];//
if (x->level[0].forward)
x->level[0].forward->backward = x;
else
zsl->tail = x;
zsl->length++;
return x;
}
- 删除跳表中的节点
//删除一个节点，x就是要删除的节点
void zslDeleteNode(zskiplist *zsl, zskiplistNode *x, zskiplistNode **update) {
int i;
for (i = 0; i < zsl->level; i++) {
if (update[i]->level[i].forward == x) {
//这个就是最接近要删除的x那一层
update[i]->level[i].span += x->level[i].span - 1;//加上x的span，同时因为要去掉x这个元素，所以要减1
update[i]->level[i].forward = x->level[i].forward;//直接把x进行删除
} else {
update[i]->level[i].span -= 1;//不是在同一层，他的update直接-1即可
}
}
//这个上面我们只是把next节点修改，向前指针没修改
//处理边界条件
//如果被删除节点不是尾节点的时候
if (x->level[0].forward) {
x->level[0].forward->backward = x->backward;//把后一个节点的前驱指向x的前一个节点
} else {
zsl->tail = x->backward;//否则，就是一个尾节点，更新尾指针
}
//如果顶层空了
while(zsl->level > 1 && zsl->header->level[zsl->level-1].forward == NULL)
zsl->level--;//我们需要将层数进行减少
zsl->length--;//长度也需要减少
}
//node就是返回删除的节点，先查找到相应的节点将其进行保存，后执行删除节点的操作
int zslDelete(zskiplist *zsl, double score, sds ele, zskiplistNode **node) {
zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x;//使用update记录进行搜索对应元素的时候每次进行下层的节点，一位进行下层，那么他们的rank值就会发生改变 ，每一层的节点的span都需要-1
int i;
x = zsl->header;
for (i = zsl->level-1; i >= 0; i--) {
while (x->level[i].forward &&
(x->level[i].forward->score < score ||
(x->level[i].forward->score == score &&
sdscmp(x->level[i].forward->ele,ele) < 0)))
{
x = x->level[i].forward;
}
update[i] = x;//记录该层p的前一个节点，用来进行修改连接关系，以及修改span值
}
/* We may have multiple elements with the same score, what we need
* is to find the element with both the right score and object. */
x = x->level[0].forward;//这个地方的x就可能是要删除的节点
//进行删除该节点
if (x && score == x->score && sdscmp(x->ele,ele) == 0) {
//说明符合我们锁需要删除的元素
zslDeleteNode(zsl, x, update);//执行删除节点从链表中
if (!node)
zslFreeNode(x);
else
*node = x;
return 1;
}
return 0; /* not found */
}
- 获得相应的排名
//查找就是分为向前（同层），向下（下层）
//查找zset某个元素在里面的排名
unsigned long zslGetRank(zskiplist *zsl, double score, sds ele) {
zskiplistNode *x;
unsigned long rank = 0;//初始化排名为0
int i;
x = zsl->header;//先获得头节点
for (i = zsl->level-1; i >= 0; i--) {
//从最顶层开始往底层走
while (x->level[i].forward &&
(x->level[i].forward->score < score ||
(x->level[i].forward->score == score &&
sdscmp(x->level[i].forward->ele,ele) <= 0)))//当前节点的下一个有节点分数小于我们需要的分数，或者元素相等的时候，ele相等，也要往下走
{
rank += x->level[i].span;//加上当前节点的rank值，排名就是span的总和
x = x->level[i].forward;//x就需要往前走
}
/* x might be equal to zsl->header, so test if obj is non-NULL */
if (x->ele && x->score == score && sdscmp(x->ele,ele) == 0) {
//如果元素存在，分数是我们需要的分数，同时value也是我们需要的分数
return rank;//那我们就返回对应的排名
}
//没找到，或者已经往前走了，就需要进行下沉
}
return 0;
}
- 判断是否存在与给定范围匹配的节点
int zslValueGteMin(double value, zrangespec *spec) {
//把节点的最大值和范围的最小值进行比较，因为最小值可能存在可能不存在，所以需要进行判断是否包含最小值
return spec->minex ? (value > spec->min) : (value >= spec->min);
}
int zslValueLteMax(double value, zrangespec *spec) {
return spec->maxex ? (value < spec->max) : (value <= spec->max);
}
/* Returns if there is a part of the zset is in range. */
//返回是否存在与给定范围匹配的节点
int zslIsInRange(zskiplist *zsl, zrangespec *range) {
zskiplistNode *x;
/* Test for ranges that will always be empty. */
//给定的区间是否不存在
if (range->min > range->max ||
(range->min == range->max && (range->minex || range->maxex)))
return 0;
x = zsl->tail;//获得尾节点，尾巴节点是最大的分数
if (x == NULL || !zslValueGteMin(x->score,range))
return 0;
x = zsl->header->level[0].forward;
if (x == NULL || !zslValueLteMax(x->score,range))
return 0;
//范围合理，返回成功
return 1;
}
- 在给定范围的第一个节点
zskiplistNode *zslFirstInRange(zskiplist *zsl, zrangespec *range) {
zskiplistNode *x;
int i;
/* If everything is out of range, return early. */
//对跳表进行范围检查，发现没有存在，所以直接返回
if (!zslIsInRange(zsl,range)) return NULL;
x = zsl->header;
for (i = zsl->level-1; i >= 0; i--) {
/* Go forward while *OUT* of range. */
//查找符合min项的节点
while (x->level[i].forward &&
!zslValueGteMin(x->level[i].forward->score,range))
x = x->level[i].forward;
}
/* This is an inner range, so the next node cannot be NULL. */
//这个x就是在范围内的第一个节点
x = x->level[0].forward;
serverAssert(x != NULL);//保证不为空
/* Check if score <= max. */
//同时要判断是不是应该也要小于最大值
if (!zslValueLteMax(x->score,range)) return NULL;
//都满足，就返回该节点
return x;
}
- 根据范围进行删除跳表的元素
* sorted set, in order to remove the elements from the hash table too. */
//范围删除
unsigned long zslDeleteRangeByScore(zskiplist *zsl, zrangespec *range, dict *dict) {
zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x;
unsigned long removed = 0;
int i;
x = zsl->header;
for (i = zsl->level-1; i >= 0; i--) {
while (x->level[i].forward &&
!zslValueGteMin(x->level[i].forward->score, range))
x = x->level[i].forward;
update[i] = x;
}
/* Current node is the last with score < or <= min. */
//定位到给定范围的第一个节点
x = x->level[0].forward;
/* Delete nodes while in range. */
while (x && zslValueLteMax(x->score, range)) {
zskiplistNode *next = x->level[0].forward;//记录下一个节点
zslDeleteNode(zsl,x,update);//删除给定的节点
dictDelete(dict,x->ele);//释放值的空间
zslFreeNode(x); /* Here is where x->ele is actually released. *///释放节点
removed++;
x = next;
}
return removed;
}