《Redis设计与实现》读书笔记(四) ——Redis中的跳跃表

《Redis设计与实现》读书笔记(四) ——Redis中的跳跃表

(原创内容,转载请注明来源,谢谢)

一、概述

跳跃表(skiplist)是一种有序的数据结构,它通过每个节点中维持多个指向其他节点的指针,从而实现快速访问。跳跃表平均O(logN),最坏O(N),支持顺序遍历查找。

在redis中,有序集合(sortedset)的其中一种实现方式就是跳跃表。当有序集合的元素较多,或者集合中的元素是比较常的字符串,则会使用跳跃表来实现。另外,在redis集群节点中的内部数据结构,也是用跳跃表实现。

二、跳跃表实现

跳跃表是由各个跳跃表节点组成。

1、跳跃表数据结构

typedef structzskiplist{
struct zskiplistNode *header,*tail;
unsigned long length;
int level;
}zskiplist;

上图最左边就是跳跃表的结构。

其中,header和tail是跳跃表节点的头结点和尾节点,length是跳跃表的长度(即跳跃表节点的数量,不含头结点),level表示层数中最大节点的层数(不计算表头结点)。

因此,获取跳跃表的表头、表尾、最大层数、长度的时间复杂度都是O(1)。

2、跳跃表节点数据结构

typedef structzskiplistNode{
struct zskiplistLevel{
struct zskiplistNode *forward;
unsigned int span;
}level[];
struct zskiplistNode *backward;
double score;
robj *obj;
}zskiplistNode;

上图右边四列就是跳跃表节点的结构。

跳跃表节点包含下列四个概念:

1)层(level)。

zskiplistNode中的zskiplistLevel就表示层。上图L1、L2等,也就是层。L1是第一层,L2是第二层,以此类推。

每个层都有两个属性,前进指针(forward)和跨度(span)。前进指针用于访问表尾方向的节点,便于跳跃表正向遍历节点的时候,查找下一个节点位置;跨度记录前进指针所指的节点和当前节点的距离,用于计算排位,访问过程中,将沿途访问的所有层的跨度累计起来,得到的结果就是跳跃表的排位。上图中带数字的箭头就表示前进指针,箭头上面的数字就是跨度。当程序从表头向表尾遍历,会沿着前进指针进行。

层的意义:

层的作用是加快访问速度,这也是跳跃表的核心思想。每次创建跳跃表后,根据幂次定律,越大的数字出现的概率越小,随机生成一个1~32之间的值作为level数组的大小,这个就是层的高度。

越高层出现的概率越低,这也是实现跳跃表的中心思想。类似的概念如图所示:

每个节点的层都是随机的,但是每个节点高层的概率都是,越高层概率越低。通过这个高层,可以快速查找到score是某个值(或某个范围的值)的跳跃表节点。

查找方式是,先从最高层进行查找,由于其从小到大排序,因此只要在最高层中确定其在哪两个节点对应的范围之间。其次,再从次高层查找。以此类推,直到在第一层的从小到大遍历,可以确定节点在或不在此跳跃表中。

下图分别是带有1、3、5个层的跳跃表节点:

程序遍历节点的时候,会从头结点开始,沿着zskiplistLevel[i].span=1,从高层开始,逐个遍历下一个节点。直到发现zskiplistLevel[i].forward=null,表示已经完成全部的遍历。

2)后退指针(backward)。

zskiplistNode中的backward就表示后退指针。在上图的节点中用BW来表示,其指向当前节点的前一个节点,用于反向遍历时候使用。

不过后退指针每次只能往回退一个节点,不像前进指针可以一次跳过很多个节点。并且,后退指针不会指向头节点。

3)分值(score)。

zskiplistNode中的score就表示分值。各节点中的数字就是分值,跳跃表中,节点按照分值从小到大排列。

这个分值,即存储有序集合中的score。

4)成员对象(obj)。

zskiplistNode中的obj就表示成员对象的指针,其指向存储着节点的具体内容的redis的sds类型的字符串。

这个obj,即指向有序集合对应的具体值。因此,每个节点的成员对象唯一。

但是,每个节点的分值可以一样。分值一样时,会按照成员变量在字典中的大小顺序,小的靠近表头。

——written by linhxx 2017.08.30

原文发布于微信公众号 - 决胜机器学习(phpthinker)

原文发表时间:2017-08-30

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Leetcode名企之路

【Leetcode】59. 螺旋矩阵 II

给定一个正整数 n,生成一个包含 1 到 n^2 所有元素,且元素按顺时针顺序螺旋排列的正方形矩阵。

820
来自专栏机器学习从入门到成神

2013百度校招笔试真题以及解析(二)

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/sinat_35512245/articl...

931
来自专栏C#

DotNet生成随机数的一些方法

  在项目开发中,一般都会使用到“随机数”,但是在DotNet中的随机数并非真正的随机数,可在一些情况下生成重复的数字,现在总结一下在项目中生成随机数的...

1987
来自专栏xingoo, 一个梦想做发明家的程序员

Spark MLlib 之 Vector向量深入浅出

local vector是一种索引是0开始的整数、内容为double类型,存储在单机上的向量。MLlib支持两种矩阵,dense密集型和sparse稀疏型。一个...

1990
来自专栏网络和编程

float类型加法精度损失问题(C++)

奇怪的就是:a依然是406682816,并没有加一。网上查了一些资料,这里分享一下原因。

48215
来自专栏大神带我来搬砖

如何编写更优雅的代码——java中用break语句模拟goto来中止代码块的执行

根据https://docs.oracle.com/javase/specs/jls/se7/html/jls-14.html, java的break语句不仅可...

2619
来自专栏云霄雨霁

无向图----深度优先搜索

2460
来自专栏ACM算法日常

POJ1258:Agri-Net-最小生成树

Farmer John has been elected mayor of his town! One of his campaign promises was...

922
来自专栏SeanCheney的专栏

《Pandas Cookbook》第02章 DataFrame基本操作1. 选取多个DataFrame列2. 对列名进行排序3. 在整个DataFrame上操作4. 串联DataFrame方法5. 在

3984
来自专栏听雨堂

从MapX到MapXtreme2004[7]-对Table、Feature等的理解

一、Table         2004中,Table还是表,可以来自原始的mapinfo表,也可以来自数据库的二维表、文本等。Table的等价概念是featu...

2028

扫码关注云+社区