redis源码解析--跳跃表
程序员文章站
2022-04-02 18:08:42
...
一、什么是跳跃表?
定义:
跳跃表是一种有序数据结构,它通过在每个节点中维护多个指向其他节点的指针,从而达到快速访问节点的目的。
注意几个关键词:
- 有序:结构是有序的
- 每个节点维护多个指针,本身结构是链表形式,和普通链表的不同之处在于每个元素内含多个指针
跳跃表支持平均O(logN),最坏O(N)复杂度的节点查询,大部分情况下,跳跃表的效率可以和平衡树相媲美,
并且因为跳跃表的实现比平衡树要来得简单,所以有不少程序都使用跳跃表来替代平衡树。
二、跳跃表示意图
从图中可以看到:
- 表头(head):负责维护跳跃表的节点指针。
- 跳跃表节点:保存着元素值,以及多个层。
- 下层的指针节点包含上层节点,最底层保持所有元素
三、redis哪些地方使用了跳跃表?
Redis使用跳跃表作为有序集合键的底层实现之一,如果一个有序集合包含你的元素较多,或者成员字符串较长,Redis就会使用跳跃表来作为有序集合的底层实现。
四、redis中跳跃表是如何实现的?
核心数据结构:
typedef struct zskiplistNode {
robj *obj;
double score;
struct zskiplistNode *backward;
struct zskiplistLevel {
struct zskiplistNode *forward;
unsigned int span;
} level[];
} zskiplistNode;
typedef struct zskiplist {
struct zskiplistNode *header, *tail;
unsigned long length;
int level;
} zskiplist;
zskiplistNode
结构用于表示跳跃表节点,zskiplist
保持跳跃表节点的相关信息,如节点数量,表头表尾等。