跳跃表

跳跃列表(skip list),简称跳表,它允许快速查询一个有序连续元素的数据链表

Redis 中的有序集合 (Sorted Set) 就是用跳表来实现的

跳表是一种动态数据结构,支持快速的插入、删除、查找操作,时间复杂度都是 O(logn),快速查询是通过维护一个多层次的链表

跳跃列表是按层建造的。底层是一个普通的有序链表。每个更高层都充当下面列表的“快速通道”,这里在第i层中的元素按某个固定的概率p(通常为 1/2 或 1/4 )出现在第 i+1 层中

比如下面有个原始的有序列表

3 6 7 9 12 17 19 21 25 26

如果我们需要查询其中 19,需要从头开始遍历,时间复杂度为O(n)

那么如何提高搜索速度呢,很简单,做个索引(即新增一个长度为一半的链表)

  6   9    17    21    26
3 6 7 9 12 17 19 21 25 26

此时我们只需要遍历第一层(6->9->17->21),发现在17和21之间,然后通过17上面的指针回到最底层原始列表的17位置向后遍历即可找到,速度快了近1倍

同理,我们可以不断的增加层数,直到最高层的元素个数小于等于2

      9          21
  6   9    17    21    26
3 6 7 9 12 17 19 21 25 26


上面只是理论,而且是按照 1/2 来搭建的,而实际场景是里面的数据是一个个加进去的,而且会有删除等操作,所以需要一些技术来保持跳表的相对平衡,而且也不强制上层是下层的 1/2 

当我们不停地往跳表中插入数据时,如果我们不更新索引,就有可能出现某 2 个索引结点之间数据非常多的情况。极端情况下,跳表还会退化成单链表

红黑树、AVL 树这样平衡二叉树,它们是通过左右旋的方式保持左右子树的大小平衡


插入操作:

跳表是通过一个随机函数来决定的

当我们往跳表中插入数据的时候,我们可以选择同时将这个数据插入到部分索引层中,我们通过一个随机函数,来决定将这个结点插入到哪几级索引中

比如随机函数生成了值 K,那我们就将这个结点添加到第一级到第 K 级这 K 级索引中,下图为插入数据6, k = 2


随机函数的选择很有讲究,从概率上来讲,能够保证跳表的索引大小和数据大小平衡性,不至于性能过度退化。如果感兴趣的话,可以参考 Redis 中关于有序集合的跳表实现


删除操作:

删除操作比较简单,直接从高层往下遍历,找到每层需要删除的节点删除即可,如果其中一层节点数为1,难么该层也可以一并删除


相较于红黑树:

1.跳表的复杂度和红黑树差不多,但是实现起来更简单

2.在并发环境下跳表有另外一个优势,红黑树在插入和删除的时候可能需要做一些重平衡的操作(左旋右旋),这样的操作可能会涉及到整个树的其他部分,而跳表的操作显然更加局部性一些,锁需要盯住的节点更少,因此在这样的情况下性能好一些


参考:

wiki-跳跃列表

跳表──没听过但很犀利的数据结构

漫画:什么是跳表?

上一篇: 链表
下一篇: 
作者邮箱: 203328517@qq.com