17 | 跳表：为什么Redis一定要用跳表来实现有序集合？
2018-10-29 王争
《数据结构与算法之美》
课程介绍
讲述：冯永吉
时长:大小15.34M
上两节我们讲了二分查找算法。当时我讲到，因为二分查找底层依赖的是数组随机访问的特性，所以只能用数组来实现。如果数据存储在链表中，就真的没法用二分查找算法了吗？
实际上，我们只需要对链表稍加改造，就可以支持类似“二分”的查找算法。我们把改造之后的数据结构叫做跳表（Skip list），也就是今天要讲的内容。
跳表这种数据结构对你来说，可能会比较陌生，因为一般的数据结构和算法书籍里都不怎么会讲。但是它确实是一种各方面性能都比较优秀的动态数据结构，可以支持快速地插入、删除、查找操作，写起来也不复杂，甚至可以替代红黑树（Red-black tree）。
Redis 中的有序集合（Sorted Set）就是用跳表来实现的。如果你有一定基础，应该知道红黑树也可以实现快速地插入、删除和查找操作。
© 版权归极客邦科技所有，未经许可不得传播售卖。 页面已增加防盗追踪，如有侵权极客邦将依法追究其法律责任。
精选留言
张先生2018-11-26为什么评论区的都这么优秀，为什么我这么菜，我该怎么办😱共 99+ 条评论903- leo2018-10-29跳表是我非常喜欢的数据结构，之前写过一篇文章，希望大家斧正（https://cloud.tencent.com/developer/article/1353762）。另外，严格来讲，Redis的对象系统中的每种对象实际上都是基于使用场景选择多种底层数据结构实现的，比如ZSET就是基于【压缩列表】或者【跳跃表+字典】（这也跟之前排序中提到的Sort包实现的思想一样，基于数据规模选择合适的排序算法），体现了Redis对于性能极致的追求。
作者回复: 👍
共 9 条评论294 
escray
2018-10-29如果每三个或者五个节点提取一个节点作为上级索引，那么对应的查询数据时间复杂度，应该也还是 O(logn)。 假设每 5 个节点提取，那么最高一层有 5 个节点，而跳表高度为 log5n，每层最多需要查找 5 个节点，即 O(mlogn) 中的 m = 5，最终，时间复杂度为 O(logn)。 空间复杂度也还是 O(logn)，虽然省去了一部分索引节点，但是似乎意义不大。 不知道在一般的生产系统，跳表的提取是按照多少个节点来实现？还是每个系统根据实际情况，都不一样。 看了跳表的 Java 实现，查找部分的代码真是漂亮，插入部分看了半天才看明白。展开作者回复: 👍
共 9 条评论129
Liam2018-10-29看了下老师github上的实现(java版本)，不是很理解，尤其是数组Node forward[]的作用，能多加些注释或讲解一下吗共 13 条评论103
董航2018-10-29redis有序集合是跳跃表实现的，直接这么说有失偏驳，他是复合数据结构，准确说应该是由一个双hashmap构成的字典和跳跃表实现的，不知道我说的有问题吗😊作者回复: 后面还会讲 你说的没错 👍
共 2 条评论101
姜威2018-10-31总结： 一、什么是跳表？ 为一个值有序的链表建立多级索引，比如每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级索引中。展开共 3 条评论78
Robert2020-02-17从2月10号开始，连续每天学习已经1个礼拜了，希望自己能够继续坚持下去。刚好这段时间待在家里，可以有比较多的时间来补充知识。虽然非计算机专业出身，但是也从事技术工作10余年，大部分时间都是做ERP相关的开发，写代码也都是以业务代码或者数据库方面的居多。曾经自己也自学过一点数据结构和算法，但是都收效甚微。短短一个礼拜的学习，已经感觉收获很大。 随着年龄的增长，也越来越有危机感，趁着这次疫情的机会，重新进行思考和学习。每次想要放弃技术的时候，想想龟叔，Linus，Ken Thompson 这些大神，在60岁甚至70岁的时候都还在从事技术相关的研究，顿时就觉得年轻了，赶紧继续钻研学习。共 3 条评论54
小情绪2018-11-29王老师：跳表的思想讲的非常好，但是我总觉得应该把跳表的具体实现讲一下吧，毕竟来这里的大部分算法能力不是很强，而跳表的实现还是有一定难度的。共 3 条评论49- 德尼2018-12-09看评论很多人说对github的代码不理解，我来说下自己的理解吧。整个代码的实现思想就是老师说的那样。每个节点的forward里存的是当前节点的所有索引层的下一跳，forward[ 0 ]对应的是原链表里的下一跳，forward[ 1 ]是最后一层节点的下一跳位置，以此类推，也就是说访问head的forward[ levelCount-1 ]表示第一层索引的头结点。head是一个头结点，它的forward里存的是原链表以及索引层的头结点。32
MG2018-12-25王老师的Java实现版本，有几个关键点理解到了，基本上就明白是怎么实现的了： 1.每次插入数据的时候随机产生的level:决定了新节点的层数； 2.数组update的作用：用以存储新节点所有层数上，各自的前一个节点的信息； 3.节点内的forwards数组：用以存储该节点所有层的下一个节点的信息； 4.当所有节点的最大层级变量maxlevel=1的时候，跳表退化成一个普通链表31- Swing2019-12-04em，看完这一节，去看了下老师github的java实现，看+整理用了两个多小时。。 代码实现那里，有几个关键的变量的声明，感觉不是很精确，比如： “update 更名为 preNodes ，即 待插新节点在每一层的pre 结点数组； forwards 更名为 nextNodes，即 当前节点在每一层的next节点数组” 个人认为这样的话，大家就容易理解了 。。。。。。。。。。展开共 6 条评论29
andavid2019-08-17关于 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展开共 3 条评论18
长期规划2019-07-25感觉跳表跟B+树有些像，父节点会出现在子节点中，而且B+的叶节点也是链接起来的。不同的是跳表每个结点只有一个子结点，而且除叶结点相连外，每层内都相连。从结构上来，很像树的变种，层内相连。老师，跳表是受树的启发两来的吗？作者回复: 有可能是的。
共 3 条评论17
k2018-11-20看了下留言 好像有人对等比数列求和有想法 老师的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展开共 6 条评论16
許敲敲2018-10-29我是机械行业打算换行的，不知道应该怎么把这些知识掌握的扎实一点，今天课里面的红黑树不了解.作者回复: 后面会讲 不急
共 2 条评论12
安南寸暖🤕2019-01-30talk is cheap, show your code共 1 条评论10
Uper2018-10-29仍然是logn 不过底数是间隔结点个数9
刘涛涛2019-02-17github上的代码，我理解的p=p.forwars[i]代表第i层的下一结点，不知道对不对作者回复: 对的！👍
共 2 条评论7
CathyLin2018-12-30思考题： 每 3 个结点提取一个结点作为上级索引，时间复杂度是 4log3N ，用大 O 表示法为 O(logn) 同理，每 5 个结点提取一个结点作为上级索引的时间复杂度是 6log5N，用大 O 表示法为 O(logn)。 github 上的代码看的有点没太看懂，还得慢慢啃，加油💪共 1 条评论7
Pluto2018-11-05学到了，这个厉害了，不过实现还是没有看的太懂作者回复: 实现确实不好看懂 我也看了很久
7