Redis之跳跃表
2021-08-21 本文已影响0人
slxixiha
跳跃表(skiplist)是一种有序数据结构,它通过在每个节点中维持毒功而指向其他节点的指针,从而达到快速访问节点的目的。
跳跃表支持平均O(logN),最坏O(N)复杂度的节点查找,还可以通过顺序性操作来批量处理节点。
跳跃表的使用场景
Redis使用跳跃表作为有序集合键的底层实现之一,如果一个有序集合包含的元素数量比较多,或者有序集合中元素的成员时比较长的字符串时,Reids就会使用跳跃表来作为有序集合键的底层实现。
跳跃表的定义
// server.h
/* ZSETs use a specialized version of Skiplists */
typedef struct zskiplistNode {
// 必须唯一,分值相同时按照ele的字典序排列
sds ele;
// 分值,所有节点按分值从小到大排序
double score;
struct zskiplistNode *backward;
struct zskiplistLevel {
struct zskiplistNode *forward;
// 跨度,用于计算该节点在跳跃表中的序号
unsigned long span;
} level[];
} zskiplistNode;
typedef struct zskiplist {
struct zskiplistNode *header, *tail;
// 跳跃表的长度(不包含表头节点)
unsigned long length;
// 层数最大的节点的层数(不包含表头节点)
int level;
} zskiplist;
zskiplistNode.score:节点的分值,节点在跳跃表中按照分值从小到大排列。
zskiplistNode.ele:节点保存的数据对象,节点的分值相同时,根据ele的字典序排序。
zskiplistNode.level:节点的层数组,程序通过这些层来加快访问其他节点的速度。每次创建新节点时回根据幂次定律(power law,越大的数出现的概率越小)随机生成一个介于1和32之间的值作为level数组的大小,这个大小就是层的高度。