跳跃表 (skiplist) 是一种有序数据结构,它通过在每个节点中维持多个指向其他节点的 指针,从而达到快速访问节点的目的。
跳跃表优点
- 表支持平均
O(logN)
, 最坏O(N)
复杂度的节点查找,效率可以和平衡树相当 - 通过顺序性操作来批量处理节点
- 实现比平衡树要来得更为简单
因为ziplist
内存占用较小,所以Redis使用作为有序集合的初始底层结构。
如果一个有序集合包含的元素数量比较多(大于zset-max-ziplist-entries
),又或者有序集合中元素的成员是比较长的字符串时(大于zset-max-ziplist-value
),Redis就会将其底层结构转换为跳跃表。