04.跳跃表

1. 简介 :

   跳跃表是一种有序数据结构,他通过每个节点中维持多个执行其他节点的指针,从而达到快速访问节点的目的。
   redis 使用跳跃表作为有序集合间的底层实现之一,如果一个有序集合包含的元素数量较多,又或者有序集合中的元素的成员是较长的字符串时,redis 就会使用跳跃表作为有序号集合的底层实现。

2. 跳跃表的实现 :

   redis 的跳跃表由 redis.h/zskiplistNode和redis.h/zskiplist 两个结构定义,其中 zskiplistNode 结构用于表示跳跃表节点,而 zskiplist 结构用于保存跳跃表节点的相关信息。

跳跃表.jpg

   1. 位于图片最左侧的是 zskiplist 结构：
     header : 执向跳跃表的表头节点
     tail : 执行跳跃表的表尾节点
     level : 记录目前跳跃表内,层数最大的几点的层数
     length : 记录跳跃表的长度
   2. 位于右侧的 4 个是 zskiplistNode :
     层 : L1 ....L32 代表的是层数,每层都带有两个属性: 前进指针和跨度 。 前进指针用于访问表尾方向的其他节点，而跨度则记录了前进指针所指向的节点和当前指针的举例。 图上 连线带有数字的箭头代表的是前进指针，而数字就是跨度 。
     后退指针： 节点中 BW 字样代表后退指针。他指向为与当前节点的前一个节点，后退指针在程序从表尾向表头遍历时使用 。
     分值： 各个节点中的 1.0 2.0 3.0 是节点所保存的分值。在跳跃表中，节点按各自所保存的分值从小到大排列。
     成员对象： 各个节点中的 01 ，02 ，03 是节点所保存的成员对象。