跳跃表(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设计与实现>一书中未介绍查找和插入的细节(待续)