关于 Redis 有序集合底层数据结构跳跃表的疑惑

[qianProgrammer]

跳跃表由 zskiplistNode 和 zskiplist 两个结构定义.
其中 zskiplistNode 表示跳跃表的各个节点,节点下有 zskiplistLevel 记录每个节点的各个层.
层中有两个字段,一个是前进指针,一个是本帖主题‘跨度’.
按《 Redis 设计与实现》书中所写,层的跨度用于记录两个节点之间的距离,实际作用是用来计算节点的排位,在查找某个节点的过程中,将沿途访问过的所有层的跨度累计起来,得到的结果就是目标节点在跳跃表中的排位.
跳跃表按我的理解就是一个维护了多层索引的链表,那么可以通过维护一个下标索引直接计算节点间的距离,也可以直接使用下标索引得到当前节点的排位,那么每个节点的各个层都维护一个跨度的意义在哪里呢…?添加删除的时候更加麻烦,还占用了更多的内存空间.

[wakzz]

因为跳跃表是按值排序的，多层索引为了快速跳跃查询指定值，不用一个一个遍历一遍，时间复杂度从 O(N) -> O(log N)。

[xkeyideal]

如果采用下标索引的方式，那么请问增删节点的时候，如何快速的维护所有节点下标索引的准确性呢

[qianProgrammer]

@xkeyideal 增删节点的时候,一样需要维护相关节点每一层的跨度啊;
比如说 A,B,C,D,F 5 个节点,如果删除了 D 节点,那么需要对 A,B,C 三个节点中有指向 F 的层进行更新
由于节点中记录的后退指针是指向上一个节点的,无法直接定位到需要更新的节点,那么需要更新就一定要进行遍历
既然横竖都是要遍历更新,只在每个节点中维护一个下标索引不是更简单一些吗?

[qianProgrammer]

@wakzz 这个我明白,但是这个跨度的作用我确实有点想不通_(:з」∠)_

[xkeyideal]

@qianProgrammer 你分析一下二者的时间复杂度吧，redis 的 span 维护的时间复杂度是 O(k)，k 是该层级的高度

[LittleDust]

举个例子：
1. 字母 a-z 里面你要查找 i，按遍历你要从 a 开始找，一直找到 i，要找 9 次；
2. 按跳跃表思想，将 a-z 分为两层，第一层还是 a-z，一共 26 个点，第二层 a 、h 、o 、z 四个点，分为 a-g, h-n, o-z 三个区间，这时候你再去找 h，先从最顶层，也就是这里的第二层开始找，四个点依次比对 a < i，h < i，o > i 判断 3 次；得到 i 在 h-o 之间，接着到 h 、o 两点对应的第一层，查找 2 次，一共 5 次就找到了 i 。
3. 总结一下：就是用层来保存区间，从上到下，点数越多，区间越精确；

[rrfeng]

你想一下如果有索引那不就是个 array 吗？这里为啥不直接用 array 呢？