图解Skip List——本质是空间换时间的数据结构,在lucene的倒排列表,bigtable,hbase,cassandra的memtable,redis中sorted set中均用到

本文涉及的产品
云数据库 Tair(兼容Redis),内存型 2GB
Redis 开源版,标准版 2GB
推荐场景:
搭建游戏排行榜
简介:

Skip List的提出已有二十多年[Pugh, W. (1990)],却依旧应用广泛(Redis、LevelDB等)。作为平衡树(AVL、红黑树、伸展树、树堆)的替代方案,虽然它性能不如平衡树稳定,但是在实现难度上却很有优势。它的查询、插入、删除等主要操作时间复杂度也都是Θ(lgn),空间复杂度是Θ(n)

一个Skip List的结构如下图,除了数据域,每个节点还包括1个或多个域用来保存后续节点的位置。

跳跃表

从结构上看,Skip List通过增加层数,节点上可以带有更多的信息,通过这些信息可以直接访问更远的节点(这 也是Skip List精髓所在),就像跳过去一样,所以取名叫Skip List(跳表)。

Skip List查询

查询操作很简单,比如我们要找图中节点key为20的节点。

  • 我们首先获取到头节点,从头检点的最高层开始(节点中的点表示指向节点的指针),下一个节点是17, 很明显20>17所以应该在后面。继续往后结果是NULL那说明后面没有要找的节点了。
  • 跳到下一层继续往后是2520<25说明后面也没有我们要找的节点了。
  • 再跳到下一层,往后就找到我们要的节点了。如果到最下面一层还找不到,那这个节点就肯定不在表中了(因为最低层包含所有节点)。

跳跃表查找

Skip List插入

插入操作稍微复杂, 首先我们要找到插入位置,怎么找我们刚才已经描述过了。如下图所示,插入key为10的节点,插入点应该是节点9和节点12之间(紫色的线表示要更新的指向)。然后是插入节点10,其实就是链表的逐层插入。 跳跃表插入

这里的需要注意是,逐层插入需要知道节点在每一层的位置,如在level-2中,节点10前面应该是头结点,而后面应该是节点17。 因为查询操作得到的只是最后位置,所以通常需要一个临时的空间来记录这些信息。如果节点的高度超过超过了Skip List的最大层数,那么Skip List的层数相应的需要升高。如节点10的高度是4的话,根据Skip List的结构特点,那么层数需要提高到level-3。

节点高度与Skip List的最大层数

理想的SkipList结构(如图一)是第一层有所有的节点,第二层只有1/2的节点,且是均匀间隔的,第三 层是1/4的节点,且是均匀间隔的...,那么理想的层数是lgnlgn。

每一次插入一个新节点时,最好的做法就是根据当前表的结构得到一个合适的高度,插入后可以让Skip List的尽量的接近理想的结构,但是实现上这会非常的复杂。

Pugh论文中提出的方法是根据概率随机为新节点生成一个高度,具体的算法如下:

  • 给定一个概率pp, 产生一个[0,1)[0,1) 之间的随机数
  • 如果这个随机数小于pp,则高度加11
  • 重复以上动作,直到随机数大于概率pp

虽然随机生成的高度会打破理想的结构,Pugh在论文中证明,这种结构依然有非常高概率可以使得时间复杂度为Θ(lgn)Θ(lgn)。

通常我们还会约束Skip List的最大层数,公式:maxLevel=log1/pnmaxLevel=log1/pn,其中n表示节点总数。 根据Pugh论文中的结论,p为1/2或者1/4时,整体性能会比较好。(当p=1/2时,确定节点高度有的地方称为抛硬币的方法)。

Skip List删除

删除操作跟插入操作类似。  跳跃表删除

有兴趣可以看看Pugh论文!


转自:http://www.zkt.name/skip-list/









本文转自张昺华-sky博客园博客,原文链接:http://www.cnblogs.com/bonelee/p/6409146.html,如需转载请自行联系原作者


相关实践学习
lindorm多模间数据无缝流转
展现了Lindorm多模融合能力——用kafka API写入,无缝流转在各引擎内进行数据存储和计算的实验。
云数据库HBase版使用教程
&nbsp; 相关的阿里云产品:云数据库 HBase 版 面向大数据领域的一站式NoSQL服务,100%兼容开源HBase并深度扩展,支持海量数据下的实时存储、高并发吞吐、轻SQL分析、全文检索、时序时空查询等能力,是风控、推荐、广告、物联网、车联网、Feeds流、数据大屏等场景首选数据库,是为淘宝、支付宝、菜鸟等众多阿里核心业务提供关键支撑的数据库。 了解产品详情:&nbsp;https://cn.aliyun.com/product/hbase &nbsp; ------------------------------------------------------------------------- 阿里云数据库体验:数据库上云实战 开发者云会免费提供一台带自建MySQL的源数据库&nbsp;ECS 实例和一台目标数据库&nbsp;RDS实例。跟着指引,您可以一步步实现将ECS自建数据库迁移到目标数据库RDS。 点击下方链接,领取免费ECS&amp;RDS资源,30分钟完成数据库上云实战!https://developer.aliyun.com/adc/scenario/51eefbd1894e42f6bb9acacadd3f9121?spm=a2c6h.13788135.J_3257954370.9.4ba85f24utseFl
相关文章
|
22天前
|
存储 消息中间件 NoSQL
Redis数据结构:List类型全面解析
Redis数据结构——List类型全面解析:存储多个有序的字符串,列表中每个字符串成为元素 Eelement,最多可以存储 2^32-1 个元素。可对列表两端插入(push)和弹出(pop)、获取指定范围的元素列表等,常见命令。 底层数据结构:3.2版本之前,底层采用**压缩链表ZipList**和**双向链表LinkedList**;3.2版本之后,底层数据结构为**快速链表QuickList** 列表是一种比较灵活的数据结构,可以充当栈、队列、阻塞队列,在实际开发中有很多应用场景。
|
26天前
|
存储 消息中间件 NoSQL
Redis 数据结构与对象
【10月更文挑战第15天】在实际应用中,需要根据具体的业务需求和数据特点来选择合适的数据结构,并合理地设计数据模型,以充分发挥 Redis 的优势。
55 8
|
29天前
|
存储 NoSQL 关系型数据库
Redis 有序集合(sorted set)
10月更文挑战第17天
44 4
|
26天前
|
存储 NoSQL Java
介绍下Redis 的基础数据结构
本文介绍了Redis的基础数据结构,包括动态字符串(SDS)、链表和字典。SDS是Redis自实现的动态字符串,避免了C语言字符串的不足;链表实现了双向链表,提供了高效的操作;字典则类似于Java的HashMap,采用数组加链表的方式存储数据,并支持渐进式rehash,确保高并发下的性能。
介绍下Redis 的基础数据结构
|
30天前
|
NoSQL 关系型数据库 MySQL
Redis 列表(List)
10月更文挑战第16天
17 2
|
1月前
|
消息中间件 存储 监控
redis 的List类型 实现 排行榜
【10月更文挑战第8天】
37 2
|
22天前
|
存储 NoSQL 关系型数据库
Redis的ZSet底层数据结构,ZSet类型全面解析
Redis的ZSet底层数据结构,ZSet类型全面解析;应用场景、底层结构、常用命令;压缩列表ZipList、跳表SkipList;B+树与跳表对比,MySQL为什么使用B+树;ZSet为什么用跳表,而不是B+树、红黑树、二叉树
|
22天前
|
存储 NoSQL Redis
Redis常见面试题:ZSet底层数据结构,SDS、压缩列表ZipList、跳表SkipList
String类型底层数据结构,List类型全面解析,ZSet底层数据结构;简单动态字符串SDS、压缩列表ZipList、哈希表、跳表SkipList、整数数组IntSet
|
5月前
|
安全 Java
java线程之List集合并发安全问题及解决方案
java线程之List集合并发安全问题及解决方案
927 1
|
4月前
|
Java API Apache
怎么在在 Java 中对List进行分区
本文介绍了如何将列表拆分为给定大小的子列表。尽管标准Java集合API未直接支持此功能,但Guava和Apache Commons Collections提供了相关API。