本文共 580 字,大约阅读时间需要 1 分钟。
Redis 跳跃表
- 概述
- 跳跃表skiplist,是一种有序的数据结构,通过在每个节点中维持多个指向其他节点的指针,达到快速访问的目的。
- 时间复杂度
- 因为大部分情况下效率与平衡树媲美,并且实现方式更为简单,故不少程序使用此数据结构代替平衡树。
- redis中使用跳表作为有序集合的底层实现。另外一个被用到的地方就是在集群节点中当作内部数据结构
- 实现
- zskiplistNode表示跳跃表节点
- level 层
- 前进指针
- 跨度 表示前进指针指向的节点与当前节点的距离
- backward指针
- 分值score
- double类型
- 从小到大排列
- 分值相同按照对象的大小排序
- 成员对象obj
- 注意
- zskiplist表示跳跃表节点的相关信息
- header
- tail
- level
- length
- 包含zskiplistNode
- 注意
- header,tail两个指针定位表头表尾时间复杂度O(1)
- O(1)时间复杂度返回跳表长度
- 空间复杂度O(N)
- 参考
转载地址:http://thiii.baihongyu.com/