跳表 (Skip List) 是由 William Pugh 在 1990 年发表的文章 Skip Lists: A Probabilistic Alternative toBalanced Trees 中描述的一种查找数据结构，支持对数据的快速查找，插入和删除。
对于 AVL 树、红黑树等平衡树，在插入过程中需要做多次旋转操作，实现复杂，而跳表实现更简单、开销更低，应用广泛。
跳表是一个包含随机算法的数据结构。跳表的查找、插入、删除的平均时间复杂度都是 O(logn)，而且可以按照范围区间查找元素，空间复杂度是 O(n)
跳表的最底层通常是一个有序链表，上层是下层的一个索引，下层元素出现在上层的概率为 p (通常 p=1/2)。
首先，对于一个有序链表，如果我们需要查找元素，则需要从头开始遍历链表，查找时间复杂度为 O(n)。如果我们每相邻两个节点增加一个指针，让指针指向下下个节点，那么上层形成了一个减缩版的链表，当我查找元素时，先在上层链表查找，当待查元素在两个节点之间时，再回到下层链表查找，这样我们就可以跳过一些节点，提高查找速度。以此类推，我们可以在第二层链表上建立第三层链表……查找一个元素时，从最高层开始，逐层向下，直到找到为止。
上述我们建立的数据结构就是一个跳表，我们可以将上层链表看作是下层链表的一个索引，每相邻两个、三个……建立一个索引，这是一种确定性策略，如果只是查找操作，这么建立跳表没有问题。但是当我们需要频繁插入和删除元素时，这种确定性策略会使维护跳表变得复杂。