原创

跳跃表深入理解

1、认识跳跃表

redis 中 zset 是一个有序非线性的数据结构,它底层核心的数据结构是跳表。跳表(skiplist)是一个特俗的链表,相比一般的链表,有更高的查找效率,其效率可比拟于二叉查找树。

一张关于跳表和跳表搜索过程如下图:

在图中,需要寻找 68,在给出的查找过程中,利用跳表数据结构优势,只比较了3次,横箭头不比较,竖箭头比较。由此可见,跳表预先间隔地保存了有序链表中的节点,从而在查找过程中能达到类似于二分搜索的效果,而二分搜索思想就是通过比较中点数据放弃另一半的查找,从而节省一半的查找时间。缺点即浪费了空间,自古空间和时间两难全。

红黑树在空间和时间效率上略胜跳跃表一筹,但跳跃表实现上相对简单,颇得程序猿们的青睐。redis和leveldb中都有采用跳表。

2、跳跃表的提出

跳表首先由William Pugh在其1990年的论文《Skip lists: A probabilistic alternative to balanced trees》中提出。由该论文的题目可以知道两点:

  1. 跳表是概率型数据结构。
  2. 跳表是用来替代平衡树的数据结构。准确来说,是用来替代自平衡二叉查找树(self-balancing BST)的结构。

比如有个在有序序列中查找某个特定元素的场景:如果序列采用支持随机访问的线性结构(数组)存储,那么很容易地用二分查找来做。但是考虑到增删效率和内存扩展性,很多时候要用不支持随机访问的线性结构(链表)存储,就只能从头遍历、逐个比对。 于是折衷考虑下,如果用二叉树结构(BST)存储,就可以不靠随机访问特性进行二分查找了。 但是普通BST对于插入元素越有序效率就越低,最坏情况会退化回链表。因此提出了自平衡BST结构,保证任何情况下的增删查操作都保持O(logn)的时间复杂度。自平衡BST的代表有AVL树、2-3树及其衍生出来的红黑树。推广不限于二叉树的话,耳熟能详的B树和B+树也属于此类,常用于文件系统和数据库。这样子来看,自平衡BST真香啊,很适合我们的场景,但也存在不爽的点:树的自平衡过程比较复杂,实现起来超级麻烦,在高并发的情况下,加锁也会带来非常可观的损耗。比如AVL树需要LL、LR、RL、RR四种旋转操作来保持平衡,红黑树则需要左旋、右旋和变色三种操作。 那么有没有实现起来简单、和自平衡BST效率想近的实现方法呢?答案就是跳表,并且简单很多。

3、设计思想

跳跃表(skiplist)是一种有序数据结构,它通过在每个节点中维持多个指向其它节点的指针,从而达到快速访问节点的目的。跳跃表在 Redis 里没有其它用途。

跳表就是如下图的链表集合:

跳表具有的性质:

  • 由很多层组成,最底层为第1层,以此类推。层数不会超过一个固定的最大值MAX。
  • 每层都是一个由头节点的有序链表,第1层的链表包含跳表中的所有元素。
  • 如果某个元素在第K层出现,那么在1~K-1层也必定会出现。

很显然这是一种空间换时间的思路,和索引异曲同工。第K层可以认为是第K-1层的索引,用来加速查找。为了避免占用过多空间,第1层之上都不存储实际数据,只有指针。

当查找元素时,会从最顶层链表的头节点开始遍历。如当前节点的下一个节点包含的值比目标元素值小,则继续向右查找。如果下一个节点的值比目标值大,就转到当前层的下一层去查找。重复向右和向下的操作,直到找到与目标值相等的元素为止。下图中的蓝色箭头标记出了查找元素21的步骤。

通过图示查找过程,可以更加明白跳表的含义,因为查找过程确实是跳跃的,比线性查找省时。当数据量越来越大的时候,这种结构的优势就更加明显了。

2.1、插入元素的概率性

前面说过,跳表第K层的元素会按一定的概率出现在K+1层,这种概率是在插入过程中实现的。当按照上述查找流程找到新元素的插入位置上,将其插入第1层。然后通过随机方法来决定是否继续插入第2、3、4、5....层。

int randomizeLevel(double p, int lmax) {  
int level = 1;   
Random random = new Random();    
while (random.nextDouble() < p && level < lmax) {
 level++; 
 } 
 return level; 
 } 

由逻辑可知,随着层树的增加,元素被插入到上层的概率会指数级的下降。这种随机方法也被称为“抛硬币”算法。

相对于插入来说,删除操作没有那么多的逻辑,跟正常的单链表删除一致。

3、为啥Redis不用平衡搜索树来实现?

至于为什么Redis不用平衡搜索树来做,结合Redis作者的话可以认为这么做挺好的,确实在保证底线(最差)的情况下在某些时候还有亮点。

  1. 内存占用更少,自定义参数化决定使用多少内存
  2. 有序集合很多时候用zrange 或者zrevrange 。性能至少不比平衡树差
  3. 简单更容易实现和维护

一句话总结什么是跳表:跳表就是在有序链表的基础上通过增加额外的指针节点来解决查询效率,通过随机插入来提高变更效率的一种数据结构。

4、参考:

《Redis 为什么用跳表而不用平衡树?》

《为什么Redis一定要用跳表来实现有序集合?》

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

关注作者,阅读全部精彩内容

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 深入理解什么是跳跃表

    前面的文章我们学习了性能高效的基于二叉搜索树的动态数据结构红黑树,其平均时间复杂度为O(logN),今天我们再来学习另外一种优秀的数据结构跳跃表,其综合性能与红...

    我是攻城师
  • 跳跃表原理

    跳表这种特殊的数据结果是有 Willam Pugh 发明的。最早出现在1990 年发表的论文《Skip Lists: A Probabilistic Alte...

    王小明_HIT
  • 跳跃表原理和实现

    有时候会被问到链表如果做到二分搜索,可能会有部分的人会去把链表中的值保存到数组来进行二分,但是如果知道跳跃表的话,那么这个数据结构就可以解决这个困惑,它允许快速...

    sunsky
  • redis跳跃表源码详解

    跳跃表是一种有序的数据结构,他通过在每个节点中维护多个指向其它节点的指针,从而达到快速访问节点的目的。跳跃表的查找操作平均时间复杂度为o(logN)。在大部分情...

    榴莲其实还可以
  • 跳跃表确定不了解下😏

    hello,大家好,周五见了。前面几周我们一起看了Redis底层数据结构,如动态字符串SDS,双向链表Adlist,字典Dict,如果有对Redis常见的类型或...

    陈琛
  • Redis的跳跃表确定不了解下吗?

    hello,大家好,前面几周我们一起看了Redis底层数据结构,如动态字符串SDS,双向链表Adlist,字典Dict。

    陈琛
  • 你确定不来了解一下Redis跳跃表的原理吗

    目前经常使用的平衡数据结构有:B树,红黑树,AVL树,Splay Tree, Treep等。想象一下,给你一张草稿纸,一只笔,一个编辑器,你能立即实现一颗红黑树...

    王知无-import_bigdata
  • 浅析SkipList跳跃表原理及代码实现

    SkipList在leveldb以及lucence中都广为使用,是比较高效的数据结构。由于它的代码以及原理实现的简单性,更为人们所接受。我们首先看看SkipLi...

    sunsky
  • 深入理解哈希表

    有些计算机常识的读者都会立刻回答: “一样快,底层都用了哈希表,查找的时间复杂度为 O(1)”。然而实际情况真的是这样么?

    sunsky
  • ConcurrentSkipListMap跳表原理解析

    内部结构如下(图片来源于网络),这里面Node其实就是HeadIndex中的level1,level2,level3中的一个个绿点。

    算法之名
  • 深入理解Java8 Lambda表达式

    匿名函数的应用场景是: 通常是在需要一个函数,但是又不想费神去命名一个函数的场合下使用Lambda表达式。lambda表达式所表示的匿名函数的内容应该是很简单...

    ZhangXianSheng
  • Redis系列(七)底层数据结构之跳跃表

    Redis 已经是大家耳熟能详的东西了,日常工作也都在使用,面试中也是高频的会涉及到,那么我们对它究竟了解有多深刻呢?

    呼延十
  • 收藏 | 医学图像分割:UNet++

    在这篇文章中,我们将探索UNet++: A Nested U-Net Architecture for Medical Image Segmentation这篇...

    计算机视觉联盟
  • 医学图像分割:UNet++

    在这篇文章中,我们将探索UNet++: A Nested U-Net Architecture for Medical Image Segmentation这篇...

    AI算法与图像处理
  • SAP 深入理解SAP DB2表空间(Tablespace)

    表空间是数据库系统中数据库逻辑结构与操作系统物理结构之间建立映射的重要存储结构,它作为数据库与实际存放数据的容器之间的中间层,用于指明数据库中数据的物理位置。任...

    matinal
  • 实战 | 深入理解 Hive ACID 事务表

    来源:https://blog.csdn.net/zjerryj/article/details/91470261

    大数据真好玩
  • ICLR 2021 | 美团AutoML论文:鲁棒的神经网络架构搜索 DARTS-

    高质量模型的设计和更新迭代是当前 AI 生产开发的痛点和难点,在这种背景下,自动化机器学习(AutoML)应运而生。2017年,谷歌正式提出神经网络架构搜索(N...

    美团技术团队
  • 极品Trick | 在ResNet与Transformer均适用的Skip Connection解读

    Skip connection是一种广泛应用于提高深度神经网络性能和收敛性的技术,它通过神经网络层传播的线性分量,缓解了非线性带来的优化困难。但是,从另一个角度...

    用户3605500
  • U-Net 和 ResNet:长短跳跃连接的重要性(生物医学图像分割)

    这次,我们来聊一聊用于生物医学图像分割的的一种全卷积神经网络,这个网络带有长短跳跃连接。

    AI研习社

扫码关注云+社区

领取腾讯云代金券