《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 条评论
登录 后参与评论

相关文章

来自专栏MelonTeam专栏

Bitmap 源码阅读笔记

导语: Android 系统上的图片的处理,跟Bitmap 这个类脱不了关系,我们有必要去深入阅读里面的源码,以便在工作中能更好的处理Bitmap相关的问题...

2608
来自专栏Petrichor的专栏

Dataset 列表:机器学习研究

In computer vision, face images have been used extensively to develop face recog...

1801
来自专栏前端儿

Web 前端颜色值--字体--使用,整理整理

颜色值 CSS 颜色使用组合了红绿蓝颜色值 (RGB) 的十六进制 (hex) 表示法进行定义。对光源进行设置的最低值可以是 0(十六进制 00)。最高值是 2...

2752
来自专栏marsggbo

Udacity并行计算课程 CS344 编程作业答案

892
来自专栏跟着阿笨一起玩NET

c# 使用timer定时器操作,上次定时到了以后,下次还未执行完怎么处理

------解决方案-------------------------------------------------------- 开始的时候,禁用定时器,你...

3031
来自专栏搞前端的李蚊子

Html5模拟通讯录人员排序(sen.js)

// JavaScript Document  var PY_Json_Str = ""; var PY_Str_1 = ""; var PY_Str_...

6356
来自专栏码匠的流水账

spring security reactive获取security context

本文主要研究下reactive模式下的spring security context的获取。

2122
来自专栏linux驱动个人学习

高通msm8909耳机调试

1、DTS相应修改: DTS相关代码:kernel/arch/arm/boot/dts/qcom/msm8909-qrd-skuc.dtsi: 1 s...

8055
来自专栏Golang语言社区

Knapsack problem algorithms for my real-life carry-on knapsack

I'm a nomad and live out of one carry-on bag. This means that the total weight o...

1192
来自专栏余生开发

echarts太阳分布图-饼图来回穿梭

var dom = document.getElementById("container");

1412

扫码关注云+社区