Redis学习笔记：跳跃表
概述
跳跃表（skiplist）是一种有序数据结构。相比于普通的链表访问元素需要一步一步的向后查找，它通过在每个节点中维持多个指向其他节点的指针，从而达到快速访问节点的目的。跳跃表支持平均O(logN)、最坏O(N)复杂度的节点查找。Redis使用跳跃表作为有序集合键的底层实现之一。
实现
下图是跳跃表结构的模型：
查找值51的节点的过程：
- 从第2层开始，1比51小，向后比较。
- 21比51小，继续向后比较。第2层21节点的next指针指向NULL，所以从21节点开始需要下降一层到第1层继续向后比较。
- 第1层中，21节点的next节点为41节点，41比51小，继续向后比较，61比51大，所以从41节点开始降一层到第0层继续向后比较。
- 在第0层，51节点为要查询的节点，节点被找到。
使用跳跃表总共查找4次就可以找到51节点，额链表需要6次，当数据量大时，优势会更明显。
Redis跳跃表的实现
基于基础的跳跃表算法，Redis实现的跳跃表略微复杂些，不仅有向前查找的各层指针，还有向后的指针用于倒序遍历，还记录跳跃表的节点数和最高层数，但是原理都是一样的。如图展示了一个跳跃表，该结构包含以下属性：
- header：指向跳跃表的表头节点。
- tail：指向跳跃表的表尾节点。
- level：记录目前跳跃表内，层数最大的那个节点的层数（表头节点的层数不计算在内）。
- length：记录跳跃表的长度，也即是，跳跃表目前包含节点的数量（表头节点不计算在内）。
- ele：用于存储字符串类型的数据。
- score：用于存储排序的分值。
- backward：后退指针，只能指向当前节点最底层的前一个节点，从后向前遍历跳跃表时使用。
- level：为柔性数组。每个节点的数组长度不一样，在生成跳跃表节点时，随机生成一个1～64的值，值越大出现的概率越低。
参考
《Redis设计与实现》
《Redis5设计与源码分析》