江苏龙网

  1. 主页 > 生活百科 > >

深入理解跳表及其在Redis中的应用

Redis

跳表的时间复杂度与AVL树和红黑树相同，可以达到O(logN)，但是AVL树要维持高度的平衡，红黑树要维持高度的近似平衡，这都会导致插入或者删除节点时的一些时间开销，所以跳表相较于AVL树和红黑树来说，省去了维持高度的平衡的时间开销，但是相应的也付出了更多的空间来存储多个层的节点，所以跳表是用空间换时间的数据结构 。前言跳表可以达到和红黑树一样的时间复杂度 O(logN)，且实现简单，redis 中的有序集合对象的底层数据结构就使用了跳表 。其作者威廉·普评价：跳跃链表是在很多应用中有可能替代平衡树的一种数据结构 。本篇文章将对跳表的实现及在Redis中的应用进行学习 。
一. 跳表的基础概念跳表，即跳跃链表（Skip List），是基于并联的链表数据结构，操作效率可以达到O(logN)，对并发友好，跳表的示意图如下所示 。

深入理解跳表及其在Redis中的应用

文章插图
跳表的特点，可以概括如下 。
•跳表是多层（level）链表结构；
•跳表中的每一层都是一个有序链表，并且按照元素升序（默认）排列；
•跳表中的元素会在哪一层出现是随机决定的，但是只要元素出现在了第 k 层，那么 k 层以下的链表也会出现这个元素；
•跳表的底层的链表包含所有元素；
•跳表头节点和尾节点不存储元素，且头节点和尾节点的层数就是跳表的最大层数；
•跳表中的节点包含两个指针，一个指针指向同层链表的后一节点，一个指针指向下层链表的同元素节点 。
以上图中的跳表为例，如果要查找元素 71，那么查找流程如下图所示 。
深入理解跳表及其在Redis中的应用

文章插图
??从顶层链表的头节点开始查找，查找到元素71的节点时，一共遍历了4个节点，但是如果按照传统链表的方式（即从跳表的底层链表的头节点开始向后查找），那么就需要遍历7个节点，所以跳表以空间换时间，缩短了操作跳表所需要花费的时间 。跳跃列表的算法有同平衡树一样的渐进的预期时间边界，并且更简单、更快速和使用更少的空间 。这种数据结构是由William Pugh(音译为威廉·普)发明的，最早出现于他在1990年发表的论文《Skip Lists: A Probabilistic Alternative to Balanced Trees》 。谷歌上找到一篇作者关于跳表的论文，感兴趣强烈建议下载阅读：
?https://epaperpress.com/sortsearch/download/skiplist.pdf?
跳表在动态查找过程中使用了一种非严格的平衡机制来让插入和删除都更加便利和快捷，这种非严格平衡是基于概率的，而不是平衡树的严格平衡 。说到非严格平衡，首先想到的是红黑树RbTree，它同样采用非严格平衡来避免像AVL那样调整树的结构，这里就不展开讲红黑树了，看来跳表也是类似的路子，但是是基于概率实现的 。
二. 跳表的节点已知跳表中的节点，需要有指向当前层链表后一节点的指针，和指向下层链表的同元素节点的指针，所以跳表中的节点，定义如下 。
public class SkiplistNode {public int data;public SkiplistNode next;public SkiplistNode down;public int level;public SkiplistNode(int data, int level) {this.data = https://www.isolves.com/it/sjk/Redis/2023-03-02/data;this.level = level;}上述是跳表中的节点的最简单的定义方式，存储的元素 data 为整数，节点之间进行比较时直接比较元素 data 的大小 。
三. 跳表的初始化跳表初始化时，将每一层链表的头尾节点创建出来并使用集合将头尾节点进行存储，头尾节点的层数随机指定，且头尾节点的层数就代表当前跳表的层数 。初始化后，跳表结构如下所示 。
深入理解跳表及其在Redis中的应用

文章插图
??跳表初始化的相关代码如下所示 。
public LinkedList<SkiplistNode> headNodes;public LinkedList<SkiplistNode> tailNodes;public int curLevel;public Random random;public Skiplist() {random = new Random();//headNodes用于存储每一层的头节点headNodes = new LinkedList<>();//tailNodes用于存储每一层的尾节点tailNodes = new LinkedList<>();//初始化跳表时，跳表的层数随机指定curLevel = getRandomLevel();//指定了跳表的初始的随机层数后，就需要将每一层的头节点和尾节点创建出来并构建好关系SkiplistNode head = new SkiplistNode(Integer.MIN_VALUE, 0);SkiplistNode tail = new SkiplistNode(Integer.MAX_VALUE, 0);for (int i = 0; i <= curLevel; i++) {head.next = tail;headNodes.addFirst(head);tailNodes.addFirst(tail);SkiplistNode headNew = new SkiplistNode(Integer.MIN_VALUE, head.level + 1);SkiplistNode tailNew = new SkiplistNode(Integer.MAX_VALUE, tail.level + 1);headNew.down = head;tailNew.down = tail;head = headNew;tail = tailNew;}}


推荐阅读


上一篇：没有了

下一篇：数据结构与算法：冒泡排序