共计 1122 个字符，预计需要花费 3 分钟才能阅读完成。
跳跃表（SkipList）是一种能高效实现插入、删除、查找的内存数据结构，这些操作的冀望复杂度都是 O(logN)。与红黑树以及其余的二分查找树相比，跳跃表的劣势在于实现简略，而且在并发场景下加锁粒度更小，从而能够实现更高的并发性。正因为这些长处，跳跃表宽泛应用于 KV 数据库中，诸如 Redis、LevelDB、HBase 都把跳跃表作为一种保护有序数据汇合的根底数据结构。
家喻户晓，链表这种数据结构的查问复杂度为 O(N)，这里 N 是链表中元素的个数。在曾经找到要删除元素的状况下，再执行链表的删除操作其实十分高效，只需把待删除元素前一个元素的 next 指针指向待删除元素的后一个元素即可，复杂度为 O(1)，如图所示
但问题是，链表的查问复杂度太高，因为链表在查问的时候，须要一一元素地查找。如果链表在查找的时候，可能防止顺次查找元素，那么查找复杂度将升高。而跳跃表就是利用这一思维，在链表之上额定存储了一些节点的索引信息，达到防止顺次查找元素的目标，从而将查问复杂度优化为 O(logN)。将查问复杂度优化之后，天然也优化了插入和删除的复杂度。
1. 定义
跳跃表的定义如下：
•跳跃表由多条分层的链表组成（设为 S0, S1, S2, … , Sn），例如图中有 6 条链表。
•每条链表中的元素都是有序的。
•每条链表都有两个元素：+∞（正无穷大）和 - ∞（负无穷大），别离示意链表的头部和尾部。
•从上到下，下层链表元素汇合是上层链表元素汇合的子集，即 S1 是 S0 的子集，S2 是 S1 的子集。
•跳跃表的高度定义为程度链表的层数。
2. 查找
在跳跃表中查找一个指定元素的流程比较简单。如图所示，以左上角元素（设为 currentNode）作为终点查找元素 5：
•如果发现 currentNode 后继节点的值小于等于待查问值，则沿着这条链表向后查问，否则，切换到以后节点的下一层链表。
•持续查问，直到找到待查问值为止（或者 currentNode 为空节点）为止。
3. 插入
跳跃表的插入算法要简单一点。如图所示。首先，须要依照上述查找流程找到待插入元素的前驱和后继；而后，依照如下随机算法生成一个高度值：
(图在跳跃表插入元素 48)
最初，将待插入节点依照高度值生成一个垂直节点（这个节点的层数正好等于高度值），之后插入到跳跃表的多条链表中去。假如 height=randomHeight(p)，这里须要分两种状况探讨：
•如果 height 大于跳跃表的高度，那么跳跃表的高度被晋升为 height，同时须要更新头部节点和尾部节点的指针指向。
•如果 height 小于等于跳跃表的高度，那么须要更新待插入元素前驱和后继的指针指向。
跳跃表的查找、删除、插入的复杂度都是 O(logN)。
文章基于《HBase 原理与实际》一书
