SkipList实现方法

文章结构概览

• 序言
  • SkipList结构示例
  • SkipList结构示例代码简易实现
  • 参考文献

前言

在前一篇文章中，笔者探讨了HDFS通过采用SkipList跳表结构来优化Snapshot的diff比较流程，并进一步提升了大规模Snapshot删除操作的效率（相关内容可参考上篇博文：聊聊HDFS删除Snapshot行为导致的NameNode crash）。本文将延续对这一跳表结构的讨论，简要介绍其原理，即通过构建多级链表体系，以牺牲部分存储空间为代价，从而显著提高数据检索的速度，属于一种典型的空间换时间的数据结构应用实例。

SkipList样例结构

为便于对SkipList进行示例说明，本文所构建的简易SkipList内部结构如下图所示，其采用按插入时间排列的链表形式实现。

     跳表的简单实现，通过维护多层级链表的形式，加速节点的查询，通过内存中维护更多
     的节点信息来换取查询的速度。
     跳表结构如下所示，基于time-based排序的链表结构.
     level 4: head----------------------------------s9->NULL
     level 3: head----------------->s5-----------