手机版网站开发工具,电脑pc端网站建设是什么意思,建设企业网站就等于开展网络营销吗,河南网站建设运营域名注册公司跳表是一个多层的有序链表#xff0c;在跳表中进行查询操作时#xff0c;查询代码可以从最高层开始查询。层数越高#xff0c;结点数越少#xff0c;同时高层结点的跨度会比较大。因此#xff0c;在高层查询结点时#xff0c;查询一个结点可能就已经查到了链表的中间位置…跳表是一个多层的有序链表在跳表中进行查询操作时查询代码可以从最高层开始查询。层数越高结点数越少同时高层结点的跨度会比较大。因此在高层查询结点时查询一个结点可能就已经查到了链表的中间位置了。
这样一来跳表就会先查高层如果高层直接查到了等于待查元素的结点那么就可以直接返回。如果查到第一个大于待查元素的结点后就转向下一层查询。下层上的结点数多于上层所以这样可以在更多的结点中进一步查找待查元素是否存在。
跳表的这种设计方法就可以节省查询开销同时跳表设计采用随机的方法来确定每个结点的层数这样就可以避免新增结点时引起结点连锁更新问题。
有些拗口详细掰掰。
基础数据结构
zskiplist是一个多层的有序列表是一个双向链表。
zskiplistNode代表zskiplist里的每一个节点包含了对象权重权重越大越往后插入。
zskiplistLevel代表索引层级每一层就是一个zskiplistLevel插入时会采用随机分层方式决定当前元素插入到那一层去或者直接加入一层。跨度是决定在当前层还要根据当前指针来计算还要跨过多少元素才可以插入。
/* ZSETs use a specialized version of Skiplists */
/** 跳跃表节点*/
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;
查询元素过程level-score-sds
level层 从头节点开始直接从层级最高的地方开始由上往下查询。
score权重同一层比较的就是score大小score越大越往后。
sds数据发生score相等的场景这个时候就会比较数据的大小。
zskiplistNode *zslFirstInRange(zskiplist *zsl, zrangespec *range) {zskiplistNode *x;int i;/* If everything is out of range, return early. */if (!zslIsInRange(zsl,range)) return NULL;// 遍历跳跃表查找符合范围 min 项的节点// T_wrost O(N), T_avg O(log N)x zsl-header;for (i zsl-level-1; i 0; i--) {/* Go forward while *OUT* of range. */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-level[0].forward;redisAssert(x ! NULL);/* Check if score max. */// 检查节点是否符合范围的 max 项// T O(1)if (!zslValueLteMax(x-score,range)) return NULL;return x;
}/** 检测给定值 value 是否大于或大于等于范围 spec 中的 min 项。** 返回 1 表示 value 大于等于 min 项否则返回 0 。** T O(1)*/
static int zslValueGteMin(double value, zrangespec *spec) {return spec-minex ? (value spec-min) : (value spec-min);
}/** 检测给定值 value 是否小于或小于等于范围 spec 中的 max 项。** 返回 1 表示 value 小于等于 max 项否则返回 0 。** T O(1)*/
static int zslValueLteMax(double value, zrangespec *spec) {return spec-maxex ? (value spec-max) : (value spec-max);
}
插入元素过程
1、层数算法随机生成每个结点的层数
过程初始化层数为1生成一个随机数如果一个随机数的小于拟定的25%的概率层数1直到拟定的最大层数64为止。
这个算法并不是真正意义上的二分查找法它永远不会保证上层和下层1:2的比例同时这个算法可以避免插入删除更新导致连续更新问题一个元素改后面元素全部需要改仅仅只需要修改下指针即可。
/* Returns a random level for the new skiplist node we are going to create.** 返回一个随机值用作新跳跃表节点的层数。** The return value of this function is between 1 and ZSKIPLIST_MAXLEVEL* (both inclusive), with a powerlaw-alike distribution where higher* levels are less likely to be returned. ** 返回值介乎 1 和 ZSKIPLIST_MAXLEVEL 之间包含 ZSKIPLIST_MAXLEVEL* 根据随机算法所使用的幂次定律越大的值生成的几率越小。* ZSKIPLIST_P 指跳表结点增加层数的概率值为 0.25* T O(N)*/
int zslRandomLevel(void) {int level 1;while ((random()0xFFFF) (ZSKIPLIST_P * 0xFFFF))level 1;return (levelZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
} 插入过程和查询一样sds数据从小到大每一层从小到大层数也是由小到大。
/* Insert (element,score) pair in ziplist. ** 将 ele 成员和它的分值 score 添加到 ziplist 里面** ziplist 里的各个节点按 score 值从小到大排列** This function assumes the element is not yet present in the list. ** 这个函数假设 elem 不存在于有序集*/
unsigned char *zzlInsert(unsigned char *zl, robj *ele, double score) {// 指向 ziplist 第一个节点也即是有序集的 member 域unsigned char *eptr ziplistIndex(zl,0), *sptr;double s;// 解码值ele getDecodedObject(ele);// 遍历整个 ziplistwhile (eptr ! NULL) {// 取出分值sptr ziplistNext(zl,eptr);redisAssertWithInfo(NULL,ele,sptr ! NULL);s zzlGetScore(sptr);if (s score) {/* First element with score larger than score for element to be* inserted. This means we should take its spot in the list to* maintain ordering. */// 遇到第一个 score 值比输入 score 大的节点// 将新节点插入在这个节点的前面// 让节点在 ziplist 里根据 score 从小到大排列zl zzlInsertAt(zl,eptr,ele,score);break;} else if (s score) {/* Ensure lexicographical ordering for elements. */// 如果输入 score 和节点的 score 相同// 那么根据 member 的字符串位置来决定新节点的插入位置if (zzlCompareElements(eptr,ele-ptr,sdslen(ele-ptr)) 0) {zl zzlInsertAt(zl,eptr,ele,score);break;}}/* Move to next element. */// 输入 score 比节点的 score 值要大// 移动到下一个节点eptr ziplistNext(zl,sptr);}/* Push on tail of list when it was not yet inserted. */if (eptr NULL)zl zzlInsertAt(zl,NULL,ele,score);decrRefCount(ele);return zl;
}
