SkipList（跳表）的原理与实现

SkipList（跳表）的原理与实现

简介

这种数据结构是William Pugh于1990年在在 Communications of the ACMJune 1990, 33(6) 668-676 发表了Skip lists: a probabilistic alternative to balanced trees，论文标题可知，SkipList设计初衷是替换平衡树

（1）AVL树查询效率严格O(logN)，插入需多次旋转，导致插入效率较低，才有更实用红黑树。

（2）红黑树并发环境不方便，更新数据时，Skip更新较少，锁的也少，而红黑树有平衡的过程（涉及到较多节点），锁住更多节点，降低并发性。

（3）SkipList优势实现简单，红黑树2天，SkipList2个小时实现。