跳跃表
先来回顾常规的跳跃表。
!!!下面的图片和内容都来自于这个链接Redis数据结构——跳跃表 - 随心所于 - 博客园
对于一个有序的链表,我们如何才能快速定位一个元素呢?只能遍历,时间复杂度是O(N),效率非常低。
既然链表是有序的,我们就可以建立索引,在上一层维护一个索引,也是链表的形式
当我们要查找元素8时,先通过索引定位到8在7和9之间,那么我们直接在7和9之间遍历可以找到。
当元素数量更多时,我们还可以继续向上抽取索引,查询效率明显提升。
这种通过为链表维护多级索引的结构,就是跳跃表
在链表上建立索引,虽然需要占用额外的空间来维护索引,但是对于元素数量非常多时,这些索引占用的空间就不那么重要了,是空间换时间的思想。
Redis中的跳跃表
跳跃表skiplist是一种有序的数据结构,通过在每个节点中维持多个指向其他节点的指针,从而达到快速访问节点的目的。
在大部分情况下,跳跃表的效率可以媲美平衡树(AVL树),并且跳跃表的实现比平衡树更简单。
跳跃表是有序集合底层的实现方式之一,如果一个有序集合中包含的元素数量比较多,或者有序集合中的元素是比较长的字符串时,Redis就会使用跳跃表来作为有序集合的实现方式
实现
简单点说,在Redis中,每个节点都包含若干层,每一层就是一级索引。
在Redis中,跳跃表是由zskiplistNode和zskiplist两个结构定义:
- zskiplistNode表示一个节点。
- zskiplist记录整个跳跃表的信息,例如头节点、尾节点、层级
最左侧的蓝色结构就是zskiplist,该结构包含以下属性: - header:指向跳跃表的头结点
- tail:指向跳跃表的尾节点
- level:记录目前跳跃表内,最大的层数,即顶级索引所在的层数
- length:跳跃表的长度,即跳跃表目前包含节点的数量(表头节点不计入)
zskiplistNode结构,包含以下属性:
- 层level:L1表示第一层,L2表示第二层,以此类推。每一层都有两个属性:前进指针和跨度
- 前进指针用于访问位于表尾方向的其他节点
- 跨度记录了前进指针所指向的节点与当前节点的距离。
- 后退指针bw:指向位于当前节点的前一个节点,后退指针在从尾向头遍历时使用
- 分值score:节点的分值,在跳跃表中,节点按各自所保存的分值从小到大排序
- 成员对象obj:各个节点中真实的数据对象
参考文章
- Redis数据结构——跳跃表 - 随心所于 - 博客园