概述

SkipList,跳表,跳跃表,在LevelDB和Lucene中都广为使用。跳表被广泛地运用到各种缓存实现当中,跳跃表使用概率均衡技术而不是使用强制性均衡,因此对于插入和删除结点比传统上的平衡树算法更为简洁高效。

Skip lists are data structures that use probabilistic balancing rather than strictly enforced balancing. As a result, the algorithms for insertion and deletion in skip lists are much simpler and significantly faster than equivalent algorithms for balanced trees.

传统意义的单链表是一个线性结构,在一个有序链表里,查询、插入、删除一个结点的算法时间复杂度都是O(n)

跳表示意图

数据结构之跳表SkipList、ConcurrentSkipListMap_skiplist

跳表是在链表之上加上多层索引构成的:

  • 表头(head):负责维护跳跃表的结点指针
  • 跳跃表结点:保存着元素值,以及多个层
  • 层:保存着指向其他元素的指针,这个层数是随机的

每一个结点不单单只包含指向下一个结点的指针,可能包含很多个指向后续结点的指针,这样就可以跳过一些不必要的结点,从而加快查找、删除等操作。对于一个链表内每一个结点包含多少个指向后续元素的指针,这个过程是通过一个随机函数生成器得到,这样子就构成一个跳跃表。通过随机生成一个结点中指向后续结点的指针数目。所有操作都以对数随机化的时间进行。

优点,跟红黑树、AVL等平衡树一样,做到比较稳定地插入、查询与删除,支持顺序操作。插入查询删除的算法时间复杂度理论值为O(logn),最坏情况下O(n)

跳表性质:

  1. 由很多层结构组成,每一层都是一个有序的链表
  2. 最底层(Level 1)的链表包含所有元素,最底层数据结构退化为一个普通的有序链表
  3. 如果一个元素出现在Level i的链表中,则它在Level i之下的链表也都会出现
  4. 每个结点包含两个指针,一个指向同一链表中的下一个元素,一个指向下面一层的元素
  5. 搜索过程是逐层进行,不能越两级搜索
  6. 在每一层中,-1和1两个元素都出现(分别表示INT_MIN和INT_MAX)
  7. Top指针指向最高层的第一个元素
  8. 跳表是一种以牺牲更多的存储空间换取查找速度,即空间换时间

Skip List构造步骤

  • 给定一个有序的链表
  • 选择链表中最大和最小的元素,然后从其他元素中按照一定算法随机选出一些元素,将这些元素组成有序链表。这个新的链表称为一层,原链表称为其下一层
  • 为刚选出的每个元素添加一个指针域,这个指针指向下一层中值同自己相等的元素。Top指针指向该层首元素
  • 重复2、3步,直到不再能选择出除最大最小元素以外的元素

跳表的插入
先确定该元素要占据的层数K(随机),然后在Level 1…Level K各个层的链表都插入元素。K大于链表层数,则需要添加新层。跳表的插入需要三个步骤:

  • 需要查找到在每层待插入位置
  • 随机产生一个层数
  • 从高层至下插入,插入时算法和普通链表的插入完全相同

删除结点操作和插入差不多,找到每层需要删除的位置,删除时和操作普通链表完全一样。如果该结点的level是最大的,则需要更新跳表的level。

理论

数据结构之跳表SkipList、ConcurrentSkipListMap_skiplist_02

数据结构之跳表SkipList、ConcurrentSkipListMap_链表_03

数据结构之跳表SkipList、ConcurrentSkipListMap_skiplist_04

跳表 vs B+树

相同:都是用空间来换取时间,用额外的空间来保存链表或者目录页,来提升查询性能

区别:

  • 层高:B+树三层就能支持千万级别的数据,但跳表存储相同的数据量需要更高的层级。InnoDB索引用B+树而不用跳表的原因,InnoDB强依赖于磁盘IO,层级越高,IO次数也就越多;Redis的zset是用的跳表,因为Redis是基于内存操作,没有磁盘IO概念,跳表更简单
  • 操作数据:跳表比B+树快,B+树在数据操作时需要维护B+树,所以会有树的分裂与合并;跳表是随机一个层次,实现相对简单

跳表 vs 平衡树

类似于平衡树,用来快速查找。区别是平衡树的插入和删除可能需要一次需要全局调整,而跳表只需对整个数据结构进行局部操作。所以在高并发下,需要对平衡树进行全局锁,而跳表只需部分加锁。
本质是维护多个分层的链表,最底层的链表维护表内所有元素,每上面一层是下面一层的子集。表内所有元素的链表都是排序的。查找时,先从最顶层开始查找,当发现查找元素大于链表中取值就进入下一行,用空间换时间。

插入
插入时,先查询,然后从最底层开始,插入被插入的元素。然后看看从下而上,是否需要逐层插入。可是到底要不要插入上一层呢?想每层的跳跃都非常高效,越是平衡就越好(第一层1级跳,第二层2级跳,第3层4级跳,第4层8级跳)。但是用算法实现起来,确实非常地复杂的,并且要严格地按照2地指数次幂,我们还要对原有地结构进行调整。所以跳表的思路是抛硬币,听天由命,产生一个随机数,50%概率再向上扩展,否则就结束。这样子,每一个元素能够有X层的概率为0.5^(X-1)次方。反过来,第X层有多少个元素的数学期望大家也可以算一下。

删除
同插入一样,删除也是先查找,查找到之后,再从下往上逐个删除。

跳表 vs 红黑树

为什么Redis要使用跳表而不使用红黑树呢?跳表相对于红黑树的优点:

  1. 代码相对简单
  2. 如果要查询一个区间里面的值,用平衡树在实现和理解上可能会麻烦些,虽然可以实现
  3. 删除一段区间,用平衡二叉树则涉及到树的平衡问题而相当困难,跳表没有这个问题

应用

JDK

在JDK里也有跳表的实现,如ConcurrentSkipListMap和ConcurrentSkipListSet。

ConcurrentSkipListMap

JDK22版本下,ConcurrentSkipListMap属性如下:

/**
 * 指定全局比较器,用于比较两个元素的关键字大小并进行排序,如果在构造器中没有显式传入指定比较器,则默认对key按照自然顺序排序
 */
@SuppressWarnings("serial") // Conditionally serializable
final Comparator<? super K> comparator;
/** 最上层索引链表的头结点,延迟加载(包括下面几个属性),即在使用时才会初始化 */
private transient Index<K,V> head;
/** 元素计数器 */
private transient LongAdder adder;
/** 保存keyset集合 */
private transient KeySet<K,V> keySet;
/** 保存value的集合 */
private transient Values<K,V> values;
/**  保存key-value的EntrySet集合 */
private transient EntrySet<K,V> entrySet;
/** 保存key-value结点的逆序排序的Map集合 */
private transient SubMap<K,V> descendingMap;
  • 1.
  • 2.
  • 3.
  • 4.
  • 5.
  • 6.
  • 7.
  • 8.
  • 9.
  • 10.
  • 11.
  • 12.
  • 13.
  • 14.
  • 15.
  • 16.
  • 17.

内部类有Node、Index、,省略构造方法(下同):

static final class Node<K,V> {
	final K key; // currently, never detached
	V val;
	Node<K,V> next;
}
  • 1.
  • 2.
  • 3.
  • 4.
  • 5.

Node表示链表结点,用于保存数据,包括三个属性:key-键、volatile的value-值、volatile的next-后继结点。

static final class Index<K,V> {
	final Node<K,V> node;  // currently, never detached
	final Index<K,V> down;
	Index<K,V> right;
}
  • 1.
  • 2.
  • 3.
  • 4.
  • 5.

Index表示基于链表的索引结点,用于保存索引关系和索引相关操作。包括三个属性:指向的链表数据结点node,指向下一层索引链表的索引结点down,指向同一层索引链表的当前结点的后继索引结点right。

抽象内部类Iter,见名知意,用于迭代:

abstract class Iter<T> implements Iterator<T> {
	/** next()方法返回的最后一个节点 */
	Node<K,V> lastReturned;
	/** next()方法返回的下一个节点 */
	Node<K,V> next;
	/** 缓存下一个值字段以保持弱一致性 */
	V nextValue;
	
	/** 初始化整个范围的升序迭代器 */
	Iter() {
		advance(baseHead());
	}
	
	public final boolean hasNext() {
		return next != null;
	}
	
	/** Advances next to higher entry. */
	final void advance(Node<K,V> b) {
		Node<K,V> n = null;
		V v = null;
		if ((lastReturned = b) != null) {
			while ((n = b.next) != null && (v = n.val) == null)
				b = n;
		}
		nextValue = v;
		next = n;
	}
	
	public final void remove() {
		Node<K,V> n; K k;
		if ((n = lastReturned) == null || (k = n.key) == null)
			throw new IllegalStateException();
		// It would not be worth all of the overhead to directly
		// unlink from here. Using remove is fast enough.
		ConcurrentSkipListMap.this.remove(k);
		lastReturned = null;
	}
}
  • 1.
  • 2.
  • 3.
  • 4.
  • 5.
  • 6.
  • 7.
  • 8.
  • 9.
  • 10.
  • 11.
  • 12.
  • 13.
  • 14.
  • 15.
  • 16.
  • 17.
  • 18.
  • 19.
  • 20.
  • 21.
  • 22.
  • 23.
  • 24.
  • 25.
  • 26.
  • 27.
  • 28.
  • 29.
  • 30.
  • 31.
  • 32.
  • 33.
  • 34.
  • 35.
  • 36.
  • 37.
  • 38.
  • 39.

基于Iter抽象类,有3个实现类分别用于Key、Value、Key和Value的遍历,即KeyIterator、ValueIterator、EntryIterator这3个内部类。

核心方法

  • put:插入结点,调用doPut方法,使用到VarHandle的acquireFence、compareAndSet两个方法,以及ThreadLocalRandom.nextSecondarySeed()方法,源码还是挺复杂的
  • remove:删除结点,有多个重载方法,最后调用doRemove方法
  • get:查找结点,调用doGet方法,也是使用到VarHandle的acquireFence、compareAndSet两个方法,和双层循环。基于doGet方法,还提供有用的getOrDefault方法
  • replace:有两个方法
  • public V replace(K key, V value),如果指定key对应的结点存在,那么使用指定value替换旧value。返回以前与指定键关联的值;如果没有该键的映射关系,则返回null
  • public boolean replace(K key, V oldValue, V newValue):如果指定key-value对应的结点存在,则使用newValue替换oldValue。如果该值被替换成功,则返回true。
  • contains:来自Map的方法,用于判断是否包括某个Key或Value,包括:
  • containsKey:直接使用doGet来判断即可
  • containsValue:通过一层循环来遍历
  • size:判断大小
  • isEmpty:判断是否为空,判断头结点是否为空即可:return findFirst() == null;
  • clear:清空

doRemove方法使用两层嵌套循环,默认情况下使用break关键词只会跳出一层循环体。为了实现一次性跳出两层(多层也可以)循环,在最外层定义一个outer:,注意冒号不能省略,然后使用break outer实现:

final V doRemove(Object key, Object value) {
	if (key == null)
	    throw new NullPointerException();
	Comparator<? super K> cmp = comparator;
	V result = null;
	Node<K,V> b;
	outer: while ((b = findPredecessor(key, cmp)) != null &&  result == null) {
	    for (;;) {
	        Node<K,V> n; K k; V v; int c;
	        if ((n = b.next) == null)
	            break outer;
	        else if ((k = n.key) == null)
	            break;
	        else if ((v = n.val) == null)
	            unlinkNode(b, n);
	        else if ((c = cpr(cmp, key, k)) > 0)
	            b = n;
	        else if (c < 0)
	            break outer;
	        else if (value != null && !value.equals(v))
	            break outer;
	        else if (VAL.compareAndSet(n, v, null)) {
	            result = v;
	            unlinkNode(b, n);
	            break; // loop to clean up
	        }
	    }
	}
	if (result != null) {
	    tryReduceLevel();
	    addCount(-1L);
	}
	return result;
}
  • 1.
  • 2.
  • 3.
  • 4.
  • 5.
  • 6.
  • 7.
  • 8.
  • 9.
  • 10.
  • 11.
  • 12.
  • 13.
  • 14.
  • 15.
  • 16.
  • 17.
  • 18.
  • 19.
  • 20.
  • 21.
  • 22.
  • 23.
  • 24.
  • 25.
  • 26.
  • 27.
  • 28.
  • 29.
  • 30.
  • 31.
  • 32.
  • 33.
  • 34.

另外outer标志字段可以使用其他非Java保留关键词都行,如flag

有2个参数的replace方法源码:

public V replace(K key, V value) {
	if (key == null || value == null)
		throw new NullPointerException();
	for (;;) {
		Node<K,V> n; V v;
		if ((n = findNode(key)) == null)
			return null;
		if ((v = n.val) != null && VAL.compareAndSet(n, v, value))
			return v;
	}
}
  • 1.
  • 2.
  • 3.
  • 4.
  • 5.
  • 6.
  • 7.
  • 8.
  • 9.
  • 10.
  • 11.

有3个参数的replace方法源码:

public boolean replace(K key, V oldValue, V newValue) {
	if (key == null || oldValue == null || newValue == null)
		throw new NullPointerException();
	for (;;) {
		Node<K,V> n; V v;
		if ((n = findNode(key)) == null)
			return false;
		if ((v = n.val) != null) {
			if (!oldValue.equals(v))
				return false;
			if (VAL.compareAndSet(n, v, newValue))
				return true;
		}
	}
}
  • 1.
  • 2.
  • 3.
  • 4.
  • 5.
  • 6.
  • 7.
  • 8.
  • 9.
  • 10.
  • 11.
  • 12.
  • 13.
  • 14.
  • 15.

用于判断Value是否存在的containsValue方法:

public boolean containsValue(Object value) {
	if (value == null)
		throw new NullPointerException();
	Node<K,V> b, n; V v;
	if ((b = baseHead()) != null) {
		while ((n = b.next) != null) {
			if ((v = n.val) != null && value.equals(v))
				return true;
		else
				b = n;
		}
	}
	return false;
}
  • 1.
  • 2.
  • 3.
  • 4.
  • 5.
  • 6.
  • 7.
  • 8.
  • 9.
  • 10.
  • 11.
  • 12.
  • 13.
  • 14.

size方法最大为Integer.MAX_VALUE

public int size() {
	long c;
	return ((baseHead() == null) ? 0 : ((c = getAdderCount()) >= Integer.MAX_VALUE) ? Integer.MAX_VALUE : (int) c);
}
  • 1.
  • 2.
  • 3.
  • 4.

getAdderCount方法如下:

final long getAdderCount() {
    LongAdder a; long c;
    do {} while ((a = adder) == null && !ADDER.compareAndSet(this, null, a = new LongAdder()));
    return ((c = a.sum()) <= 0L) ? 0L : c; // ignore transient negatives
}
  • 1.
  • 2.
  • 3.
  • 4.
  • 5.
VarHandle

JDK 9引入的概念。TODO。

Kafka

Kafka的每个日志对象中使用ConcurrentSkipListMap来保存各个日志分段,每个日志分段的baseOffset作为key,这样可以根据指定偏移量来快速定位到消息所在的日志分段。

LevelDB

memtable用于存储在内存中还未落盘到sstable中的数据,这部分使用跳表做为底层的数据结构。

Lucene

占用内存小,且可调,但是对模糊查询支持不好。Lucene3.0之前使用的也是跳跃表结构,后换成FST,但跳跃表在Lucene其他地方还有应用如倒排表合并和文档号索引。

基于lucene-core-9.10.0版本,可以看到两个抽象类MultiLevelSkipListReader和MultiLevelSkipListWriter。前面的分析讲过,普通的快表只能从最上层往下一层层搜索,不能越两级搜索,因为没有维护越级的指针。

以MultiLevelSkipListReader为例,看看其属性有哪些:

public abstract class MultiLevelSkipListReader implements Closeable {
	/** the maximum number of skip levels possible for this index */
	protected int maxNumberOfSkipLevels;

	/** number of levels in this skip list */
	protected int numberOfSkipLevels;
	
	private int docCount;
	
	/** skipStream for each level. */
	private IndexInput[] skipStream;
	
	/** The start pointer of each skip level. */
	private long[] skipPointer;
	
	/** skipInterval of each level. */
	private int[] skipInterval;
	
	/**
	 * Number of docs skipped per level. It's possible for some values to overflow a signed int, but this has been accounted for.
	 */
	private int[] numSkipped;
	
	/** Doc id of current skip entry per level. */
	protected int[] skipDoc;
	
	/** Doc id of last read skip entry with docId <= target. */
	private int lastDoc;
	
	/** Child pointer of current skip entry per level. */
	private long[] childPointer;
	
	/** childPointer of last read skip entry with docId <= target. */
	private long lastChildPointer;
	
	private final int skipMultiplier;
}
  • 1.
  • 2.
  • 3.
  • 4.
  • 5.
  • 6.
  • 7.
  • 8.
  • 9.
  • 10.
  • 11.
  • 12.
  • 13.
  • 14.
  • 15.
  • 16.
  • 17.
  • 18.
  • 19.
  • 20.
  • 21.
  • 22.
  • 23.
  • 24.
  • 25.
  • 26.
  • 27.
  • 28.
  • 29.
  • 30.
  • 31.
  • 32.
  • 33.
  • 34.
  • 35.
  • 36.
  • 37.

TODO

Redis

zset数据结构,由zskiplist和zskiplistNode两个结构组成:前者用于保存跳跃表信息(如头结点、尾结点、长度等),后者用于表示跳跃表结点

参考