跳表，一种简单的搜索数据结构

跳表是用来快速搜索的数据结构，在大部分情况下可以和平衡树效率相近。他是基于有序双向链表的查找。可以认为是一种兼顾了有序数组快速搜索和链表的随意高效插入两种特性的数据结构。特别是在实现排行榜业务时，基本就是使用他了。而且广为人知的Redis的zset也是跳表的实现。

数据结构概览

可以看到每个节点有backward指针指向后置节点。Redis中排序是从小到大的。也就是指向比当前节点小的下一个节点。

当前节点指向前进方向（变大）节点的指针是有多个的。这也是实现跳进访问，提高有效搜索的关键。在Redis中还有span成员也重要，用来计算搜索到当前节点经过的节点数量，对应的也就是业务中的排名。如果仅用来搜索是不用维护span这个数值的。

Redis实现概览

出自Redis设计与实现

实现关键

1. 链表的Header其实是一个伪节点，他从初始化就包含了最大的层数。在Redis下是32层。
2. 其他节点的层数是动态的根据幂次定律生成的（掷色子）。
3. 查找是从左边顶层往下搜索,遇到小的就进行一次跳跃。否则继续往下层找。直到找到或者到了最小层也无法找到。