数据结构之 SkipList

algorithm

上一篇中简单介绍了跳跃表的基本结构和构建思想，本篇接着来看看 skiplist 到底是如何构建的以及具体是怎么进行操作的。

构造

上一篇中提到过， skiplist 是一种随机化数据结构，并且这种结构的查找效率可比拟那些自平衡二叉查找树结构，那么它的特点在哪里呢。

我们知道想经典的AVL树、红黑树等平衡二叉查找树拥有极高的查询效率但是相对的，当其节点发生变化时，会有一系列的操作（比如红黑树的左右旋）来使树重新变得左右平衡。而 skiplist 的一切都建立在随机的基础上，跳跃列表是对有序的链表增加上附加的前进链接，增加是以随机化的方式进行的。所有操作都以对数随机化的时间进行。

其构造过程：
1. 首先我们有一个有序的链表
2. 然后按一定的随机算法选出一些元素，将这些元素顺序相连生成新的一层
3. 新的层级元素完善指针，这个指针指向下一层中值同自己相等的元素。Top指针指向该层首元素
4. 重复上两步

插入元素的过程也依靠随机算法完成，首先先查找到待插入位置，然后随机的产生一个层数，然后一层一层的插入插入时算法和普通链表的插入完全相同。

查找

如图，如果要查找一个元素 7 ， 那么其步骤就是：
1. 首先由最高层找到5，比较发现大于5
2. 沿向后的指针向后，发现到达末尾，降低层数
3. 沿指针向后比较找到元素7，结束

如果要查找元素2 ：
1. 首先由最高层找到5，比较发现小于5
2. 降低层数，找到1，比较发现大于1
3. 向后找到5，比较发现小于5
4. 降低层数，向后找到3，比较发现小于3
5. 降低层数，找到2

Redis Base

在功能上的需要，Redis 对 skiplist 做了相应的定制化
1. 允许重复的 score 值：多个不同的 member 的 score 值可以相同。
2. 进行对比操作时，不仅要检查 score 值，还要检查 member，单靠 score 值无法判断一个元素的身份
3. 每个节点都带有一个高度为 1 层的后退指针，用于从表尾方向向表头方向迭代（以便于对 ZREV* 类的命令更好的支持）

跳跃表目前在 Redis 的唯一作用，就是作为有序集类型的底层数据结构之一（另一个构成有序集的结构是字典）。