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

相关文章

来自专栏数据结构与算法

P3808 【模版】AC自动机(简单版)

题目背景 这是一道简单的AC自动机模版题。 用于检测正确性以及算法常数。 为了防止卡OJ,在保证正确的基础上只有两组数据,请不要恶意提交。 题目描述 给定n个模...

2566
来自专栏肖洒的博客

数据结构笔记(一)

算法是解决特定问题求解步骤的描述,在计算机中表现为指令的有限序列,并且每条指令表示一个或多个操作。

543
来自专栏算法与数据结构

PTA 7-1 有序链表的插入(20 分)

已知一个递增有序链表L(带头结点,元素为整数),编写程序将一个新整数插入到L中,并保持L的有序性。 其中单链表的类型定义参考如下: typedef int el...

2508
来自专栏mathor

线性表(二)

985
来自专栏数据结构与算法

#106. 二逼平衡树(附带详细代码注释)

内存限制:512 MiB时间限制:4000 ms标准输入输出 题目类型:传统评测方式:文本比较 上传者: 匿名 提交提交记录统计讨论测试数据 题目描述 这是一道...

3627
来自专栏真皮专栏

Data Structurestackheapheap的实现索引堆tree并查集图 Graph

堆的基本性质: ①堆中的某一个节点总是不小于或不大于其父节点的值。 ②堆总是一棵完全二叉树 比较经典的堆有二叉堆,费波纳茨堆等等。如果一棵二叉树最下层上的...

502
来自专栏王硕

原 pg查询树的简单解读

34013
来自专栏C/C++基础

图的周游

图的周游:是一种按某种方式系统地访问图中的所有节点的过程,它使每个节点都被访问且只访问一次。图的周游也称图的遍历。

762
来自专栏尾尾部落

[算法总结] 一文搞懂面试链表题

链表是面试过程中经常被问到的,这里把剑指offer 和 LeetCode 中的相关题目做一个汇总,方便复习。

481
来自专栏java达人

Java 8 Stream 教程 (二)

作者:Benjamin 译者:java达人 来源:http://winterbe.com/posts/2014/07/31/java8-stream-tuto...

19310

扫描关注云+社区