skiplist跳表--一种高性能数据结构

meridian00 2019-07-01

skiplist简介

skip List是一种随机化的数据结构,基于并联的链表,实现简单,插入、删除、查找的复杂度均为O(logN)(大多数情况下),因为其性能匹敌红黑树且实现较为简单,因此在很多著名项目都用跳表来代替红黑树,例如LevelDB、Reddis的底层存储结构就是用的SkipList。

目前常用的key-value数据结构有三种:Hash表、红黑树、SkipList,它们各自有着不同的优缺点:
Hash表:插入、查找最快,为O(1);如使用链表实现则可实现无锁;数据有序化需要显式的排序操作。
红黑树:插入、查找为O(logn),但常数项较小;无锁实现的复杂性很高,一般需要加锁;数据天然有序。
SkipList:插入、查找为O(logn),但常数项比红黑树要大;底层结构为链表,可无锁实现;数据天然有序。

SkipList基本数据结构及其实现

一个跳表,应该具有以下特征:

1、一个跳表应该有几个层(level)组成;
通常是10-20层,leveldb中默认为12层。

2、跳表的第0层包含所有的元素;
且节点值是有序的。

3、每一层都是一个有序的链表;
层数越高应越稀疏,这样在高层次中能'跳过’许多的不符合条件的数据。

4、如果元素x出现在第i层,则所有比i小的层都包含x;

5、每个节点包含key及其对应的value和一个指向该节点第n层的下个节点的指针数组
x->next[level]表示第level层的x的下一个节点

skiplist的查询过程

查询的第一个比vx大的节点的前一个值,看是否相等。相等则存在,否则查找下一层,直到层数为0。

以已有数据13、22、75、80、99为例

skiplist跳表--一种高性能数据结构

从最高层(此处为2)开始

1、level2找到结点Node75小于80,且level2.Node75->next 大于80,则进入level1查找(此处已经跳过了13~75中间的结点(22),

2、level1.Node75 < 80 < level1.Node75->next,进入level0

3、level0.Node75->next 等于80,找到结点

skiplist的插入过程

假设插入一新键值key,值为84,level为当前层

skiplist跳表--一种高性能数据结构

1、从最高层开始找到每一层比84大的节点的前一个值,存入prev[level]。

这里

prev[2] = leve2.Node75

prev[1] = leve1.Node75

prev[0] = level0.Node80

2、初始化一个新的节点84
3、为x随机选择一个高度h,这里选2
4、x->next[0..h-1] = prev[0..h-1]->next
5、prev[0..h-1]->next[0..h-1] = x

(步骤4、5为链表插入结点的操作)

skiplist删除操作

删除操作类似于插入操作,包含如下3步:1、查找到需要删除的结点 2、删除结点 3、调整指针

总结

如果要实现一个key-value结构,需求的功能有插入、查找、迭代、修改,那么首先Hash表就不是很适合了,因为迭代的时间复杂度比较高;而红黑树的插入很可能会涉及多个结点的旋转、变色操作,因此需要在外层加锁,这无形中降低了它可能的并发度。而SkipList底层是用链表实现的,可以实现为lock free,同时它还有着不错的性能(单线程下只比红黑树略慢),非常适合用来实现我们需求的那种key-value结构。

相关推荐