skiplist，又称作跳表，跳跃表。
最开始接触skiplist的时候是在看那本《数据结构与算法分析——C++语言实现》，这本书很好，但是看完的人并不多。在书中第一次看到skiplist数据结构的时候，感觉还挺复杂的。直到去年看redis实现的时候又看到了skiplist才发现这真的是一种很巧妙的数据结构。下面先看一下最简单的skiplist，然后介绍两种变体。
Basic Skiplist
Why Skiplist
首先看一下为什么需要skiplist这种数据结构？现在有这么一个应用场景，我们需要持续有序地存储一些数据，并且满足下面的需要：1.查找；2.插入。这两个是最具有代表性的操作，为什么这么说呢？如果需要查找的效率尽量高，那么就应该使用线性存储（比如数组，查找复杂度O(1) ）；而频繁插入则应该使用链式存储（比如链表，插入复杂度O(1) ）。如果要把这两种结合起来的话，一种还不错的选择是二叉查找树（BST）。但是树本身有很多问题，比如如何保持平衡，如何动态调整。这个时候skiplist就出现了。简单来说，skiplist是一种可以满足树的大多数应用场景，同时又比树这种结构实现简单的数据结构。那么skiplist到底是什么样的呢？继续往下看。
原理
想要快速理解一个事情的原理的时候最简单的方法就是图示法（当然前提是图可以表示出来）。下图摘自维基百科。
如上图所示，skiplist底层数据存储使用的还是链表，这样我们就可以在每个节点定制化更多的信息。除了底层链表之外，上面还有几层，上面的每一层都比它的下一层节点要少，同时每一层的节点可以指定寻址到它的上一层（如果对应位置上一层也有节点的话）和下一层的对应的节点的。然后所有的层用一个指针数组来连接起来。下面看一下查找以及插入在skiplist中是怎么个样子。
首先是查找，先从最上面的一层开始。上图中第一层只有一个节点，但是我觉得更好一点是两个节点，不是一头一尾，而是一个头部节点和一个中间节点，假定为head, mid。将待查找的元素值于mid节点比较，如果小于mid节点值，则待查找节点一定在head和mid之间；大于mid节点则落在后半段区间。这样一次就去除了一半的元素。是不是似曾相似，对的，就是二分查找。整个查找的时间复杂度是O(lgn)。
插入。插入数据的时候我们先查找到底层数据节点需要插入的位置。然后像链表一样插入就可以了。这里还有一个问题，底层数据插入之后，上层链表的节点有时候也需要做一下改变。关于如何改变不同的skiplist实现往往都是不同的。下面的动图很好地演示了插入过程。其它像删除操作和插入操作很类似。
Segment Skiplist
虽然我这里叫Segment Skiplist，其实并没有这种算法，我只是觉得这么使用有点像Segment Tree而且没有想到其他的好名字，所以暂且这么叫吧。前面说过由于skiplist底层是链表节点，所以节点的数据可以实现定制化。现在有这么一个场景：和上面类似，在存储（当然也有修改）有序数据的基础上，我还需要查询两个数据中间有多少个数据。
首先底层肯定还是类似于上面的skiplist结构，这里的关键点是如何定制化节点的信息来实现区间查询。如果不添加数据，我们可以先查找到下限节点在底层链表（也就是存储了所有数据的链表）中的位置，然后在顺序往后查找。这个最坏的情况下，时间复杂度为O(n)。那么需要定制化什么信息呢？
在监控数据的时候，比如unix时间就是1970.1.1到当前的时间秒数，有时候我们存储的数据都是基于一个时间戳。这样查找的话只需要用上界数据减去下届数据就可以了。猛然一看，这个和我们上面的情景还是挺像的，但是仔细一想就发现完全不是那么一回事。以为我们上面还需要改动数据，而基于时间存储的数据一般是不会改动的。如果我们使用这种的话，改动一个数据，这个时间戳之后的数据往往都需要改动。那么怎么办呢？
上面的数据改动太多的本质原因是所有的数据都基于一个时间点，要想数据改动尽量小，我们就要使各个节点的数据依赖的部分尽可能的少。对于每一层，每个节点只存储上一个节点和当前节点之间的原始数据个数。举个栗子，上面第一幅图的第二层各个节点存储的额外数据从左到右分别为1，3，2。对于插入操作，则只需要找到插入数据所在的每一层链表区间，然后将区间的右边界存储数据加一；删除操作同理。
Cache-Friendly Skiplist
一个数据结构的好坏有一个很重要的指标是是否是Cache Friendly的？什么样的数据结构是Cache-Friendly的？简单来说就是连续存储。cache-friendly有什么用呢？我们知道cpu 有L1,L2 cache，在cpu与内存交互的时候会先去cpu cache里面取数据，如果取到了就是cache hit，否则就是miss。
skiplist本身是cache-unfriendly的，然后大概11年的时候写Linux内核的两个哥们Liu Bo和Chris Mason对skiplist做了friendly的改进，并做了benchmark测试。改进后的skiplist如下，并不打算细说了。感兴趣的可以参考cache-friendly skiplist