跳跃表(skiplist)是一种有序数据结构,通过每个节点中维持多个指向其他节点的指针,达到快速访问节点的目的,被作为有序集合键的底层实现之一
-
跳跃表由zskiplist和zskiplistNode两个结构定义
-
zskiplist的结构
header | tail | level | length
header: 跳跃表的表头节点
tail: 跳跃表的表尾节点
level: 目前跳跃表内,层数最大的那个节点的层数(表头的节点层数不计算在内)
length: 节点的个数
-
zskiplistNode的结构
level[] | *backward | score | *obj
level: 保存前进指针和跨度,level的层数是根据幂次定律(power law,越大的数出现的概率越小)产生.
backward: 后退指针,指向前一个节点
score: 排序用到的分数
obj: 成员对象
-
level的结构
*forward | span
forward: 前进指针
span: 跨度,用于计算目标节点的排位
-
-
总结
- 跳跃表可以看做是有序的双向链表中随机添加了一些快速跳跃的指针,将链表O(N)的时间复杂度优化成O(logN)(通过指针的空间换取操作时间).
- header指向一个不保存数据的哑结点(dummy node),这个哑结点可以设置成最大level层数(ZSKIPLIST_MAXLEVEL,32or64),防止保存数据的头节点的level层数随机达不到最大层数的问题.<Redis设计与实现>一书中未介绍查找和插入的细节(待续)
Redis-跳跃表
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
