0%

从skiplist说起

skiplist,又称作跳表,跳跃表。

最开始接触skiplist的时候是在看那本《数据结构与算法分析——C++语言实现》,这本书很好,但是看完的人并不多。在书中第一次看到skiplist数据结构的时候,感觉还挺复杂的。直到去年看redis实现的时候又看到了skiplist才发现这真的是一种很巧妙的数据结构。下面先看一下最简单的skiplist,然后介绍两种变体。

Basic Skiplist

Why Skiplist

首先看一下为什么需要skiplist这种数据结构?现在有这么一个应用场景,我们需要持续有序地存储一些数据,并且满足下面的需要:1.查找;2.插入。这两个是最具有代表性的操作,为什么这么说呢?如果需要查找的效率尽量高,那么就应该使用线性存储(比如数组,查找复杂度O(1) );而频繁插入则应该使用链式存储(比如链表,插入复杂度O(1) )。如果要把这两种结合起来的话,一种还不错的选择是二叉查找树(BST)。但是树本身有很多问题,比如如何保持平衡,如何动态调整。这个时候skiplist就出现了。简单来说,skiplist是一种可以满足树的大多数应用场景,同时又比树这种结构实现简单的数据结构。那么skiplist到底是什么样的呢?继续往下看。

原理

想要快速理解一个事情的原理的时候最简单的方法就是图示法(当然前提是图可以表示出来)。下图摘自维基百科。

如上图所示,skiplist底层数据存储使用的还是链表,这样我们就可以在每个节点定制化更多的信息。除了底层链表之外,上面还有几层,上面的每一层都比它的下一层节点要少,同时每一层的节点可以指定寻址到它的上一层(如果对应位置上一层也有节点的话)和下一层的对应的节点的。然后所有的层用一个指针数组来连接起来。下面看一下查找以及插入在skiplist中是怎么个样子。

首先是查找,先从最上面的一层开始。上图中第一层只有一个节点,但是我觉得更好一点是两个节点,不是一头一尾,而是一个头部节点和一个中间节点,假定为head, mid。将待查找的元素值于mid节点比较,如果小于mid节点值,则待查找节点一定在head和mid之间;大于mid节点则落在后半段区间。这样一次就去除了一半的元素。是不是似曾相似,对的,就是二分查找。整个查找的时间复杂度是O(lgn)。

插入。插入数据的时候我们先查找到底层数据节点需要插入的位置。然后像链表一样插入就可以了。这里还有一个问题,底层数据插入之后,上层链表的节点有时候也需要做一下改变。关于如何改变不同的skiplist实现往往都是不同的。下面的动图很好地演示了插入过程。其它像删除操作和插入操作很类似。

Segment Skiplist

虽然我这里叫Segment Skiplist,其实并没有这种算法,我只是觉得这么使用有点像Segment Tree而且没有想到其他的好名字,所以暂且这么叫吧。前面说过由于skiplist底层是链表节点,所以节点的数据可以实现定制化。现在有这么一个场景:和上面类似,在存储(当然也有修改)有序数据的基础上,我还需要查询两个数据中间有多少个数据。

首先底层肯定还是类似于上面的skiplist结构,这里的关键点是如何定制化节点的信息来实现区间查询。如果不添加数据,我们可以先查找到下限节点在底层链表(也就是存储了所有数据的链表)中的位置,然后在顺序往后查找。这个最坏的情况下,时间复杂度为O(n)。那么需要定制化什么信息呢?

在监控数据的时候,比如unix时间就是1970.1.1到当前的时间秒数,有时候我们存储的数据都是基于一个时间戳。这样查找的话只需要用上界数据减去下届数据就可以了。猛然一看,这个和我们上面的情景还是挺像的,但是仔细一想就发现完全不是那么一回事。以为我们上面还需要改动数据,而基于时间存储的数据一般是不会改动的。如果我们使用这种的话,改动一个数据,这个时间戳之后的数据往往都需要改动。那么怎么办呢?

上面的数据改动太多的本质原因是所有的数据都基于一个时间点,要想数据改动尽量小,我们就要使各个节点的数据依赖的部分尽可能的少。对于每一层,每个节点只存储上一个节点和当前节点之间的原始数据个数。举个栗子,上面第一幅图的第二层各个节点存储的额外数据从左到右分别为1,3,2。对于插入操作,则只需要找到插入数据所在的每一层链表区间,然后将区间的右边界存储数据加一;删除操作同理。

Cache-Friendly Skiplist

一个数据结构的好坏有一个很重要的指标是是否是Cache Friendly的?什么样的数据结构是Cache-Friendly的?简单来说就是连续存储。cache-friendly有什么用呢?我们知道cpu 有L1,L2 cache,在cpu与内存交互的时候会先去cpu cache里面取数据,如果取到了就是cache hit,否则就是miss。
skiplist本身是cache-unfriendly的,然后大概11年的时候写Linux内核的两个哥们Liu Bo和Chris Mason对skiplist做了friendly的改进,并做了benchmark测试。改进后的skiplist如下,并不打算细说了。感兴趣的可以参考cache-friendly skiplist