redis6.0.5之zset阅读笔记1--跳跃列表(zshiplist)之初步介绍

/* 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;

上一篇:Redis-Zset(有序集合)


下一篇:redis常用命令大全