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

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

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

一、概述

最近在学习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 条评论
登录 后参与评论

相关文章

来自专栏章鱼的慢慢技术路

Go指南练习_循环与函数

1242
来自专栏华章科技

程序员必须知道的十大基础实用算法及其讲解

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要Ο(nlogn) 次比较。在最坏状况下则需要Ο(n2) 次比较,但这种状况并不常见。...

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

Sweet Snippet系列 之 随机选择

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

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

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

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

2646
来自专栏智能算法

程序员必须知道的十大基础实用算法及其讲解

出自博客园 原文地址:http://kb.cnblogs.com/page/210687/ 算法一:快速排序算法   快速排序是由东尼·霍尔所发展的一种排序算法...

3598
来自专栏钱塘大数据

【干货】十大必须掌握的基础实用算法及其讲解

作者:CSDN大数据 算法一:快速排序算法 快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要Ο(nlogn) 次比较。在最坏状况下...

2736
来自专栏有趣的Python和你

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

993
来自专栏编程之旅

数据结构——最小生成树(C++和Java实现)

快要一整个月没有更新博客了,之前的几周每周都想着要写,但是最后时间还是排不开,最近的状态是一直在写代码,一直在怼工作的需求,顺便刷刷算法题,国庆则是没心没肺的玩...

1554
来自专栏算法修养

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

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

2924
来自专栏小樱的经验随笔

Codeforces 626E Simple Skewness(暴力枚举+二分)

E. Simple Skewness time limit per test:3 seconds memory limit per test:256 megab...

3014

扫码关注云+社区