跳表

每一层都是对下一层的独立稀疏抽样，搜索在高层跨过大段键区间，接近目标后逐层下降。几何高度让最高塔只有对数级，每层反向经过的节点数又有常数期望，因此无需全局旋转也能得到期望对数路径。

快车道例子 ​

底层存放全部时间戳；较高层只保留逐级抽样的时间戳。查询某一时刻先在稀疏层跨过大片区间，接近目标后下降到底层。这与给链表额外固定步长索引不同：随机高度使任何插入位置都不需要整体重排。

边界与接口 ​

这些不是最坏界；随机源退化或能观察结构的自适应对手可能制造更细的条件问题。工程实现常设最大层，截断概率分布后须重新写高度保证。范围报告先定位左端点再顺底层输出，期望成本是 $O(\log (n+1)+k)$，不能漏掉输出量 $k$。并发 skip list 的内存回收与线性化点是额外正确性问题，不由这里的顺序概率分析覆盖。

插入路径与尾界 ​

搜索时保存每层最后一个小于目标的节点 update$[\ell ]$，再检查第 0 层后继是否就是目标键。已有键按上面的覆盖或无操作规则处理，不重新抽样。对新键抽出高度 $h$ 后，只在 $0,\dots ,h$ 层把 update 的 next 改指新节点，再让新节点指向原后继；若 $h$ 超过当前最高层，新增层以前驱头节点开始。由此每层有序链和每键唯一节点的不变量都得到保持。

对 $n\ge 1$ 和任意常数 $c>1$，对各节点的高塔事件取并集界理路并集界Union bound · Boole 不等式多个坏事件中至少一个发生的概率，不超过各事件概率之和。，得到存在高度至少 $c{\log }_{1/p}n$ 的节点概率至多

这是对最高层的高概率界；完整搜索步数还需结合每层水平移动的几何尾，不能只由“高度低”一句推出。

一条搜索路径的账 ​

搜索键 37 时，指针可能依次经过“顶层右移到 24、下降、右移到 32、下降两层、右移到 35”。从目标位置反向看，每层连续跨过未晋升节点的步数受几何尾控制。对通常的 $O({\log }_{1/p}n)$ 层逐层累加期望水平步数，再计入更高层的尾部贡献，可得期望 $O(\log n)$ 搜索时间。