研究跳表的构建方法与性能优化策略

一、简介

跳表在该算法的时间复杂度下（即O(log(n))）内可实现增删查等基本操作。相对于树堆与红黑树而言，在功能上与其相仿，在性能上具有可比性，并且由于其代码长度较短，在实现难度上亦较之更胜一筹。其设计理念则与链表构造思路不谋而合。

• Skip List（跳越列表），简称跳表
• 本质上是一种基于二分查找机制的链表数据结构
• 通过在原有有序链表基础上建立层次化索引系统
• 借助层级化索引实现快速定位数据存储位置，在一定程度上实现了时间和空间资源的权衡

二、跳表的特点

• 多层次结构设计中各层的生成遵循一定的概率分布
  • 各层均为有序的链表结构默认按升序排列，默认情况下底层则包含所有原始元素
  • 每个节点均包含两个指针指向右侧（right）和下方（down），分别对应同级和下级列表中的对应节点

三、跳表的组成