有趣的算法(二)——跳跃表的分析

有趣的算法(二)——跳跃表的分析

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

一、概述

最近在学习redis,其中说到当使用redis的sorted set类型时,如果数据量大,redis内部会使用跳跃表结合散列表的方式对数据进行存储。其中散列表主要用在存储score,即hash的方式——键值对。而由于sorted set的值按照score有序排序,因此跳跃表用于存储score和内容的对应关系。

二、理想跳跃表的存储

跳跃表是一种改进的链表,理想的跳跃表如下图:

从图中可以看到,跳跃表通过增加存储,来达到查询时的类二分法。理想跳跃表,第一层的数字是从小到大排序,第二层存储了第一层每两个中的一个,第三层存第二层每两个中的一个,以此类推,最后一层存储2个。另外,除了第一层,其余每一层每一个元素都指向下一层中和本元素值相同的元素。

这样做的好处在于,查询的时候可以从最高层开始查找,从小到大,当匹配到小于目标值的最大值时,进入下一层进行查找,以此类推,直到找到结果或确定结果不存在。

三、redis中sorted set的值存储

类似跳跃表,但是为了方便逆向排序,对每个元素加入了指向前一个元素的指针。另外根据sorted set特性,允许跳跃表中的元素值相同。

四、类理想跳跃表

理想跳跃表对于查找来说实现完全的二分法,速度最快。但是,当元素插入、删除时,如果仍使用理想跳跃表,维护起来极其复杂。因此,通常采用类理想跳跃表,即非理想情况下的最优,而又最利于元素的插入和删除。

观察理想跳跃表,发现高层元素的个数总是下一层元素的一半。现采用概率的方式,第一层所有新增的数据全部加入,第二层开始,当第一层元素插入后的,其的前后都没有对应的第二层的元素指向,则在第二层直接加入;如果前后都有,则不加入;如果前后有一个指向,则用随机的方式,如果随机出值,就在第二层进行增加,否则不增加。高层类推。

此方法在数据量小的时候,偏差较大,而当数据量非常大的时候,由于总是0.5的几率插入,因此概率上是一个接近完美的跳跃表。

因此,数据量小的时候,不适合使用跳跃表,因为n很小的时候,O(1)和O(n)差距不大。当数据量大的时候,由于类理想跳跃表又接近于理想跳跃表,则可以很好的使用。

——written by linhxx 2017.08.07

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

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

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏算法修养

POJ 1964&HDU 1505&HOJ 1644 City Game(最大0,1子矩阵和总结)

最大01子矩阵和,就是一个矩阵的元素不是0就是1,然后求最大的子矩阵,子矩阵里的元素都是相同的。 这个题目,三个oj有不同的要求,hoj的要求是5s,...

3014
来自专栏有趣的Python和你

Python数据分析之锁具装箱问题问题重述问题分析建模与求解

1073
来自专栏潇涧技术专栏

Python Algorithms - C3 Counting 101

原书主要介绍了一些基础数学,例如排列组合以及递归循环等,但是本节只重点介绍计算算法的运行时间的三种方法

754
来自专栏专知

【PyTorch实战】手把手教你用torchtext处理文本数据

【导读】我们一直在关心深度学习模型的具体实现, 实际上,无论是什么实验, 数据的处理总是占大头的。如何将一个纯文本数据(比如一个 txt 文本), 变成一个模型...

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

2017.7.21夏令营清北学堂解题报告

预计分数: 60+30+0=90=划水 实际分数: 90+30+20=140=rank5=雷蛇鼠标 一句话总结:今天该买彩票! T1: 题目描述 从前有一个?...

2746
来自专栏数说工作室

【SAS Says】高级篇:IML(1)

开篇话: 前段时间数说君征原创稿,果真得到了不少牛人的赐稿,比如本文的作者Ansta,作为数说工作室的特约撰稿人,将会承担下“【SAS Says】高级篇” 的写...

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

BZOJ4872: [Shoi2017]分手是祝愿

Description Zeit und Raum trennen dich und mich. 时空将你我分开。B 君在玩一个游戏,这个游戏由 n 个灯和 n...

2895
来自专栏专注数据中心高性能网络技术研发

[LeetCode]Array主题系列{1,11,15,16,18,26,27,31,33,34题}

1.内容介绍 开一篇文章记录在leetcode中array主题下面的题目和自己的思考以及优化过程,具体内容层次按照{题目,分析,初解,初解结果,优化解,优化解结...

3346
来自专栏聊聊技术

原 初学算法-快速排序与线性时间选择(De

3636
来自专栏tkokof 的技术,小趣及杂念

Sweet Snippet系列 之 随机选择

  平日工作学习时总会遇到一些令人欣喜的代码段子(Snippet),虽然都很短小,但是其间所含的道理都颇有意味,遂而觉得应该不时的将她们记下,一来算作复习整理,...

1062

扫码关注云+社区