做网站大家都找谁,公司网站制作高端,可以随意建国际商城的网站吗,科技粉末1.基本指令
部分指令#xff0c;涉及到第4章的api#xff0c;没有具体看实现#xff0c;但是逻辑应该差不多。
zadd keyscore1value1score2value2... 将一个或多个member元素及其score值加入到有序集key当中。根据zslInsert zran…1.基本指令
部分指令涉及到第4章的api没有具体看实现但是逻辑应该差不多。
zadd keyscore1value1score2value2... 将一个或多个member元素及其score值加入到有序集key当中。根据zslInsert zrange keystartstop[WITHSCORES] 返回有序集key中下标在 之间的元素 根据zslGetElementByRank以及backward指针 zrangebyscore key min max [withscores] [limit offset count] 返回有序集 key 中所有score值介于min和max 之间(包括等于min或max )的成员根据zslFirstInRange和zslLastInRange以及backward指针 zrank keyvalue 返回该值在集合中的排名从0开始。根据zslGetRank
2.数据结构
ZSET是由有序集合跳表实现的按照分值的大小排序分值相同时按照成员对象的大小进行排序。同一个跳表可以有同分值的节点但是对象必须是唯一的。 定义结构的代码src/server.h
// 1.ZSET节点
/* ZSETs use a specialized version of Skiplists */
typedef struct zskiplistNode {// member元素的valuesds ele;// member元素的scoredouble score;// 后向指针struct zskiplistNode *backward;// 层struct zskiplistLevel {// 前进指针struct zskiplistNode *forward;// 跨度unsigned long span;} level[];
} zskiplistNode;// 2.ZSET链表
typedef struct zskiplist {// 头节点和尾节点struct zskiplistNode *header, *tail;// 节点的数量(不包括头节点)unsigned long length;// 表中层数最大节点的层数int level;
} zskiplist;结合上方的图容易理解其中有一些值得注意的点
header表头节点只有level没有存放元素的value和score。在zskiplist的length也不包括头节点。每一层都有两个属性前向forward指针和跨度。前向指针指向包含同一层的下一个结点跨度记录了两个节点间的距离。指向NULL的跨度都为0。跨度是用来计算排位rank的在查找某个节点的过程中将沿途访问过的所有层跨度累计起来就能得到目标节点的排位。后向backward指针指向当前节点的前一个节点。目的是遍历。和range有关的指令可以获得range范围的首尾节点后从尾节点遍历到首节点。只有backward指针是遍历相邻节点forward指针每一层都有指向的间隔为span的节点不是下一个节点每次创建一个跳表节点时根据幂次定律随机生成一个介于1到32之间的值作为level数组的大小。(见第3章节复杂度分析)节点的score是一个double类型的浮点数成员对象value是一个SDS(字符串对象)。如果想用zset实现两个维度排序可以用拼接的思想。
3.跳表通用复杂度分析
跳表的复杂度和level的层数有关如果只有一层那复杂度必然都是最坏情况O(N)。一个节点有多少层来自于下面这个函数在新建节点时根据幂次定律生成一个1到32间的随机数。 可以理解为有概率P多加一层。
int zslRandomLevel(void) {static const int threshold ZSKIPLIST_P*RAND_MAX;int level 1;while (random() threshold)level 1;return (levelZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
}我们知道完全二叉树的复杂度推导是 2 h − 1 N 2^h-1N 2h−1N h l o g 2 ( N 1 ) hlog_2(N1) hlog2(N1)所以平均查找的时间复杂度是O(log(N)) 跳表相当于一个多叉树叉为 1 P \frac{1}{P} P1。每一个节点有P的概率加一层那相邻两层的节点数比为P。由于跳表最多32层相邻两层实际节点数也不严格为P所以这是一个近似的概念。 复杂度推导为 ( 1 P ) h − 1 − 1 N (\frac{1}{P})^{h-1}-1N (P1)h−1−1N h l o g 1 p ( N 1 ) hlog_{\frac{1}{p}}(N1) hlogp1(N1) 如果p0.25 h 0.5 ∗ l o g 2 ( N 1 ) h0.5*log_2(N1) h0.5∗log2(N1) 如果p0.5 h l o g 2 ( N 1 ) hlog_2(N1) hlog2(N1) 所以p在一定范围都是O(log(N))级别的复杂度。P在极端情况下(比如接近0或1)会变成O(N)。 推导比较粗糙可能有问题 4.API复杂度分析
4.1. 查找元素
zslFirstInRange找到分值范围的第一个元素zslLastInRange找到分值范围的最后一个元素 平均O(logN)最坏O(N)
zskiplistNode *zslFirstInRange(zskiplist *zsl, zrangespec *range) {zskiplistNode *x;int i;/* 判断跳表分数的范围是否在该范围内 */if (!zslIsInRange(zsl,range)) return NULL;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;}/* This is an inner range, so the next node cannot be NULL. *//* 下一节点就是目标值 */ x x-level[0].forward;serverAssert(x ! NULL);/* Check if score max. */if (!zslValueLteMax(x-score,range)) return NULL;return x;
}
int zslValueGteMin(double value, zrangespec *spec) {return spec-minex ? (value spec-min) : (value spec-min);
}4.2. 判断分值是否在范围
zslIsInRange判断是否至少一个节点的分值在范围内 O(1)根据头尾节点实现。zslFirstInRange和zslLastInRange都会先调用这个函数进行判断。
/* 存在返回1不存在返回0 */
int zslIsInRange(zskiplist *zsl, zrangespec *range) {zskiplistNode *x;/* 对值的范围进行判定 */if (range-min range-max ||(range-min range-max (range-minex || range-maxex)))return 0;// 1.获取尾节点尾节点的分数不大于等于(就是小于)范围的最小值返回0x zsl-tail;if (x NULL || !zslValueGteMin(x-score,range))return 0;// 2.获取头节点头节点的分数大于范围的最大值返回0x zsl-header-level[0].forward;if (x NULL || !zslValueLteMax(x-score,range))return 0;return 1;
}4.3. 添加元素
zslInsert添加元素 平均O(logN)最坏O(N)
zskiplistNode *zslInsert(zskiplist *zsl, double score, sds ele) {/* 为了插入节点到正确位置存储遍历过程中每一层最尽头的节点其实就是新节点的上一个节点(该节点的forward指向新节点)*/zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x;/* 为了更新span存储遍历过程中每一层的rank */unsigned long rank[ZSKIPLIST_MAXLEVEL];int i, level;serverAssert(!isnan(score));/**和查找类似的思路**/x zsl-header;for (i zsl-level-1; i 0; i--) {/* 存储每一层的rank值 */rank[i] i (zsl-level-1) ? 0 : rank[i1];/* 在同一层通过前向指针遍历直到1.下一个节点为空2.下一节点分数大于等于范围最小值3.节点分数相同元素值更大进入下一层 */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))){/* 累加span获得rank */rank[i] x-level[i].span;x x-level[i].forward;}/* 记录每一层最末节点 */update[i] x;}/* 获取一个随机的level层数 */level zslRandomLevel();/* 如果新层数大于原跳表最大层数更新zsl-level并将超出的层记录下来 */if (level zsl-level) {for (i zsl-level; i level; i) {rank[i] 0; update[i] zsl-header;update[i]-level[i].span zsl-length; }zsl-level level; }x zslCreateNode(level,score,ele);/* 更新新节点和每层新节点前一个节点的forward和span */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 */x-level[i].span update[i]-level[i].span - (rank[0] - rank[i]);update[i]-level[i].span (rank[0] - rank[i]) 1;}/* increment span for untouched levels *//* 高于该节点的每一个span因为插入了一个节点所以要增加1 */for (i level; i zsl-level; i) {update[i]-level[i].span;}/* 更新backward指针 */x-backward (update[0] zsl-header) ? NULL : update[0];if (x-level[0].forward)x-level[0].forward-backward x;elsezsl-tail x;zsl-length;return x;
}4.4.获取成员排位
zslGetRank返回包含给定成员和score的节点的排位 平均O(logN)最坏O(N)
unsigned long zslGetRank(zskiplist *zsl, double score, sds ele) {zskiplistNode *x;unsigned long rank 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))) {/* 这一步记录了rank */rank x-level[i].span;x x-level[i].forward;}/* 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) {return rank;}}return 0;
}4.5. 获取某排位节点
zslGetElementByRank返回跳跃表在给定排位上的节点
zskiplistNode* zslGetElementByRank(zskiplist *zsl, unsigned long rank) {zskiplistNode *x;/* 记录了遍历过程中的rank累加值 */unsigned long traversed 0; int i;x zsl-header;for (i zsl-level-1; i 0; i--) {while (x-level[i].forward (traversed x-level[i].span) rank){traversed x-level[i].span;x x-level[i].forward;}if (traversed rank) {return x;}}return NULL;
}参考 《redis的设计与实现》redis源码-7.2.1
文章转载自： http://www.morning.stmkm.cn.gov.cn.stmkm.cn http://www.morning.ryspp.cn.gov.cn.ryspp.cn http://www.morning.qwbls.cn.gov.cn.qwbls.cn http://www.morning.rtlth.cn.gov.cn.rtlth.cn http://www.morning.rycd.cn.gov.cn.rycd.cn http://www.morning.qfdmh.cn.gov.cn.qfdmh.cn http://www.morning.krfpj.cn.gov.cn.krfpj.cn http://www.morning.nwfxp.cn.gov.cn.nwfxp.cn http://www.morning.tbjtp.cn.gov.cn.tbjtp.cn http://www.morning.yckwt.cn.gov.cn.yckwt.cn http://www.morning.wprxm.cn.gov.cn.wprxm.cn http://www.morning.wlqbr.cn.gov.cn.wlqbr.cn http://www.morning.mlpch.cn.gov.cn.mlpch.cn http://www.morning.jwgnn.cn.gov.cn.jwgnn.cn http://www.morning.mttqp.cn.gov.cn.mttqp.cn http://www.morning.xgmf.cn.gov.cn.xgmf.cn http://www.morning.lzbut.cn.gov.cn.lzbut.cn http://www.morning.yybcx.cn.gov.cn.yybcx.cn http://www.morning.snktp.cn.gov.cn.snktp.cn http://www.morning.ghxkm.cn.gov.cn.ghxkm.cn http://www.morning.wdpt.cn.gov.cn.wdpt.cn http://www.morning.sfgzx.cn.gov.cn.sfgzx.cn http://www.morning.jzxqj.cn.gov.cn.jzxqj.cn http://www.morning.fjlsfs.com.gov.cn.fjlsfs.com http://www.morning.nhgkm.cn.gov.cn.nhgkm.cn http://www.morning.rrxgx.cn.gov.cn.rrxgx.cn http://www.morning.wpspf.cn.gov.cn.wpspf.cn http://www.morning.xpmwt.cn.gov.cn.xpmwt.cn http://www.morning.qrgfw.cn.gov.cn.qrgfw.cn http://www.morning.qrqdr.cn.gov.cn.qrqdr.cn http://www.morning.nhbhc.cn.gov.cn.nhbhc.cn http://www.morning.qbwyd.cn.gov.cn.qbwyd.cn http://www.morning.yybcx.cn.gov.cn.yybcx.cn http://www.morning.frsbf.cn.gov.cn.frsbf.cn http://www.morning.jokesm.com.gov.cn.jokesm.com http://www.morning.mfct.cn.gov.cn.mfct.cn http://www.morning.qwnqt.cn.gov.cn.qwnqt.cn http://www.morning.ckfqt.cn.gov.cn.ckfqt.cn http://www.morning.lmfmd.cn.gov.cn.lmfmd.cn http://www.morning.lqytk.cn.gov.cn.lqytk.cn http://www.morning.hjrjr.cn.gov.cn.hjrjr.cn http://www.morning.xrwsg.cn.gov.cn.xrwsg.cn http://www.morning.jqbpn.cn.gov.cn.jqbpn.cn http://www.morning.mngh.cn.gov.cn.mngh.cn http://www.morning.yyzgl.cn.gov.cn.yyzgl.cn http://www.morning.ggfdq.cn.gov.cn.ggfdq.cn http://www.morning.ljhnn.cn.gov.cn.ljhnn.cn http://www.morning.thwhn.cn.gov.cn.thwhn.cn http://www.morning.hrgxk.cn.gov.cn.hrgxk.cn http://www.morning.tnyanzou.com.gov.cn.tnyanzou.com http://www.morning.cjqqj.cn.gov.cn.cjqqj.cn http://www.morning.zstry.cn.gov.cn.zstry.cn http://www.morning.fkwp.cn.gov.cn.fkwp.cn http://www.morning.lstmq.cn.gov.cn.lstmq.cn http://www.morning.qsy39.cn.gov.cn.qsy39.cn http://www.morning.zdmrf.cn.gov.cn.zdmrf.cn http://www.morning.lmxzw.cn.gov.cn.lmxzw.cn http://www.morning.lflsq.cn.gov.cn.lflsq.cn http://www.morning.dbfj.cn.gov.cn.dbfj.cn http://www.morning.lgnz.cn.gov.cn.lgnz.cn http://www.morning.kaoshou.net.gov.cn.kaoshou.net http://www.morning.hryhq.cn.gov.cn.hryhq.cn http://www.morning.bqts.cn.gov.cn.bqts.cn http://www.morning.mkpkz.cn.gov.cn.mkpkz.cn http://www.morning.pmdlk.cn.gov.cn.pmdlk.cn http://www.morning.dnmgr.cn.gov.cn.dnmgr.cn http://www.morning.yqyhr.cn.gov.cn.yqyhr.cn http://www.morning.kpcjl.cn.gov.cn.kpcjl.cn http://www.morning.hdwjb.cn.gov.cn.hdwjb.cn http://www.morning.rfhm.cn.gov.cn.rfhm.cn http://www.morning.cbchz.cn.gov.cn.cbchz.cn http://www.morning.hxpff.cn.gov.cn.hxpff.cn http://www.morning.kwksj.cn.gov.cn.kwksj.cn http://www.morning.kgtyj.cn.gov.cn.kgtyj.cn http://www.morning.jpkk.cn.gov.cn.jpkk.cn http://www.morning.lsnnq.cn.gov.cn.lsnnq.cn http://www.morning.nrjr.cn.gov.cn.nrjr.cn http://www.morning.nnpwg.cn.gov.cn.nnpwg.cn http://www.morning.zqwqy.cn.gov.cn.zqwqy.cn http://www.morning.prgyd.cn.gov.cn.prgyd.cn
