跳跃表简介

发布时间: 2020-09-02 11:11:12文章作者: 网站编辑阅读量: 350

　　跳跃表简介 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；其他节点指向最底层的前一个节点。
　　
　　跳跃表每个节点维护了多个指向其他节点的指针，所以在跳跃表进行查找、插入、删除操作时可以跳过一些节点，快速找到操作需要的节点。归根结底，跳跃表是以牺牲空间的形式来达到快速查找的目的。跳跃表与平衡树相比，实现方式更简单，只要熟悉有序链表，就可以轻松地掌握跳跃表。

最热文章

随机推荐

web服务器如何配置？web服务器和应用服务器部署

企业网站云服务器配置推荐