1. 跳跃表的用处
- 有序集合(zset)的底层可以采用数组, 链表, 平衡树等结果来实现, 但是他们都有各自的缺点 . 数组方便查询, 但不便于插入和删除, 链表方便插入和删除, 但是不利于查找, 平衡树/红黑树效率高但是实现起来很复杂
- 所以Redis自己实现了跳跃表来来当做有序集合(zset)的底层实现, 他的查询复杂度平均O(logN), 最坏O(N), 堪比红黑树, 但实现起来远比红黑树简单
2. 跳跃表的具体示例
我们先来看一下如果用有序链表来实现有序集合
插入和删除为O(1), 但是查找的复杂度为O(N)
但是我们看跳跃表的实现
我们从有序链表中选取部分节点, 组成一个新的链表如图中的10 -> 30 -> 50 -> 70 -> null, 当做一级索引
如果一级索引中节点还是很多, 我们可以再从一级索引中选取部分节点, 再组成一个新的链表, 并以此作为原始链表的二级索引10 -> 50 -> null
跳跃表的查找
那么跳跃表是如何进行查找的呢
- 优先从高层查找
- 若当前节点的值, 小于要查找的值, 并且next指针指向大于目标值的节点, 就要降一级寻找, 或者next指针指向了null, 那么也需要降一级查找
跳跃表的具体实现
跳跃表底层使用了zskiplist, 和zskiplistnode两个结构体来实现
zskiplist
typedef struct zskiplist {
struct zskiplistNode *header, *tail;
unsigned long length;
int level;
} zskiplist;
- header 指向跳跃表表头节点, tail指向表尾节点
- length:记录跳跃表的长度,也即是,跳跃表目前包含节点的数量(表头节点不计算在内)
- level:记录目前跳跃表内,层数最大的那个节点的层数(表头节点的层数不计算在内)，通过这个属性可以在O(1)的时间复杂度内获取层数最高的节点的层数。
typedef struct zskiplistNode {
sds ele;
double score;
// 后退指针
struct zskiplistNode *backward;
// 层
struct zskiplistLevel {
// 前进指针
struct zskiplistNode *forward;
/**
* 跨度实际上是用来计算元素排名(rank)的，
* 在查找某个节点的过程中，将沿途访过的所有层的跨度累积起来，
* 得到的结果就是目标节点在跳跃表中的排位
*/
unsigned long span;
} level[];
} zskiplistNode;
-
backward 指针指向前一个节点, 用于方便寻找数据
-
sds动态字符串存储内容, score存储分数, 用来排序使用
-
level(每个节点的层数) :
节点中用1、2、L3等字样标记节点的各个层,L1代表第一层,L代表第二层,以此类推.每个层都带有两个属性:前进指针和跨度。前进指针用于访问位于表尾方向的其他节点,而跨度则记录了前进指针所指向节点和当前节点的距离(跨度越大、距离越远)。在上图中,连线上带有数字的箭头就代表前进指针,而那个数字就是跨度。当程序从表头向表尾进行遍历时,访问会沿着层的前进指针进行。
相当于这是三个节点第一个节点处于第0层, 第二个节点他是可以处于三层, 第三个节点可以处于5层
下图是根据具体一点的一个跳跃表实现
header指向的是一个层高为32的伪头结点, 实际链表的开端是这个伪头结点的后一个节点, 根据这个伪头结点就可以快速的找到层数最高的, 因为其他节点的层数都是要比32小的
本文重点
- 跳跃表基于单链表加索引的方式实现
- 跳跃表以空间换时间的方式提升了查找速度
- Redis有序集合在节点元素较大或者元素数量较多时使用跳跃表实现
- Redis的跳跃表实现由 zskiplist和 zskiplistnode两个结构组成,其中 zskiplist用于保存跳跃表信息(比如表头节点、表尾节点、长度),而zskiplistnode则用于表示跳跃表节点
- Redis每个跳跃表节点的层高都是1至32之间的随机数