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

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

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

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

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

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

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

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

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

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

老师，跳表的索引使用数组是不是就不用建立多级索引了？