跳跃表由多个节点构成,每个节点由很多层构成,每层都有指向本层下个节点的指针。跳跃表节点与结构,那么,Redis中的跳跃表是如何实现的呢?
跳跃表节点下面我们来看跳跃表节点的zskiplistNode结构体。
typedef struct zskiplistNode {
sds ele; double score;
struct zskiplistNode *backward;
struct zskiplistLevel {
struct zskiplistNode *forward;
unsigned int span;
} level[];} zskiplistNode;
该结构体包含如下属性。
1)ele:用于存储字符串类型的数据。
2)score:用于存储排序的分值。
3)backward:后退指针,只能指向当前节点最底层的前一个节点,头节点和第一个节点——backward指向NULL,从后向前遍历跳跃表时使用。
4)level:为柔性数组。每个节点的数组长度不一样,在生成跳跃表节点时,随机生成一个1~64的值,值越大出现的概率越低。
level数组的每项包含以下两个元素。
·forward:指向本层下一个节点,尾节点的forward指向NULL。·span:forward指向的节点与本节点之间的元素个数。span值越大,跳过的节点个数越多。
跳跃表是Redis有序集合的底层实现方式之一,所以每个节点的ele存储有序集合的成员member值,score存储成员score值。所有节点的分值是按从小到大的方式排序的,当有序集合的成员分值相同时,节点会按member的字典序进行排序。
跳跃表结构
除了跳跃表节点外,还需要一个跳跃表结构来管理节点,Re-dis使用zskiplist结构体,定义如下:
typedef struct zskiplist {
struct zskiplistNode *header, *tail;
unsigned long length;
int level;} zskiplist;
该结构体包含如下属性。
1)header:指向跳跃表头节点。头节点是跳跃表的一个特殊节点,它的level数组元素个数为64。头节点在有序集合中不存储任何member和score值,ele值为NULL,score值为0;也不计入跳跃表的总长度。头节点在初始化时,64个元素的for-ward都指向NULL,span值都为0。
2)tail:指向跳跃表尾节点。
3)length:跳跃表长度,表示除头节点之外的节点总数。
4)level:跳跃表的高度。通过跳跃表结构体的属性我们可以看到,程序可以在O(1)的时间复杂度下,快速获取到跳跃表的头节点、尾节点、长度和高度。