跳跃表（Skip List）是一种基于概率的、多层有序链表数据结构，由 William Pugh 于 1989 年提出。它通过维护多个层级的索引来实现快速查找，本质上是用"空间换时间"。

核心原理：

• 底层（Level 0）包含所有元素，是一个完整的有序链表。
• 上层是下层的"快速通道"——层级越高，节点越稀疏，跳跃的步幅越大。
• 每个节点随机决定自己出现在哪些层级（类似抛硬币，50%概率向上延伸一层）。
• 搜索时从最高层开始，向右移动直到下一个节点值大于目标值，然后下降一层继续，直到在底层找到目标或确认不存在。

这种设计使得跳跃表的平均时间复杂度为：搜索 O(log n)、插入 O(log n)、删除 O(log n)，与平衡树相当，但实现更简单。

优点：

• 🚀 实现简单：不需要复杂的旋转或重新平衡操作，代码量远少于红黑树。
• 🎲 概率性平衡：不需要维护严格的平衡条件，依赖随机化自动保持良好性能。
• 🔍 范围查询高效：底层是有序链表，范围遍历非常方便。
• 🔒 并发友好：插入和删除只影响局部指针，更容易实现无锁并发版本。

缺点：

• 💾 额外空间开销：每个节点需要存储多个指针（平均约2倍指针数）。
• 🎰 最坏情况退化：极低概率下可能退化为普通链表 O(n)，但实际中几乎不会发生。
• 📊 缓存不友好：节点分散在内存中，相比B+树等结构缓存局部性较差。

• Redis 有序集合（Sorted Set）：Redis 使用跳跃表作为有序集合的底层实现之一（当元素较多时）。
• LevelDB / RocksDB：LSM-Tree 的 MemTable 常使用跳跃表实现。
• Apache HBase：内存中的索引结构使用跳跃表。
• Lucene / Elasticsearch：倒排索引中的词汇表使用跳跃表加速合并操作。
• 并发数据结构：Java 的 ConcurrentSkipListMap 和 ConcurrentSkipListSet 提供了线程安全的有序映射和集合。

跳跃表使用随机化决定每个节点的层数：

• 每个节点必定出现在 Level 0（底层）。
• 从 Level 0 开始，以概率 p（通常 p=0.5）决定是否向上延伸一层。
• 如果成功（随机数 < p），则继续尝试下一层，直到失败或达到最大层数限制。

在概率 p=0.5 时，大约50%的节点只有1层，25%有2层，12.5%有3层，以此类推。这种分布保证了上层索引的稀疏性，使得搜索可以快速跳过大量节点。

在本可视化工具中，每次插入节点时，您可以看到节点被随机分配到的层级，直观感受这种概率性结构。