如果说要学习一个简单却非常实用的“高级”数据结构，那么Skip List一定不能错过。它的提出已有二十多年[Pugh, W. (1990)]，却依旧应用广泛（Redis、LevelDB等）。作为平衡树(AVL、红黑树、伸展树、树堆)的替代方案，虽然它性能不如平衡树稳定，但是在实现难度上却很有优势，可算是高性价数据结构。 Skip List是什么### 我们常用数组和链表来组织数据，对于已排序的数据，数组的查询时间复杂度可以是$\Theta(lgn)$(二分查找)，插入和删除都是$\Theta(n)$。 链表提供了一种更加灵活的组织方式，