跳表在有序链表上增加多级稀疏索引。查找从最高层开始向右走，下一节点超过目标时下降一层，直到最底层确认。它像在道路上先走高速再转支路，避免从头逐个扫描。

节点层高通常随机生成：每次以固定概率决定是否再升一层，因此高层节点越来越少。插入前先记录每层最后一个小于目标的前驱，再生成新节点高度，并把它接入对应层；删除同样利用前驱数组，在每层绕过目标节点。随机化不要求维护严格平衡，代码通常比平衡树直接。

1
2
3
4
5
x = head
for level from max down to 0:
  while x.next[level] < target:
    x = x.next[level]
candidate = x.next[0]

在合理随机层级下，查找、插入、删除的期望时间为 O(log n)，空间期望 O(n)；最坏情况下所有节点都只有底层，仍可能退化为 O(n)。有序底层链表使范围查询很自然：定位起点后连续向右输出，成本约 O(log n + k)。

Redis 有序集合采用跳表等结构支持按分值范围和排名访问，实际实现还会处理相同分值、跨度与字典映射。工程上需控制最大层数、随机概率与并发同步。

误区是把期望复杂度说成绝对保证、认为每隔固定节点建立索引、只更新底层指针，以及忽略重复键排序规则。小结：跳表用随机化换取简单的动态有序索引，优势在更新与范围遍历，代价是概率性高度和额外指针。