golang实现跳表(SkipList)

跳表的理解

如果要维护一组有序的整数序列，支持高效的插入删除和搜索，并且能维护序列的有序性。可以选择的数据结构是有限的，哈希表虽然支持常数时间复杂度的增删查，但是hashmap不能维护有序性。红黑树可以维持有序性，并且增加删除修改的性能也很好，但是红黑树不能支持范围搜索。跳表这种数据结构利用空间换时间，性能和红黑树比肩，还能支持区间搜索，在redis和leveldb等开源项目中都用被应用。

跳表的结构如图所示：

在最底层包含了所有的数据节点，每一层链表都有一个指向下一层和自己相同的节点，向后的指针指向随机的同一层比自己大的数据。

时间复杂度分析

不难理解，对于一个有n个节点的链表，如果每两个节点会提取出一个节点作为索引节点，那么第一层的节点个数为n/2，再往上一层，节点数变成n/4，以此类推，第k层的索引个数为n/(2^k)，假设层数有x层，并且第x层的节点个数为2，也就是n/(2^x) = 2，所以x = (logn - 1)，而第0层是链表本身，所以整个跳表的高度就是logn，如果每一层都需要遍历m个节点，那么在跳表中查询某个数的时间复杂度就是O(m * log(n))。

简单的单向跳表实现: skiplist