新购 续费 升级
超多折扣优惠
阿里云服务器限时两折起
年付每月仅需24元,低至0.73元/天起
阿里云服务器ECS    
弹性可伸缩的计算服务,助您降低 IT 成本,提升运维效率,使您更专注于核心业务创新 [咨询更多]
阿里云存储OSS
简单易用、多重冗余、数据备份高可靠、多层次安全防护安全性更强、低成本 [咨询更多]
阿里云数据库RDS
稳定可靠、可弹性伸缩、更拥有容灾、备份、恢复、监控、迁移等方面的全套解决方案 [咨询更多]
阿里云安全产品
DDoS高防IP、web应用防火墙、安骑士、sll证书、态势感知众多阿里云安全产品热销中 [咨询更多]
阿里云折扣优惠    
云服务器ECS、数据库、负载均衡等产品新购、续费、升级联系客服获取更多专属折扣 [咨询更多]
跳跃表简介
2020-9-2
  跳跃表简介      Redis采用了一种新型的数据结构——跳跃表。跳跃表的效率堪比红黑树,然而其实现却远比红黑树简单。
  
  在了解跳跃表之前,我们先了解一下有序链表。有序链表是所有元素以递增或递减方式有序排列的数据结构,其中每个节点都有指向下个节点的next指针,最后一个节点的next指针指向NULL。递增有序链表举例如图3-1所示。
  递增有序链表举例
  图3-1 递增有序链表举例
  
  如图3-1所示的有序链表,如果要查询值为51的元素,需要从第一个元素开始依次向后查找、比较才可以找到,查找顺序为1→11→21→31→41→51,共6次比较,时间复杂度为O(N)。有序链表的插入和删除操作都需要先找到合适的位置再修改next指针,修改操作基本不消耗时间,所以插入、删除、修改有序链表的耗时主要在查找元素上。
  
  如果我们将有序链表中的部分节点分层,每一层都是一个有序链表。在查找时优先从最高层开始向后查找,当到达某节点时,如果next节点值大于要查找的值或next指针指向NULL,则从当前节点下降一层继续向后查找,这样是否可以提升查找效率呢?
  分层有序链表
  图3-2 分层有序链表
  
  分层有序链表如图3-2所示,我们再次查找值为51的节点,查找步骤如下。
  
  1)从第2层开始,1节点比51节点小,向后比较。
  
  2)21节点比51节点小,继续向后比较。第2层21节点的next指针指向NULL,所以从21节点开始需要下降一层到第1层继续向后比较。
  
  3)第1层中,21节点的next节点为41节点,41节点比51节点小,继续向后比较。第1层41节点的next节点为61节点,比要查找的51节点大,所以从41节点开始下降一层到第0层继续向后比较。
  
  4)在第0层,51节点为要查询的节点,节点被找到。采用图3-2所示的数据结构后,总共查找4次就可以找到51节点,比有序链表少2次。当数据量大时,优势会更明显。综上所述,通过将有序集合的部分节点分层,由最上层开始依次向后查找,如果本层的next节点大于要查找的值或next节点为NULL,则从本节点开始,降低一层继续向后查找,依次类推,如果找到则返回节点;否则返回NULL。采用该原理查找节点,在节点数量比较多时,可以跳过一些节点,查询效率大大提升,这就是跳跃表的基本思想。
  
  跳跃表的实现过程如图3-3所示。
  跳跃表的实现过程
  图3-3 跳跃表的实现过程
  
  从图3-3中我们可以看出跳跃表有如下性质。
  
  1)跳跃表由很多层构成。
  
  2)跳跃表有一个头(header)节点,头节点中有一个64层的结构,每层的结构包含指向本层的下个节点的指针,指向本层下个节点中间所跨越的节点个数为本层的跨度(span)。
  
  3)除头节点外,层数最多的节点的层高为跳跃表的高度(level),图3-3中跳跃表的高度为3。
  
  4)每层都是一个有序链表,数据递增。
  
  5)除header节点外,一个元素在上层有序链表中出现,则它一定会在下层有序链表中出现。
  
  6)跳跃表每层最后一个节点指向NULL,表示本层有序链表的结束。
  
  7)跳跃表拥有一个tail指针,指向跳跃表最后一个节点。
  
  8)最底层的有序链表包含所有节点,最底层的节点个数为跳跃表的长度(length)(不包括头节点),图3-3中跳跃表的长度为7。9)每个节点包含一个后退指针,头节点和第一个节点指向NULL;其他节点指向最底层的前一个节点。
  
  跳跃表每个节点维护了多个指向其他节点的指针,所以在跳跃表进行查找、插入、删除操作时可以跳过一些节点,快速找到操作需要的节点。归根结底,跳跃表是以牺牲空间的形式来达到快速查找的目的。跳跃表与平衡树相比,实现方式更简单,只要熟悉有序链表,就可以轻松地掌握跳跃表。
联系客服免费领取更多阿里云产品新购、续费升级折扣,叠加官网活动折上折更优惠