跳表

概述

跳表（SkipList）是由William Pugh提出的。他在论文《Skip lists: aprobabilistic alternative to balancedtrees》中详细地介绍了有关跳表结构、插入删除操作的细节。

这种数据结构是利用概率均衡技术，加快简化插入、删除操作，且保证绝大大多操作均拥有O(logn)的良好效率。

作者在他的论文中这样介绍跳表：

跳表 - 图1

平衡树（以红黑树为代表）是一种非常复杂的数据结构，为了维持树结构的平衡，获取稳定的查询效率，平衡树每次插入可能会涉及到较为复杂的节点旋转等操作。作者设计跳表的目的就是借助概率平衡，来构建一个快速且简单的数据结构，取代平衡树。

跳表 - 图2

作者从链表讲起，一步步引出了跳表这种结构的由来。

图a中，所有元素按序排列，被存储在一个链表中，则一次查询之多需要比较N个链表节点；

图b中，每隔2个链表节点，新增一个额外的指针，该指针指向间距为2的下一个节点，如此以来，借助这些额外的指针，一次查询至多只需要⌈n/2⌉+ 1次比较；

图c中，在图b的基础上，每隔4个链表节点，新增一个额外的指针，指向间距为4的下一个节点，一次查询至多需要⌈n/4⌉+ 2次比较；

作者推论，若每隔2^i个节点，新增一个辅助指针，最终一次节点的查询效率为O(logn)。但是这样不断地新增指针，使得一次插入、删除操作将会变得非常复杂。

一个拥有k个指针的结点称为一个k层结点（level knode）。按照上面的逻辑，50%的结点为1层节点，25%的结点为2层节点，12.5%的结点为3层节点。若保证每层节点的分布如上述概率所示，则仍然能够相同的查询效率。图e便是一个示例。

维护这些辅助指针将会带来较大的复杂度，因此作者将每一层中，每个节点的辅助指针指向该层中下一个节点。故在插入删除操作时，只需跟操作链表一样，修改相关的前后两个节点的内容即可完成，作者将这种数据结构称为跳表。

结构

跳表 - 图3

一个跳表的结构示意图如上所示。

跳跃列表是按层建造的。底层是一个普通的有序链表。每个更高层都充当下面链表的"快速通道"，这里在层i 中的元素按某个固定的概率 p (通常为0.5或0.25)出现在层 i+1中。平均起来，每个元素都在 1/(1-p)个列表中出现，而最高层的元素（通常是在跳跃列表前端的一个特殊的头元素）在O(log1/p__n) 个列表中出现。

查找

跳表 - 图4

在介绍插入和删除操作之前，我们首先介绍查找操作，该操作是上述两个操作的基础。

例如图中，需要查找一个值为17的链表节点，查找的过程为：

  • 首先根据跳表的高度选取最高层的头节点；
  • 若跳表中的节点内容小于查找节点的内容，则取该层的下一个节点继续比较；
  • 若跳表中的节点内容等于查找节点的内容，则直接返回；
  • 若跳表中的节点内容大于查找节点的内容，且层高不为0，则降低层高，且从前一个节点开始，重新查找低一层中的节点信息；若层高为0，则返回当前节点，该节点的key大于所查找节点的key。

综合来说，就是利用稀疏的高层节点，快速定位到所需要查找节点的大致位置，再利用密集的底层节点，具体比较节点的内容。

插入

插入操作借助于查找操作实现。

跳表 - 图5

  • 在查找的过程中，不断记录每一层的前任节点，如图中红色圆圈所表示的；
  • 为新插入的节点随机产生层高（随机产生层高的算法较为简单，依赖最高层数和概率值p，可见下文中的代码实现）；
  • 在合适的位置插入新节点（例如图中节点12与节点19之间），并依据查找时记录的前任节点信息，在每一层中，以链表插入的方式，将该节点插入到每一层的链接中。

链表插入指：将当前节点的Next值置为前任节点的Next值，将前任节点的Next值替换为当前节点。

  1. func (p *DB) randHeight() (h int) {
  2.     const branching = 4
  3.     h = 1
  4.     for h < tMaxHeight && p.rnd.Int()%branching == 0 {
  5.         h++
  6.     }
  7.     return
  8. }

删除

跳表的删除操作较为简单，依赖查找过程找到该节点在整个跳表中的位置后，以链表删除的方式，在每一层中，删除该节点的信息。

链表删除指：将前任节点的Next值替换为当前节点的Next值，并将当前节点所占的资源释放。

迭代

向后遍历

  • 若迭代器刚被创建，则根据用户指定的查找范围[Start,Limit)找到一个符合条件的跳表节点；
  • 若迭代器处于中部，则取出上一次访问的跳表节点的后继节点，作为本次访问的跳表节点（后继节点为最底层的后继节点）；
  • 利用跳表节点信息（keyvalue数据偏移量，key，value值长度等），获取keyvalue数据；

向前遍历

  • 若迭代器刚被创建，则根据用户指定的查找范围[Start,Limit）在跳表中找到最后一个符合条件的跳表节点；
  • 若迭代器处于中部，则利用上一次访问的节点的key值，查找比该key值更小的跳表节点；
  • 利用跳表节点信息（keyvalue数据偏移量，key，value值长度等），获取keyvalue数据；