17 | 跳表：为什么Redis一定要用跳表来实现有序集合？

精选留言(170)

• 

  张先生

  为什么评论区的都这么优秀，为什么我这么菜，我该怎么办😱

  2018-11-26

   11

   246
• 

  leo

  跳表是我非常喜欢的数据结构，之前写过一篇文章，希望大家斧正（https://cloud.tencent.com/developer/article/1353762）。另外，严格来讲，Redis的对象系统中的每种对象实际上都是基于使用场景选择多种底层数据结构实现的，比如ZSET就是基于【压缩列表】或者【跳跃表+字典】（这也跟之前排序中提到的Sort包实现的思想一样，基于数据规模选择合适的排序算法），体现了Redis对于性能极致的追求。

  作者回复: 👍

  2018-10-29

   1

   141
• 

  Liam

  看了下老师github上的实现(java版本)，不是很理解，尤其是数组Node forward[]的作用，能多加些注释或讲解一下吗

  2018-10-29

   1

   78
• 

  董航

  redis有序集合是跳跃表实现的，直接这么说有失偏驳，他是复合数据结构，准确说应该是由一个双hashmap构成的字典和跳跃表实现的，不知道我说的有问题吗😊

  作者回复: 后面还会讲 你说的没错 👍

  2018-10-29

   1

   48
• 

  escray

  如果每三个或者五个节点提取一个节点作为上级索引，那么对应的查询数据时间复杂度，应该也还是 O(logn)。
  
  假设每 5 个节点提取，那么最高一层有 5 个节点，而跳表高度为 log5n，每层最多需要查找 5 个节点，即 O(mlogn) 中的 m = 5，最终，时间复杂度为 O(logn)。
  
  空间复杂度也还是 O(logn)，虽然省去了一部分索引节点，但是似乎意义不大。
  
  不知道在一般的生产系统，跳表的提取是按照多少个节点来实现？还是每个系统根据实际情况，都不一样。
  
  看了跳表的 Java 实现，查找部分的代码真是漂亮，插入部分看了半天才看明白。

  作者回复: 👍

  2018-10-29

   2

   42
• 

  姜威

  总结：
  一、什么是跳表？
  为一个值有序的链表建立多级索引，比如每2个节点提取一个节点到上一级，我们把抽出来的那一级叫做索引或索引层。如下图所示，其中down表示down指针，指向下一级节点。以此类推，对于节点数为n的链表，大约可以建立log2n-1级索引。像这种为链表建立多级索引的数据结构就称为跳表。
  二、跳表的时间复杂度？
  1.计算跳表的高度
  如果链表有n个节点，每2个节点抽取抽出一个节点作为上一级索引的节点，那第1级索引的节点个数大约是n/2，第2级索引的节点个数大约是n/4，依次类推，第k级索引的节点个数就是n/(2^k)。假设索引有h级别，最高级的索引有2个节点，则有n/(2^h)=2，得出h=log2n-1，包含原始链表这一层，整个跳表的高度就是log2n。
  2.计算跳表的时间复杂度
  假设我们在跳表中查询某个数据的时候，如果每一层都遍历m个节点，那在跳表中查询一个数据的时间复杂度就是O(m*logn)。那这个m是多少呢？如下图所示，假设我们要查找的数据是x，在第k级索引中，我们遍历到y节点之后，发现x大于y，小于后面的节点z，所以我们通过y的down指针，从第k级下降到第k-1级索引。在第k-1级索引中，y和z之间只有3个节点（包含y和z），所以，我们在k-1级索引中最多只需要遍历3个节点，以此类推，每一级索引都最多只需要遍历3个节点。所以m=3。因此在跳表中查询某个数据的时间复杂度就是O(logn)。
  三、跳表的空间复杂度及如何优化？
  1.计算索引的节点总数
  如果链表有n个节点，每2个节点抽取抽出一个节点作为上一级索引的节点，那每一级索引的节点数分别为：n/2，n/4，n/8，…，8，4，2，等比数列求和n-1，所以跳表的空间复杂度为O(n)。
  2.如何优化时间复杂度
  如果链表有n个节点，每3或5个节点抽取抽出一个节点作为上一级索引的节点，那每一级索引的节点数分别为（以3为例）：n/3，n/9，n/27，…，27，9，3，1，等比数列求和n/2，所以跳表的空间复杂度为O(n)，和每2个节点抽取一次相比，时间复杂度要低不少呢。
  四、高效的动态插入和删除？
  跳表本质上就是链表，所以仅插作，插入和删除操时间复杂度就为O(1)，但在实际情况中，要插入或删除某个节点，需要先查找到指定位置，而这个查找操作比较费时，但在跳表中这个查找操作的时间复杂度是O(logn)，所以，跳表的插入和删除操作的是时间复杂度也是O(logn)。
  五、跳表索引动态更新？
  当往跳表中插入数据的时候，可以选择同时将这个数据插入到部分索引层中，那么如何选择这个索引层呢？可以通过随机函数来决定将这个节点插入到哪几级索引中，比如随机函数生成了值K，那就可以把这个节点添加到第1级到第K级索引中。

  2018-10-31

   1

   31
• 

  小情绪

  王老师：跳表的思想讲的非常好，但是我总觉得应该把跳表的具体实现讲一下吧，毕竟来这里的大部分算法能力不是很强，而跳表的实现还是有一定难度的。

  2018-11-29

  

   25
• 

  德尼

  看评论很多人说对github的代码不理解，我来说下自己的理解吧。整个代码的实现思想就是老师说的那样。每个节点的forward里存的是当前节点的所有索引层的下一跳，forward[ 0 ]对应的是原链表里的下一跳，forward[ 1 ]是最后一层节点的下一跳位置，以此类推，也就是说访问head的forward[ levelCount-1 ]表示第一层索引的头结点。head是一个头结点，它的forward里存的是原链表以及索引层的头结点。

  2018-12-09

  

   20
• 

  MG

  王老师的Java实现版本，有几个关键点理解到了，基本上就明白是怎么实现的了：
  1.每次插入数据的时候随机产生的level:决定了新节点的层数；
  2.数组update的作用：用以存储新节点所有层数上，各自的前一个节点的信息；
  3.节点内的forwards数组：用以存储该节点所有层的下一个节点的信息；
  4.当所有节点的最大层级变量maxlevel=1的时候，跳表退化成一个普通链表

  2018-12-25

  

   17
• 

  k

  看了下留言 好像有人对等比数列求和有想法 老师的n-2并不是估算解 是精确解
  n/2, n/4, .., 2 这个数列中一共有log2(n/2)项
  套进等比数列求和公式
  S = a0(1-q^n)/(1-q), 其中a0表示首项，n表示项数
  这里的a0=n/2, 项数=log2(n/2), q=1/2
  S = n/2(1-2/n)/(1-1/2) = n-2

  2018-11-20

   1

   10
• 

  許敲敲

  我是机械行业打算换行的，不知道应该怎么把这些知识掌握的扎实一点，今天课里面的红黑树不了解.

  作者回复: 后面会讲 不急

  2018-10-29

   1

   8
• 

  安南寸暖🤕

  talk is cheap, show your code

  2019-01-30

  

   5
• 

  CathyLin

  思考题：
  每 3 个结点提取一个结点作为上级索引，时间复杂度是 4log3N ，用大 O 表示法为 O(logn)
  同理，每 5 个结点提取一个结点作为上级索引的时间复杂度是 6log5N，用大 O 表示法为 O(logn)。
  
  github 上的代码看的有点没太看懂，还得慢慢啃，加油💪

  2018-12-30

  

   5
• 

  Smallfly

  老师想问下文章中出现的等比数列求和怎么算的，因为整数除法是取整的，所以公式好像不好使……，用数据代入老师的公式又是正确的，希望能指点一下。

  作者回复: 整数除法是取取整的是什么意思啊

  2018-10-29

   1

   5
• 

  Uper

  仍然是logn 不过底数是间隔结点个数

  2018-10-29

  

   5
• 

  长期规划

  感觉跳表跟B+树有些像，父节点会出现在子节点中，而且B+的叶节点也是链接起来的。不同的是跳表每个结点只有一个子结点，而且除叶结点相连外，每层内都相连。从结构上来，很像树的变种，层内相连。老师，跳表是受树的启发两来的吗？

  作者回复: 有可能是的。

  2019-07-25

  

   4
• 

  kakasi

  感觉github上的实现好难理解，希望老师有时间能解释下。
  我有一个思路：定义两个数据结构，一个是普通的单链表Node，一个索引类Index。索引类中两个域：单链表节点Node， 下一个Index引用。用Index数组表示1 - level索引层。
  这样数据结构里就不会出现数组了，不知这样的思路是否正确。

  作者回复: 你的方法也可以 我的实现思路比较有技巧 是不容易看懂 建议不要纠结实现了

  2018-11-12

  

   4
• 

  andavid

  关于 GitHub 上跳表的 Java 代码实现，本人仔细研读后，按自己的理解加上了注释，并写了一个测试程序打印跳表每一层的结点，以及每个结点在各层的下一跳结点。希望对大家理解跳表有所帮助。如果理解有不恰当的地方，还请指正，多谢~
  
  https://github.com/andavid/ds-algo-java/blob/master/src/main/java/com/github/andavid/ds/datastructure/skiplist/SkipList.java
  
  https://github.com/andavid/ds-algo-java/blob/master/src/test/java/com/github/andavid/ds/datastructure/skiplist/SkipListTest.java
  
  

  2019-08-17

   2

   3
• 

  刘涛涛

  github上的代码，我理解的p=p.forwars[i]代表第i层的下一结点，不知道对不对

  作者回复: 对的！👍

  2019-02-17

   1

   3
• 

  Pluto

  学到了，这个厉害了，不过实现还是没有看的太懂

  作者回复: 实现确实不好看懂 我也看了很久

  2018-11-05

  

   3