数据结构:跳表(Skip list)（跳表数据结构与算法）

mhr18 2025-05-03 15:20 27 浏览 0 评论

跳表[Skip list]是由分层的有序链表实现的数据结构，使用概率平衡，可以用来替代平衡树。它的插入、查找、删除时间复杂度跟平衡树相同，都是log(N), 但相比于平衡树，跳表的实现更加简单，并且节省空间。Redis的Sorted Set（有序集合）、LevelDB中的Memtable等都使用跳表实现。

性能比较

实现细节

我们考虑一个有序单链表：

在链表中查找一个数据需要遍历整个链表，时间复杂度是O(N)。
如果是有序数组，我们可以通过二分查找，时间复杂度O(logN)。
能不能把二分查找的思想用到链表上呢？

跳表就是通过快速定位元素所在的区间段而增加查询效率。每个链表的节点会有不同的高度，高度是随机的，越高层两个节点的间距越大，如下图：

具体实现(Go语言描述)

具体代码可参考：

https://github.com/liwnn/algorithms-go/blob/master/skiplist/skiplist.go

随机层数

p 取值范围为[0.0,1.0)，代表第i层能否出现的固定概率，通常为1/4
MaxLevel 最大层数，跟节点数有关。(1/p)^MaxLevel要大于最多节点数算法如下：

结构定义

查找

如上图所示，对于一个从小到大的跳表
如果我们需要查找元素e=17或19，只需要找到前置节点12，然后比较12的下一个节点是否是要查找的值即可

插入

跟查找类似，不过需要记录每一层的前置节点。插入元素的随机层数，并对每一层进行链表插入。

删除

跟插入一样，都需要要查找前置节点，然后删除元素所有层的链表元素

参考

Skip Lists: A Probabilistic Alternative toBalanced Trees：https://www.epaperpress.com/sortsearch/download/skiplist.pdf

redis 跳表

数据结构:跳表(Skip list)（跳表数据结构与算法）

性能比较

实现细节

具体实现(Go语言描述)

随机层数

结构定义

查找

插入

删除

参考

相关推荐

取消回复欢迎你发表评论:

生产系统数据库操作规范(2):（数据库生产库是什么意思）

Redis客户端 Jedis 与 Lettuce

高并发架构系列:Redis并发竞争key的解决方案详解

redis如何防止并发（redis如何防止高并发）

开源推荐:如何实现的一个高性能 Redis 服务器

redis安装与调优部署文档(WinServer)

Redis 入门 - 安装最全讲解(Windows、Linux、Docker)

一文带你了解 Redis 的发布与订阅的底层原理

Redis如何应对并发访问（redis控制并发量）

Java SE Development Kit 8u441下载地址【windows版本】

数据结构:跳表(Skip list)（跳表数据结构与算法）

性能比较

实现细节

具体实现(Go语言描述)

随机层数

结构定义

查找

插入

删除

参考

相关推荐

取消回复欢迎 你 发表评论:

生产系统数据库操作规范(2):（数据库生产库是什么意思）

Redis客户端 Jedis 与 Lettuce

高并发架构系列:Redis并发竞争key的解决方案详解

redis如何防止并发（redis如何防止高并发）

开源推荐:如何实现的一个高性能 Redis 服务器

redis安装与调优部署文档(WinServer)

Redis 入门 - 安装最全讲解(Windows、Linux、Docker)

一文带你了解 Redis 的发布与订阅的底层原理

Redis如何应对并发访问（redis控制并发量）

Java SE Development Kit 8u441下载地址【windows版本】

取消回复欢迎你发表评论: