数据结构 -- SkipList

2015-11-20 Friday    

William Pugh 于 1990 年发表了 Skip lists: a probabilistic alternative to balanced trees 论文,也就是设计初衷是作为替换平衡树的一种选择,这是一种随机化数据结构,基于并联的链表,其效率可比拟二叉查找树。

同时,可以支持排序。

简介

对于有序链表,查找的时间复杂度为 O(n),尽管真正的插入与删除操作节点复杂度只有 O(1),但都需要先查找到节点的位置,从而降低了有序链表的性能。

而 SkipList 采用 “空间换时间” 的策略,除了原始链表外还保存一些 “跳跃” 的链表,从而可以达到加速查找的效果。

链表优化

对于链表来说,如果通过指针顺序查找,就需要忍受 O(n) 的效率;如果采用数组实现,可以通过二分查找优化到 O(lgn) ,主要是因为二分查找需要用到中间位置的节点,而链表不能随机访问。

如果链表在保存原始数据的同时,保存中间节点的位置,那么就可以获取到高性能的查找方式。简单来说,其处理思想类似如下方式:

  • 结合了链表和二分查找的思想;
  • 将原始链表和一些通过 “跳跃” 生成的链表组成层;
  • 第 0 层是原始链表,越上层 “跳跃” 的步距越大,对应链表元素也越少;
  • 上层链表是下层链表的子序列,在查找时从顶层向下,不断缩小搜索范围。

其实现如下。

skiplist

主要由如下的几部分组成:

  • 表头,负责维护跳表的节点指针;
  • 节点,包括了元素值以及多个层的指针;
  • 层,保存了指向其它元素的指针,用来从上层依次查找;
  • 表尾,通过 NULL 组成,标识跳跃表结束。

SkipList 每层的数量不会严格按照 2:1 的比例,而是对每个要插入的元素随机一个层数。 随机层数的计算过程如下:

每个节点都有第一层 那么它有第二层的概率是p,有第三层的概率是p*p 不能超过最大层数

在 Redis 中的实现如下。

/* Returns a random level for the new skiplist node we are going to create.
 * The return value of this function is between 1 and ZSKIPLIST_MAXLEVEL
 * (both inclusive), with a powerlaw-alike distribution where higher
 * levels are less likely to be returned. */
int zslRandomLevel(void) {
    int level = 1;
    while ((random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF))
        level += 1;
    return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
}

其中 ZSKIPLIST_P 的值是 0.25,也就是说存在上一层的概率是 1/4

其它

SkipList VS. Tree

对于 AVL 树来说,有着严格的 O(logN) 的查询效率,但是由于插入过程中可能需要多次旋转,导致插入效率较低,因而才有了在工程界更加实用的红黑树。

但红黑树有个问题就是在并发环境下使用不方便,在更新数据时,红黑树有个平衡的过程,在这个过程中会涉及到较多的节点,需要锁住更多的节点,从而降低了并发性能。

另外,SkipList 的实现要简单很多,目前在 Redis、BigTable 中有使用。

Rank

一般在游戏中会有一个排名,通过跳表可以很容易实现相关的功能,在计算排名次序时,与在跳表中查找的时间复杂度是一样的,仍然是 O(lgN),而对于二叉树,貌似查找排名只能按照顺序遍历的方式来统计。



如果喜欢这里的文章,而且又不差钱的话,欢迎打赏个早餐 ^_^