跳跃表通过分层节点与无锁CAS机制实现高并发有序集合操作。其核心是预查找+原子更新两阶段：先定位各层前驱节点，再逐层CAS修改forward指针；随机层数设计降低竞争，Java中ConcurrentSkipListSet复用该结构，读写高效且无全局锁。
跳跃表本身是有序链表的多层索引结构，天然支持 O(log n) 平均时间复杂度的查找、插入和删除。但原始跳跃表是单线程结构，要支持高并发下的有序集合操作，关键不在于“改结构”，而在于“加控制”——即在跳表骨架上叠加细粒度、无全局锁的并发协调机制。
分层节点+无锁/轻量锁设计
每个跳表节点（如 Redis 或 Java 的 ConcurrentSkipListMap）包含：
- 多个 forward 指针（按 level 分层），指向同层后继节点；
- 可选的 backward 指针（用于逆向遍历或范围查询）；
- span 字段（记录到下一节点的跨度，用于快速计算排名）；
- 原子引用字段（如 Java 中用
AtomicReferenceArray存储 forward 数组）。
插入或删除时，并不锁定整条链，而是只对涉及的局部节点（如待更新的前驱节点及其各层 forward）做 CAS（Compare-And-Swap）操作。例如：更新 level-2 的 forward 指针时，仅对该指针位置执行原子写，不影响其他层级或其他节点。
插入与删除的并发安全路径
核心是“预查找 + 原子更新”两阶段：
- 先从最高层开始向下遍历，记录每一层中目标位置的前驱节点（存入 update[] 数组）；
- 再逐层自顶向下尝试 CAS 更新：对第 i 层，将 update[i] 的 forward[i] 从旧值设为新节点（或跳过已删除节点）；
- 若某层 CAS 失败（说明该层已被其他线程修改），则重新遍历或回退重试；
- 成功插入后，新节点的各层 forward 指针也通过原子方式设置，确保其他线程看到一致视图。
删除同理：先定位节点，再逐层将前驱节点的 forward 指针跳过它，最后标记节点为“逻辑删除”（如置 null 或打删除标记），避免 ABA 问题。
随机层数 + 动态平衡，减少竞争热点
新节点的层数由概率算法决定（如抛硬币：每层以 0.5 概率向上延伸），这带来两个并发优势：
- 高层节点稀疏，插入/删除极少触及顶层，避免多线程频繁争抢头节点或顶层索引；
- 不同节点层数差异大，操作分散在不同层级，天然降低冲突概率；
- 无需全局 rebalance（对比红黑树），不会出现因旋转引发的长临界区或级联锁等待。
Java 中 ConcurrentSkipListSet 的实际体现
它底层复用 ConcurrentSkipListMap，key 为元素，value 为 Boolean.TRUE。其并发保障体现在：
- 所有 public 方法（
add/remove/contains）都是无锁或基于 CAS 的； - 内部使用 volatile 字段和
Unsafe原子操作，不依赖 synchronized； - 支持高吞吐的 range 查询（如
subSet），因底层跳表保持有序且跨度信息完整，可并行扫描区间而不阻塞写操作。
这种设计让并发读几乎无竞争，读写之间也仅在局部节点发生 CAS 冲突，整体吞吐远高于基于 ReentrantLock 的 TreeSet。
