在数据结构中，树一直被许多系统钟爱，如mysql 的innodb运用的是B+ 数，在java中Map的hash磕碰后，假如链表超越8 会切换为红黑树。树结构的优点个人认为是在写入的时分对数据进行一个预处理，并且这个出力和子节点的数量相关，在写入的时分依照规则刺进，能够在查询的时分有效的查询对应的子树，然后到达查询时刻为LogN 。如红黑树，红黑树的结构是异构化的23 树，能够确保左右子树的高度差维持在1，有效保证数据平衡，可是红黑树的完成比较复杂，刺进进程涉及到树的重平衡。后来呈现了一种链表的结构，称之为跳表即SkipList，他是由William Pugh 在Skip Lists: A Probabilistic Alternative to Balanced Trees提出的一种平衡性很好的数据结构，这种数据结构是运用空间换时刻，完成较为简略，查询复杂度和树结构接近。在redis 和leveldb中都有运用。本文会介绍下SkipList的基本原理和一个java完成。

（更多…）