那些经典算法:跳表（跳表的特征）
mhr18 2025-04-06 18:53 26 浏览 0 评论
简介
跳表（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的概率来插入数据的。
有空自己也实现下，就聊到这里面吧。
相关推荐
- 【推荐】一个开源免费、AI 驱动的智能数据管理系统，支持多数据库
-
如果您对源码&技术感兴趣，请点赞+收藏+转发+关注，大家的支持是我分享最大的动力！！！.前言在当今数据驱动的时代，高效、智能地管理数据已成为企业和个人不可或缺的能力。为了满足这一需求，我们推出了这款开...
- Pure Storage推出统一数据管理云平台及新闪存阵列
-
PureStorage公司今日推出企业数据云(EnterpriseDataCloud)，称其为组织在混合环境中存储、管理和使用数据方式的全面架构升级。该公司表示，EDC使组织能够在本地、云端和混...
- 对Java学习的10条建议（对java课程的建议）
-
不少Java的初学者一开始都是信心满满准备迎接挑战，但是经过一段时间的学习之后，多少都会碰到各种挫败，以下北风网就总结一些对于初学者非常有用的建议，希望能够给他们解决现实中的问题。Java编程的准备：...
- SQLShift 重大更新:Oracle→PostgreSQL 存储过程转换功能上线!
-
官网：https://sqlshift.cn/6月，SQLShift迎来重大版本更新！作为国内首个支持Oracle->OceanBase存储过程智能转换的工具，SQLShift在过去一...
- JDK21有没有什么稳定、简单又强势的特性?
-
佳未阿里云开发者2025年03月05日08:30浙江阿里妹导读这篇文章主要介绍了Java虚拟线程的发展及其在AJDK中的实现和优化。阅前声明：本文介绍的内容基于AJDK21.0.5[1]以及以上...
- 「松勤软件测试」网站总出现404 bug?总结8个原因，不信解决不了
-
在进行网站测试的时候，有没有碰到过网站崩溃，打不开，出现404错误等各种现象，如果你碰到了，那么恭喜你，你的网站出问题了，是什么原因导致网站出问题呢，根据松勤软件测试的总结如下：01数据库中的表空间不...
- Java面试题及答案最全总结(2025版)
-
大家好，我是Java面试陪考员最近很多小伙伴在忙着找工作，给大家整理了一份非常全面的Java面试题及答案。涉及的内容非常全面，包含：Spring、MySQL、JVM、Redis、Linux、Sprin...
- 数据库日常运维工作内容（数据库日常运维 工作内容）
-
#数据库日常运维工作包括哪些内容?#数据库日常运维工作是一个涵盖多个层面的综合性任务，以下是详细的分类和内容说明：一、数据库运维核心工作监控与告警性能监控：实时监控CPU、内存、I/O、连接数、锁等待...
- 分布式之系统底层原理(上)（底层分布式技术）
-
作者：allanpan，腾讯IEG高级后台工程师导言分布式事务是分布式系统必不可少的组成部分，基本上只要实现一个分布式系统就逃不开对分布式事务的支持。本文从分布式事务这个概念切入，尝试对分布式事务...
- oracle 死锁了怎么办?kill 进程 直接上干货
-
1、查看死锁是否存在selectusername,lockwait,status,machine,programfromv$sessionwheresidin(selectsession...
- SpringBoot 各种分页查询方式详解(全网最全)
-
一、分页查询基础概念与原理1.1什么是分页查询分页查询是指将大量数据分割成多个小块（页）进行展示的技术，它是现代Web应用中必不可少的功能。想象一下你去图书馆找书，如果所有书都堆在一张桌子上，你很难...
- 《战场兄弟》全事件攻略 一般事件合同事件红装及隐藏职业攻略
-
《战场兄弟》全事件攻略，一般事件合同事件红装及隐藏职业攻略。《战场兄弟》事件奖励，事件条件。《战场兄弟》是OverhypeStudios制作发行的一款由xcom和桌游为灵感来源，以中世纪、低魔奇幻为...
- LoadRunner（loadrunner录制不到脚本）
-
一、核心组件与工作流程LoadRunner性能测试工具-并发测试-正版软件下载-使用教程-价格-官方代理商的架构围绕三大核心组件构建，形成完整测试闭环：VirtualUserGenerator(...
- Redis数据类型介绍（redis 数据类型）
-
介绍Redis支持五种数据类型：String（字符串），Hash（哈希），List（列表），Set（集合）及Zset(sortedset：有序集合)。1、字符串类型概述1.1、数据类型Redis支持...
- RMAN备份监控及优化总结（rman备份原理）
-
今天主要介绍一下如何对RMAN备份监控及优化，这里就不讲rman备份的一些原理了，仅供参考。一、监控RMAN备份1、确定备份源与备份设备的最大速度从磁盘读的速度和磁带写的带度、备份的速度不可能超出这两...
欢迎 你 发表评论:
- 一周热门
- 最近发表
- 标签列表
-
- oracle位图索引 (63)
- oracle批量插入数据 (62)
- oracle事务隔离级别 (53)
- oracle 空为0 (50)
- oracle主从同步 (55)
- oracle 乐观锁 (51)
- redis 命令 (78)
- php redis (88)
- redis 存储 (66)
- redis 锁 (69)
- 启动 redis (66)
- redis 时间 (56)
- redis 删除 (67)
- redis内存 (57)
- redis并发 (52)
- redis 主从 (69)
- redis 订阅 (51)
- redis 登录 (54)
- redis 面试 (58)
- 阿里 redis (59)
- redis 搭建 (53)
- redis的缓存 (55)
- lua redis (58)
- redis 连接池 (61)
- redis 限流 (51)