跳表
SkipList(跳表) 这种数据结构是由_William Pugh_于 1990 年在在 Communications of the ACM June 1990, 33(6) 668-676 发表了_Skip lists: a probabilistic alternative to balanced trees_，在其中详细描述了他的工作。由论文标题可知，SkipList 的设计初衷是作为替换平衡树的一种选择。
我们都知道，AVL 树有着严格的
但是红黑树有一个问题就是在并发环境下使用不方便，比如需要更新数据时，Skip 需要更新的部分比较少，锁的东西也更少，而红黑树有个平衡的过程，在这个过程中会涉及到较多的节点，需要锁住更多的节点，从而降低了并发性能。
SkipList 还有一个优势就是实现简单，SkipList 的实现只花了 2 个小时，而红黑树，我可能得 2 天。
时隔将近三十多年，SkipList 这种数据结构仍在许多途径有用武之地，比如Redis, 还有 Google 的著名项目Bigtable.