【数据结构】核心数据结构解析：跳表（Skip List）从底层原理到经典对比
在高性能后端开发和分布式存储中，跳表（Skip List）和B+ 树是高频出现的两个核心数据结构。Redis 的 ZSet、Java 的ConcurrentSkipListMap选择了跳表；而 MySQL 的 InnoDB 存储引擎则选择了 B+ 树。
本文将为你彻底拆解跳表的底层逻辑、核心机制，并深度对比它与 B+ 树的异同。
一、 什么是跳表（Skip List）？
跳表是一种可以用来替代平衡树（如红黑树、AVL树）的概率型数据结构。它在有序链表的基础上增加了多级索引，通过“空间换时间”的策略，实现了高效的查找、插入和删除操作，其平均时间复杂度均为O(logn)O(\log n)O(logn)。
核心结构特点：
基础层（Level 0）：最底层的单链表包含所有的元素，并且这些元素是严格递增排序的。
索引层（Level 1 ~ Level N）：上层的链表是下层链表的“导流索引”。每一层的节点都是从下一层中按一定概率ppp（通常为1/21/21/2或1/41/41/4）随机抽取出来的。
概率平衡：跳表不需要像平衡树那样在插入时进行复杂的旋转或重平衡，而是为每个新插入的节点随机生成一个高度（层数）。这种概率上的平衡同样能保证整体操作的高效性。
二、 核心精髓：多级索引（Multi-level Index）
单链表最大的痛点在于无法进行二分查找，只能从头到尾一个个往后拉（时间复杂度O(n)O(n)O(n)）。为了让链表也能飞起来，跳表引入了多级索引。
1. 结构具象化
多级索引的核心思想是：“给索引再做索引，通过层层提炼、减少搜索范围，实现大数据的快速定位”。
Plaintext
Level 2 (高跨度索引) : [1] --------------------------> [5] --------------------------> [9] | | | Level 1 (中跨度索引) : [1] -----------> [3] -----------> [5] -----------> [7] -----------> [9] | | | | | Level 0 (基础数据层) : [1] -> [2] -> [3] -> [4] -> [5] -> [6] -> [7] -> [8] -> [9]2. 查找过程示例
假设我们要查找节点7：
从顶层（Level 2）出发：看到
1，向右看是5。因为7 > 5，继续向右看是9。由于7 < 9，说明目标值必然在5到9之间。下沉到 Level 1：从刚才锁定的
5开始往右看，下一个节点直接就是7。目标命中！直接下沉到 Level 0 即可获取真实数据。
生活映射：这就像我们查字典。先根据声母（第一级索引）找到T，再根据音节（第二级索引）找到tiao，最后翻到具体页码（基础层）顺序找到“跳”字。多级索引将长距离的查找切分成**“大步跳跃→\rightarrow→小步微调”**的过程。
三、 为什么跳表能完美支持范围查询？
跳表能够高效支持范围查询（Range Query，如查找区间[low,high][low, high][low,high]内的所有元素），主要得益于它的双重特性：上层的快速定位能力+底层的顺序遍历能力。
第一步：快速定位起点
利用多级索引从顶层向下、向右查找，如同二分查找一般快速跳过无关元素，在O(logn)O(\log n)O(logn)的时间内定位到范围的左边界（第一个≥low\ge low≥low的节点）。
第二步：底层顺序横扫
定位到起点后，直接下沉到最底层的Level 0。由于 Level 0 是一个完整的、紧凑的有序单向（或双向）链表，接下来只需沿着底层链表一路向右顺序指针遍历，直到遇到第一个>high> high>high的节点为止。
复杂度分析：总时间复杂度为O(logn+k)O(\log n + k)O(logn+k)，其中O(logn)O(\log n)O(logn)为定位起点的时间，kkk为区间内元素的数量。
四、 终极对决：跳表 VS B+ 树
跳表和 B+ 树都能完美支持范围查询，但它们的底层设计哲学和应用场景截然不同。
1. 存储介质与内存布局（核心区别）
B+ 树：专为磁盘（外存）设计。它的分支因子非常大（通常上百），树的高度极低（一般 3~4 层），每个节点对应一个固定大小的磁盘页（Page）。这样可以最大限度地减少磁盘 I/O 次数。
跳表：专为纯内存设计。跳表充斥着大量的指针，在内存中离散分布。如果放到磁盘上，指针跳转会导致极其致命的随机 I/O。但在纯内存环境下，指针跳转的代价微乎其微。
2. 并发锁粒度（为什么高并发多线程喜欢跳表？）
B+ 树：在多线程高并发插入时，如果引发节点的分裂或合并，可能会触发级联反应，导致从叶子节点一直向上锁到根节点（锁升级），并发性能受限。
跳表：插入和删除操作极其局部化。由于节点的层数是随机决定的，插入一个节点只需要修改它前后相邻节点的指针，不需要做全局平衡调整。因此，跳表可以非常容易地使用CAS（Compare And Swap）保证线程安全，实现无锁或细粒度锁的并发结构（如 Java 的
ConcurrentSkipListMap）。
3. 特性对比一览表
| 对比维度 | 跳表 (Skip List) | B+ 树 (B+ Tree) |
|---|---|---|
| 主要存储介质 | 纯内存 (In-Memory) | 磁盘 / 外存 (Disk-Based) |
| 平衡机制 | 概率型平衡（依靠随机数，无锁化友好） | 确定型平衡（节点分裂/合并，易触发级联锁） |
| 平均时间复杂度 | O(logn)O(\log n)O(logn) | O(logn)O(\log n)O(logn)(由于分支大，常数项更小) |
| 空间开销 | 较大（每个节点需要维护多个前向指针） | 较小（紧凑的页结构，指针占比低） |
| 并发性能 | 极高（局部指针修改，适合 CAS 无锁化） | 一般（树平衡时需要锁大范围节点） |
| 缓存友好度 | 一般（指针悬空，容易 CPU Cache Miss） | 极高（页内数据连续存储，充分利用预读机制） |
| 实现复杂度 | 简单（代码优雅，指针操作，易于维护） | 极高（分裂、合并、红黑平衡逻辑复杂） |
| 典型应用经典 | Redis (ZSet)、Lucene、Java 并发包 | MySQL (InnoDB)、文件系统 (XFS, NTFS) |
五、 总结
如果你的场景是大数据量、强依赖磁盘 I/O、需要极致压榨单次查询性能（如数据库引擎），B+ 树是无可替代的选择。
如果你的场景是纯内存操作、面临超高并发的读写交织、且希望代码易于实现和扩展（如缓存中间件、并发工具包），那么跳表凭借其随性的概率平衡和极其优秀的无锁化潜力，则是绝对的明星选手。