欢迎关注公众号《后台开发探索之旅》。
有序集合
日常开发经常需要对数据进行排序，针对不同的场景，采用特定的排序方法，比如：
（1）数组排序：将数值存入数组中，对数组进行冒泡、快排等排序方法，得到一个有序数组
（2）二叉搜索：构造二叉平衡树，从根结点开始向左向右搜索，每次查找规模减半，最终找到目标节点
（3）最小根堆：同样将数值存入数组中，对数组进行堆排序，保持最小值始终在堆顶，从而得到最小值
（4）有序链表：将数值存入链表中，保持链表有序，类似于数组
每一类数据结构都有其适合的场景，存在一些缺点，如下：
（1）数组排序：更新复杂度高，若插入首结点，后面所有元素都需要后移一位
（2）二叉搜索：只适合查找和更新，不能获取排序列表
（3）最小根堆：只适合获取最小值
（4）有序链表：查找复杂度高，每次都需要从头遍历
理想的有序集合是：
（1）查找、插入、删除的复杂度都小于O(N)，即不需要遍历所有结点
（2）可以获取排序列表，以及某个结点的排名
（3）可以根据数值查找排名，也可以根据排名查找数值
跳表（skiplist）就可以满足这些苛刻的要求，付出的代价是增加一倍的空间消耗，典型的空间换时间。
跳表原理
跳表实际上是在有序链表的基础上实现的，比如有数值1~10，用有序链表表示就是：
1,2,3,4,5,6,7,8,9,10
有序链表的缺点是每次都要从头遍历，比如查找9，要从1开始查找，那么能不能跳着查找，比如1,3,5,7,9这种方式呢，增加1层链表：
1,3,5,7,10
1,2,3,4,5,6,7,8,9,10
先从第2层开始查找，顺序为1,3,5,7，后面是10，不能继续向右了，进入下一层，从7接着向右，找到8,9
如果数据量特别大，有几百万条数据，还是很慢，能不能再快点，可以的，增加层数到20层，每次从20层开始，本层查找完毕，进入下一层继续查找。
当跳表设置为25层时，无论数据量有多大，查找次数稳定在50次以内，性能非常优秀。
redis的跳表实现
redis基于自身功能需求，扩展了跳表的功能。每个元素有name和score两个属性，name是元素唯一标识符，根据score排序。支持以下操作：
（1）插入name和score，name不能相同，score可以相同； 先根据score排序，若score相同，根据name排序
（2）根据name，删除元素，获取元素score，获取元素rank排名
（3）获取指定score区间的元素排序列表； 比如传入1和5，返回1,2,3,4,5
（4）获取指定rank区间的元素排序列表； 比如获取前10名的元素列表
golang实现
考虑到redis跳表的强大，用golang实现了其功能，项目地址为：
https://github.com/throne-developer/skiplist
测试代码：
func TestSkipListSimple(t *testing.T) {
sl := New()
sl.Insert("A", 1)
sl.Insert("B", 2)
sl.Insert("C", 3)
sl.Insert("D1", 6)
sl.Insert("D2", 6)
sl.Insert("D3", 6)
if elem := sl.Find("D1"); elem != nil {
fmt.Println("Find D1, score=", elem.Score())
}
if rank, ok := sl.GetRank("D1"); ok {
fmt.Println("D1 rank is ", rank)
}
if score, ok := sl.GetScore("D1"); ok {
fmt.Println("D1 score is ", score)
}
if elem := sl.FindByRank(5); elem != nil {
fmt.Println("FindByRank 5, name=", elem.Name())
}
for elem := sl.FindGreaterOrEqual(3); elem != nil; elem = elem.Next() {
fmt.Println("FindGreaterOrEqual 3, name=", elem.Name())
}
sl.Delete("A")
}在此接口基础上做简单的封装，即可实现redis的zset命令，下一篇将介绍golang版本的skiplist内部实现机制。