简介

跳表（Skip List）是一种高效适合动态查找插入修改的数据结构，最早我了解跳表这个数据结构是学习Lucene，里面的倒排索引的实现利用到了跳表这种数据结构，在redis的有序集合的实现中，也是实现了跳表这种数据结构，可以参考源码t_zset.c。

跳表构造和原理

首先看看跳表的数据结构，如下：

从图中可以看出，跳表首先是一个多层链表（图中未两层），链表中的数字是有大小顺序的，每层节点不光有向右的本层指针，还有指向下层节点的指针，通过上层来确定数据的大小范围，再通过下层指针来进行最终的查找，查找索引链表的时候，是查找值首先和当前节点的值做比较，如果比当前的值大，且比后面节点的值小，则指针指向当前节点的down指针指向的下层索引链表节点或是原始链表。

增加了多层链表的目的是为了建立原始链表的索引，这样再查找数据的时候先从顶层开始查找，同样是上图，假设查找数字29，如果在原始链表上查找，需要查找的遍历8个节点，如果通过一级索引则需要遍历5个节点就可以查询到了，虽然只相差一个，相差不明显，如果数据量比较大，比如1000个，且做多层索引，性能会更好。

跳表的查询性能分析

普通链表查找元素的算法复杂度为O(n),如果按照上图，我们每两个链表节点就抽出一个节点作为上层节点，那第一级索引的节点个数为n/2,第二次为n/4，依次类推，第k层索引的节点个数为n/2k, 假设最高一层索引有两个节点则，n/2k = 2 从而得到k = log2n-1,如果我们查询元素的时候每层遍历m个节点，则查询数据的算法复杂度为O（m*logn),对于我们上面的这种情况，因为每隔两个节点会抽取一个做索引，分析下，每层包括访问的m为3，忽略系数，则查找数据的算法复杂度为O(logn)。

跳表的空间占用情况

跳表是一种以空间换时间的数据结构，只所以速度快，是因为有索引，到底占用了多少的额外空间那，需要分析下：
还按照每隔2个节点抽一个节点作为索引节点，那么每个索引层的节点数为：
n/2, n/4,n/8,...,8,4,2 相加按照等比数列计算求和公式：n-2
这样算起来跳表的空间的复杂度，当然如果在实际的软件开发中，索引节点只存储关键的比较值和指针占用的空间并不大，而且我们可以多个节点抽取一个节点作为索引节点，也可以进一步减少额外的空间占用。

跳表的插入和删除

单链表中，我们的插入数据和删除数据本身操作比较快，算法复杂度为O(1)，但是要查找到要删除的数据和插入数据的位置是比较麻烦的，借用老师的一张图表示下插入的过程：

插入的时间复杂度主要就是查找位置的过程，时间复杂度为O(logN)。

删除操作类似，只是删除需要获取节点的前驱节点指针，所以跳表如果删除操作比较多那么就适合用双向链表。

跳表索引的动态更新

当我们一直向原始链表插入数据的时候，需要及时更新索引，实际应用过程中，不一定严格按照上面每两个节点抽取一个节点作为索引节点，而是通过随机函数生成值K，那我们就将这个节点插入到第一级到第K层索引中。
借用老师的图：

并不是对每次插入都用随机函数来计算，可以每插入N个数据的时候，用随机函数来计算一次，如果每次都用随机函数生成K值，如果K永远大于1则有问题的，如果K的范围可以设置为小于0的特定数比如-3 到超过0的数比如2的整数，这样有1/6的概率来插入数据的。

有空自己也实现下，就聊到这里面吧。

Tags：设指针变量p指向单链表中结点a

微信扫一扫：分享

微信里点“发现”，扫一下

二维码便可将本文分享至朋友圈。