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

相关文章

来自专栏静默虚空的博客

排序六 堆排序

堆的概念 在介绍堆排序之前,首先需要说明一下,堆是个什么玩意儿。 堆是一棵顺序存储的完全二叉树。 其中每个结点的关键字都不大于其孩子结点的关键字,这样的堆称为小...

17110
来自专栏用户画像

7.4.2 选择排序之堆排序

堆排序是一个树形选择排序方法,它的特点是:在排序过程中,将L[1...n]看成是一棵完全二叉树的顺序存储结构,

554
来自专栏决胜机器学习

PHP数据结构(六) ——树与二叉树之概念及存储结构

PHP数据结构(六)——树与二叉树之概念及存储结构 (原创内容,转载请注明来源,谢谢) 一、树的含义 1、树为非线性结构,是n(n>=0)个节点的有限集,非空树...

41110
来自专栏算法channel

基本算法|图解各种树(二)

01 — 二叉搜索树 基本算法|图解各种树(一) 二叉搜索树,又称为二叉排序树,简写为 BST,它与线性表,链表,二叉树间的关系,二维链表近似是二叉树,BST继...

2625
来自专栏算法channel

二叉树非递归版的后序遍历算法

本公众号主要推送关于对算法的思考以及应用的消息。算法思想说来有,分而治之,搜索,动态规划,回溯,贪心等,结合这些思想再去思考如今很火的大数据,云计算和机器学习,...

36810
来自专栏深度学习思考者

Python学习(三) 八大排序算法的实现(上)

   本文Python实现了直接插入排序、基数排序、冒泡排序、快速排序、直接选择排序、堆排序、归并排序、希尔排序。    上篇来介绍前四种排序方式:  ...

1828
来自专栏codingforever

经典算法巡礼(四) -- 排序之希尔排序

希尔排序与之前的排序算法不同,她是以她的发明者Donald Shell来命名的。她是插入排序的一种改进版本。

212
来自专栏python学习路

数据结构与算法(二)

排序与搜索 排序算法(英语:Sorting algorithm)是一种能将一串数据依照特定顺序进行排列的一种算法。 排序算法的稳定性 稳定性:稳定排序算法会让原...

3168
来自专栏恰同学骚年

数据结构基础温故-7.排序

排序(Sorting)是计算机内经常进行的一种操作,其目的是将一组“无序”的记录序列调整为按关键字“有序”的记录序列。如何进行排序,特别是高效率地进行排序时计算...

701
来自专栏java学习

请你对Java中树的了解有多少?

树 1200101班的学生信息表如图6.1所示,其中学生被分到了不同的学习小组,第一组组长是李华,组员有王丽、张阳、赵斌; 第二组组长是孙琪,组员有马丹; 第三...

3375

扫码关注云+社区