跳表(Skip List)

定义

跳表是一种基于多层链表的有序数据结构，通过在原始链表上方建立若干层稀疏的索引，实现接近平衡树的查找效率，同时实现简单、易于并发。

原理

最底层是包含全部元素的有序链表，每往上一层节点数约减半，形成快速通道。查找时从最高层开始向右走，遇到比目标大的节点就下降一层，逐层逼近目标。节点的层数在插入时随机决定（如抛硬币），无需像平衡树那样旋转维护。其期望性能与平衡树相当，但代码远更简单。

复杂度

• 查找（期望）：O(log n)
• 插入（期望）：O(log n)
• 删除（期望）：O(log n)
• 空间复杂度：O(n)

应用场景

• Redis 的有序集合 zset
• LevelDB、RocksDB 的 MemTable
• 需要有序且支持并发的内存索引