SkipList研究

吐槽

作为一名学渣，每次回头去翻看一下大学课程的基础知识，总会有不同的感受。笔者也总想着把自己工作中领悟的做归纳。关于查找算法，思想大概可以归类为三类（大神请绕路）：

• 顺序查找
• 二分查找（插入查找、斐波拉切查找…）
• 哈希查找

顺序查找是我们常用的遍历。在对性能要求比较高的业务场景下，我们便需要考虑其他更好的实现方式了（例如：为了避免全表扫描，数据库通过B+ Tree索引提高查找效率）。哈希查找，时间复杂度为O(1)，是一种常见且应用广泛的查找算法。本文将在剩余篇幅对二分查找法进行吐槽。

思考

咦？今天我们讨论的不是SkipList吗，为什么会谈到二分查找法，接下来笔者将阐述一下原因。在实际工程应用中，算法与数据结构是相辅相成的，相互依存，相互影响的， 没有数据结构支撑的算法只能是空中阁楼。接下来，我们思考尝试为二分查找（或类似思想）寻找一个适合的**数据结构**。

通常会从CRUD（即增、删、改、查）四个角度，结合具体应用场景去衡量一个数据结构的适用性。我们知道数据的存储方式分为两种：①顺序存储②链式存储。顺序存储中，有序列表的元素在内存中紧紧相连，可以**随机访问**（直接用下标访问，时间复杂度O(1)），能用二分查找法快速定位节点。但是顺序存储对增、删操作的处理比较费力（当删除列表中一个元素时，列表应当将该元素后面的元素前移，填补空的节点，同样增加元素时亦是如此）。

顺序存储不适用于增 、删操作频繁的应用场景，那么我们考虑一下*链式存储**。链表*能很好的处理增、删频繁的场景。但是链表一般**顺序访问（即读取第一个元素后才可以读取第二个元素，以此类推），显然传统的链表数据结构无法应用二分的思想进行快速查找。

聪明的人们结合二叉树，发明了**二叉查找树**———既可以二分查找，又能够快速添加、删除元素的数据结构。这正是我们期望的能够应用二分查找的完美数据结构吗？很遗憾，并不是。二叉查找树在最坏情况下可能变成一个链表。于是，在二分查找树的基础上，就出现了AVL平衡树。AVL树在增、删节点时，为了保持树的平衡，会进行左旋，右旋操作，增加了增、删操作的复杂度。于是乎根据人们在发明了B-Tree，B+ Tree，红黑树等。但是AVL树实现起来比较复杂，平衡操作较难理解。

所以便有了SkipList。

实现

百度搜索网上一些SkipList的实现，代码多多少少存在一些瑕疵。笔者根据自己对SkipList的理解，结合网上的一些实现，整理出了一份C语言版本的SkipList实现。读者可以参阅笔者的GitHub，源文件：https://github.com/keepalive555/study/blob/master/skiplist/skiplist.c。

其中SkipList新建Node节点，随机获取节点level值的random_level函数（源码如下所示），是笔者摘抄自Redis源码。*该函数是保证SkipList的CRUD操作时间复杂度为**O(logN)的核心所在***。

#define MAX_LEVEL 32
#define P 0.25

int random_level(void) {  
    int level = 1;  
    while ((random() & 0xFFFF) < (P * 0xFFFF))  
        level += 1;  
    return (level < MAX_LEVEL) ? level : MAX_LEVEL;  
}