redis6.0.5之zset阅读笔记1--跳跃列表(zshiplist)之初步介绍
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了redis6.0.5之zset阅读笔记1--跳跃列表(zshiplist)之初步介绍，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2761字，纯文字阅读大概需要4分钟。
内容图文
/* ZSETs are ordered sets using two data structures to hold the same elements
* in order to get O(log(N)) INSERT and REMOVE operations into a sorted
* data structure.
整数集合是有序集合， 使用了两种数据结构来保持相同数据在插入和删除操作上可以达到O(log(N))的存储结构。
* The elements are added to a hash table mapping Redis objects to scores.
* At the same time the elements are added to a skip list mapping scores
* to Redis objects (so objects are sorted by scores in this "view").
这个元素被添加到一个哈希表中，映射一个redis对象对应分数
同时，这个元素被添加到一个跳跃表中，映射一个redis对象对应分数
(这样对象能被按照视图里面的分数排序)。
* Note that the SDS string representing the element is the same in both
* the hash table and skiplist in order to save memory. What we do in order
* to manage the shared SDS string more easily is to free the SDS string
* only in zslFreeNode(). The dictionary has no value free method set.
* So we should always remove an element from the dictionary, and later from
* the skiplist.
注意到SDS字符串在hash表和跳跃表中保持同样的表示用来节省内存。
为了使管理共享的SDS字符串更加容易，只能在函数zslFreeNode释放SDS字符串(统一释放入口)
* This skiplist implementation is almost a C translation of the original
* algorithm described by William Pugh in "Skip Lists: A Probabilistic
* Alternative to Balanced Trees", modified in three ways:
* a) this implementation allows for repeated scores.
* b) the comparison is not just by key (our 'score') but by satellite data.
* c) there is a back pointer, so it's a doubly linked list with the back
* pointers being only at "level 1". This allows to traverse the list
* from tail to head, useful for ZREVRANGE. */
这个跳跃列表基本是William Pugh论文(需要对该论文进行仔细阅读，并且翻译，这个估计需要一周左右时间)
"Skip Lists: A Probabilistic Alternative to Balanced Trees"原始算法的C语言实现。
只在三处进行了修改：
a)这个实现允许重复的分数
b)不仅仅用键比较，还需要比较键对应的数据
c)多了一个回退指针，这样只有在level 1的层次是个双向指针(意味着其它层次是单向向前指针)
这个功能被用来从结尾想后补遍历，对函数ZREVRANGE特别有用
********************用到的数据结构*******************************************************
/* ZSETs use a specialized version of Skiplists */
zsets使用一个特护版本的跳跃列表
typedef struct zskiplistNode {
sds ele; 元素
double score; 分值
struct zskiplistNode *backward; 后向指针，用于层次1
struct zskiplistLevel { 每层
struct zskiplistNode *forward; 向前的指针
unsigned long span; 跳跃的间隔
} level[];
} zskiplistNode;
typedef struct zskiplist {
struct zskiplistNode *header, *tail; 头和尾指针
unsigned long length; 跳表长度
int level; 所在层次
} zskiplist;
typedef struct zset {
dict *dict; 字典集合
zskiplist *zsl; 跳表
} zset;
内容总结
以上是互联网集市为您收集整理的redis6.0.5之zset阅读笔记1--跳跃列表(zshiplist)之初步介绍全部内容，希望文章能够帮你解决redis6.0.5之zset阅读笔记1--跳跃列表(zshiplist)之初步介绍所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。