redis学习之四skiplist
之前相关联文章:
redis学习之一SDS
redis学习之二链表
redis学习之三字典
一 经典的skiplist
我们先来看看skiplist的一张示意图:
文章图片
这是在一个有序列表{3,7,11,19,22,26,37}里查找23这个值的一个过程,它是从头节点的最上层开始,经过每个层的比较判断来进行节点的定位。
skiplist特性:
- 由多层组成。
- 每一层都是有序的链表。
- 最底层(Level 1)的链表包含所有元素。
- 如果一个元素出现在 Level i 的链表中,则它在 Level i 之下的链表也都会出现。
- 每个节点包含两个指针,一个指向同一链表中的下一个元素,一个指向下面一层的元素。
【redis学习之四skiplist】skiplist定义
typedef struct zskiplist{
//表头节点和表尾节点
struct zskiplistNode *header,*tail;
//表中节点数量
unsigned long length;
//最大节点层数
int level;
}zskiplist;
二 redis里skiplist
redis里skiplist定义:
typeof struct zskiplistNode{
//后退节点,当前节点指向的前一个节点,从后向前遍历时使用
struct zskiplistNode *backward;
//分值
double score;
//成员对象
robj *obj;
//层
strcut zskiplistLevle{
//前进指针
struct zskiplistNode *forward;
//跨度
unsigned int span;
}level[];
}zskiplistNode;
文章图片
说明:图中是redis里使用经过改造过的skiplist,BW是后退指针;1.0/2.0/3.0是分值;o1/o2/o3是对象。
redis里的skiplist与经典的skiplist之间的比较,有如下特点:
- 分数(score)允许重复,也就是skiplist的key是充许重复的。
- 大比较过程中,需要比较score也需要比较数据本身。score相同时,数据本身是按字典有序的。
- 第一层是一个双向链表,方便由后向前遍历。
- 跨度span是用来计算排位(rank)的:在查找某个节点的过程中,将沿途访问过的所有层的跨度累计起来,得到的结果就是目标节点在skiplist中的排位。
Redis中的sorted set,是在skiplist, dict和ziplist基础上构建起来的:
- 当数据较少时,sorted set是由一个ziplist来实现的。
- 当数据多的时候,sorted set是由一个叫zset的数据结构来实现的,这个zset包含一个dict + 一个skiplist。dict用来查询数据到分数(score)的对应关系,而skiplist用来根据分数查询数据(可能是范围查找)。
黄健宏的《Redis设计与实现》一书
张铁蕾关于skiplist的文章
其它文章
推荐阅读
- 由浅入深理解AOP
- 继续努力,自主学习家庭Day135(20181015)
- python学习之|python学习之 实现QQ自动发送消息
- 一起来学习C语言的字符串转换函数
- 定制一套英文学习方案
- 漫画初学者如何学习漫画背景的透视画法(这篇教程请收藏好了!)
- 《深度倾听》第5天──「RIA学习力」便签输出第16期
- 如何更好的去学习
- 【韩语学习】(韩语随堂笔记整理)
- 焦点学习田源分享第267天《来访》