内容纲要
跳跃表的优点
-
可以快速查找到需要的节点
-
可以在O(1)的时间复杂度下,快速获得跳跃表的头节点、尾结点、长度和高度
跳跃表的应用场景
跳跃表是Redis有序集合(sorted-set)类型的底层实现,效率高,实现简单。
跳跃表的思想
跳跃表是将有序链表中的部分节点提取出来分层,每一层都是一个有序链表。如图所示
简单讲:链表加多级索引的结构,就叫做跳跃表。使用多级索引在跳跃表中查找元素,可以提升查询效率。
跳跃表的查找
在查找时优先从最高层开始向后查找,当到达某个节点时,如果next节点值大于要查找的值或next指针指向null,则从当前节点下降一层继续向后查找。
举例:
查找元素9,按道理我们需要从头结点开始遍历,一共遍历8个结点才能找到元素9。
第一次分层:遍历5次找到元素9(红色的线为查找路径)
第二次分层:遍历4次找到元素9
第三层分层:遍历4次找到元素9
这种数据结构,就是跳跃表,它具有二分查找的功能。
跳跃表的插入
上面例子中,9个结点,一共4层,是理想的跳跃表。
可以通过抛硬币(概率1/2)的方式来决定新插入结点跨越的层数
-
正面:插入上层
-
背面:不插入
跳跃表的删除
通过找到指定元素并删除每层的该元素即可。
跳跃表的特点
-
每层都是一个有序链表
-
查找次数近似于层数(1/2)
-
底层包含所有元素
-
空间复杂度 O(n) 扩充了一倍
Redis跳跃表的实现
//跳跃表节点
typedef struct zskiplistNode {
sds ele; /* 存储字符串类型数据 redis3.0版本中使用robj类型表示,
但是在redis4.0.1中直接使用sds类型表示 */
double score;//存储排序的分值
struct zskiplistNode *backward;//后退指针
/*
层,柔性数组,随机生成1-64的值
*/
struct zskiplistLevel {
struct zskiplistNode *forward; //指向本层下一个节点
unsigned int span;//本层下个节点到本节点的元素个数
} level[];
} zskiplistNode;
//链表
typedef struct zskiplist{
//表头节点和表尾节点
structz skiplistNode *header, *tail;
//表中节点的数量
unsigned long length;
//表中层数最大的节点的层数
int level;
}zskiplist;
完整的跳跃表结构,如下图所示
评论前必须登录!
注册