Redis 数据结构之跳跃表

跳跃表是一种有序数据结构,它通过每个节点中维持多个指向其他节点的指针,从而达到快速访问节点的目的

跳跃表支持平均 O(logN)、最坏 O(N) 复杂度的节点查找,还可以通过顺序性操作来批量处理节点

如果一个有序集合包含的元素数量比较多,又或者有序集合中元素的成员是比较长的字符串时,Redis 就会使用跳跃表来作为有序集合键的底层实现

除了有序集合,跳跃表在 Redis 的另一个用途是在集群节点中用作内部数据结构

跳跃表实现

位于图片最左边的是 zskiplist 结构,用于保存跳跃表信息

通过两个指针,程序定位表头节点和表尾节点复杂度都为 O(1)
通过 length 属性,程序可以在 O(1) 时间内返回跳跃表的长度

右方是四个 zskiplistNode 结构,用于表示跳跃表节点

每个跳跃表节点层高都是 1 至 32 之间的随机数

在同一个跳跃表中,多个节点可以包含相同的分值,但每个节点的成员对象必须是唯一的

跳跃表中的节点按照分值大小进行排序,当分值相同时,节点按照成员对象的字典序进行排序

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容