1 什么是跳表

1.1 概念

跳表【Skip list】全称为跳跃列表，是一种可以代替平衡树的数据结构，默认是按照Key值升序的。

Skip list让已排序的数据分布在多层链表中。它允许快速查询，插入和删除一个有序连续元素的数据链表。
跳表的平均查找和插入时间复杂度都是O(logn)。

快速查询是通过维护一个多层次的链表，且每一层链表中的元素是前一层链表元素的子集（见下面的示意图），上层链表相当于下层链表的索引

查找元素的过程是从最高级索引【最稀疏的层次】开始搜索，直至需要查找的元素在该层两个相邻的元素中间。这时，算法将跳转到下一个层次，重复刚才的搜索，直到找到需要查找的元素为止。

查找的时间复杂度 = 索引的高度 * 每层索引遍历元素的个数

跳表的索引高度：
假设每两个结点会抽出一个结点作为上一级索引的结点，原始的链表有n个元素，则一级索引有n/2 个元素、二级索引有 n/4 个元素、k级索引就有 n/(2^k)个元素。最高级索引一般有2个元素，即：最高级索引 h 满足 2 = n/2^h，即 h = log₂n - 1，最高级索引 h 为索引层的高度加上原始数据一层，跳表的总高度 h = log₂n。

跳表的空间复杂度
跳表通过建立索引，来提高查找元素的效率，是典型的“空间换时间”的思想，所以在空间上做了一些牺牲，那空间复杂度到底是多少呢？

假如原始链表包含 n 个元素，则一级索引元素个数为 n/2、二级索引元素个数为 n/4、三级索引元素个数为 n/8 以此类推。所以索引节点的总和是：n/2 n/4 n/8 … 8 4 2 = n-2，空间复杂度是 O(n)。

1.2 特性

• 跳表是可以实现二分查找的有序链表；
• 由很多层结构组成，每一层都是一个有序的链表， level是通过一定的概率随机产生的。
• 最底层(Level 1)的链表包含所有元素
• 如果一个元素出现在 Level i 的链表中，则它在 Level i 之下的链表也都会出现
• 每个索引节点包含两个指针，一个向下，一个向右；
• 跳表查询、插入、删除的时间复杂度为O(log n)，与平衡二叉树接近；

2 跳表的应用

2.1 在hbase中的应用

HBase MemStore 内部存储数据就使用的跳表。HBase 属于 LSM Tree 结构的数据库，LSM Tree 结构的数据库有个特点，实时写入的数据先写入到内存，内存达到阈值往磁盘 flush 的时候，会生成类似于 StoreFile 的有序文件，而跳表恰好就是天然有序的，所以在 flush 的时候效率很高，而且跳表查找、插入、删除性能都很高，这应该是 HBase MemStore 内部存储数据使用跳表的原因之一。HBase 使用的是 java.util.concurrent 下的 ConcurrentSkipListMap()。

2.2 在RocksDB中的应用

RocksDB的MemTable 内部存储数据也使用了跳表。

2.3 ConcurrentSkipListMap

ConcurrentSkipListMap中有三种结构，base nodes,Head nodes和index nodes。

• base node组成了有序的链表结构，是ConcurrentSkipListMap的最底层实现。
• index node是构建SkipList上层结构的基本节点。Index节点包含了Node节点，除此之外，Index还有两个指针，一个指向同一个layer的下一个节点，一个指向下一层layer的节点。
• HeadIndex代表的是head node，继承自Index node，增加了level表示层级
• 在ConcurrentSkipListMap初始化的时候，会初始化HeadIndex：看到HeadIndex中的Node是key=null，value=BASE_HEADER的虚拟节点。初始的level=1

 /**
     * Initializes or resets state. Needed by constructors, clone,
     * clear, readObject. and ConcurrentSkipListSet.clone.
     * (Note that comparator must be separately initialized.)
     */
    private void initialize() {
        keySet = null;
        entrySet = null;
        values = null;
        descendingMap = null;
        head = new HeadIndex<K,V>(new Node<K,V>(null, BASE_HEADER, null),
                                  null, null, 1);
    }

2.4 ConcurrentSkipListSet

ConcurrentSkipListSet的实现基于ConcurrentSkipListMap的，添加和删除元素，元素遍历等都是基于ConcurrentSkipListMap方法的，value固定为Boolean.TRUE，其常用方法实现如下：

	public ConcurrentSkipListSet() {
        m = new ConcurrentSkipListMap<E,Object>();
    }
 
	public ConcurrentSkipListSet(Comparator<? super E> comparator) {
        m = new ConcurrentSkipListMap<E,Object>(comparator);
    }
 
 
	public boolean add(E e) {
        return m.putIfAbsent(e, Boolean.TRUE) == null;
    }
 
	public boolean remove(Object o) {
        return m.remove(o, Boolean.TRUE);
    }
 
	public Iterator<E> iterator() {
        return m.navigableKeySet().iterator();
    }
 
	public Iterator<E> descendingIterator() {
        return m.descendingKeySet().iterator();
    }