对于一个单链表来讲，即便链表中存储的数据是有序的，如果我们要想在其中查找某个数据，也只能从头到尾遍历链表。这样查找效率就会很低，时间复杂度会很高，是 O(n)。
比如下图的链表，我们想要查找9需要比较9次，查找路径是红色箭头
想要提高效率就有一个非常简单的办法，加索引，如下图，加一层的话比较次数就减小到了5次
再加一层，比较次数就直接减少了三次
再加一层，甚至可以减少到两次的比较次数
这种链表加多级索引的结构就是跳表，他的显著优势就是可以提高查询效率，那么我们分析一下，他究竟可以有多快。先来看这样一个问题，如果链表里有 n 个结点，会有多少级索引呢？
如果每两个结点会抽出一个结点作为上一级索引的结点，那第一级索引的结点个数大约就是 n/2，第二级索引的结点个数大约就是 n/4，第三级索引的结点个数大约就是 n/8，依次类推，也就是说，第 k 级索引的结点个数是第 k-1 级索引的结点个数的 1/2，那第 k级索引结点的个数就是 n / ( 2 k ) n/(2^k) n/(2k)。
假设索引有 h 级，*的索引有 2 个结点。通过上面的公式，我们可以得到 n / ( 2 h ) = 2 n/(2^h)=2 n/(2h)=2，从而求得 h = log 2 n − 1 h=\log _{2}{n-1} h=log2n−1。如果包含原始链表这一层，整个跳表的高度就是 log 2 n \log_{2}{n} log2n。我们在跳表中查询某个数据的时候，如果每一层都要遍历 m 个结点，那在跳表中查询一个数据的时间复杂度就是 O(m*logn)。
这几级索引的结点总和就是 n/2+n/4+n/8…+8+4+2=n-2。所以，跳表的空间复杂度是 O(n)。也就是说，如果将包含 n 个结点的单链表构造成跳表，我们需要额外再用接近 n 个结点的存储空间。那我们有没有办法降低索引占用的内存空间呢？其实也有，现在我们大概是每两个节点抽一个索引，还可以每三个节点抽一个。这样的话就可以显著降低空间复杂度，但是会提高时间复杂度，看实际项目如何平衡。
跳表是一种典型的空间换时间的解决方案。