Redis的设计与实现 跳跃表

一 跳跃表概念

跳跃表是一个有序数据结构，他通过每个节点中维持多个指向其他节点的指针，从而达到快速访问节点的目的，大部分情况下跳跃表的效率会和平衡树接近，但是他的实现简单，所以很多都使用了跳跃表，Redis使用跳跃表作为他的有序集合键(zset)的底层实现以及集群节点中用作内部的数据结构

二 数据结构

三 跳跃表的实现

Redis由zskiplistNode和zskiplist两个数据结构定义

1. zskiplist

   他的数据结构

   

   • header 指向跳跃表的表头节点
   • tail 指向跳跃表的表尾节点
   • level 记录跳跃表内层数最大的那个节点的层数
   • length 记录跳跃表节点的数量（表头节点不计入）
   • 代码

     typedef struct zskiplist {
     // 表头节点和表尾节点
     struct zskiplistNode header, tail;
     // 表中节点的数量
     unsigned long length;
     // 表中层数最大节点的层数
     int level;
     } zskiplist;

2. zskiplistNode

   他的数据结构

   

• 层（对应L1 L2 L3...） 每个层包含两个属性，前进指针和跨度，前进指针用来访问表尾节点的其他节点，跨度用来记录前进指针所指向节点和当前节点的距离
• 后退指针 节点中使用BW来标记后退指针，他指向当前节点的前一个节点，从表尾到表头遍历时使用
• 分值 如图中，各个节点保存的1.0 2.0 3.0 就是各个节点的分值，节点按照各个保存的分值从大到小排列（这里保证了zset的有序）

• 成员变量 节点中所保存的 o1 o2 o3 就是所保存的成员变量,比如

   
   jedis.zadd("myzset", 98, "tom1");
   jedis.zadd("myzset", 99, "peter");
   jedis.zadd("myzset", 33, "james");
   

  这里面"tom1"就是成员变量，98就是分值

• 代码

    typedef struct zskiplistNode {  
        //成员变量
        robj *obj;  
        // 分值
        double score;  
        // 后退指针
        struct zskiplistNode *backward;  
        
        // 层
        struct zskiplistLevel {  
            // 前进指针
            struct zskiplistNode *forward;  
            
            // 跨度
            unsigned int span;  
        } level[];  
    } zskiplistNode;  
    

四 跳跃表的遍历及插入

1. 遍历

   首先访问跳跃表表头节点，获取第一个元素L1，再通过L1去查找其他元素上的跨度最短的L1，如果找到了末尾，末尾的L1节点指向null那么遍历结束，得到L1的分值以及成员变量。

2. 插入
   以依次插入50、7、25为例子

   • 初始化一个层数为1的节点
   • 插入50时，先通过一个函数生成一个随机数表示50占据的层数，即2。从顶层开始遍历，由于下一个节点为null，直接插入。
   • 比较层数，因为新节点有两层，那么我们需要将头节点的第二层指向新节点。并把当前层数更新为2。
   • 紧接着，插入7，同样通过一个函数生成一个随机数表示7占据的层数，这里为1。
   • 从顶层开始遍历，由于头部节点顶层指向50，7和50比较，可以得出7要插入的位置在头部到50这个位置，此时我们取得头部节点。
   • 由于从顶层位置开始找其，此时层数为第二层，而7这个节点只有一层，我们以取得的头部为出发点，从头部的第一层开始找起。
   • 由于第一层的头部节点指向50，7和50比较，再次得出7要插入的位置在头部到50这个位置。
   • 此时，比较7的层数和头部位置所在的层数（都是第一层），建立关联，将7和头部位置第一曾做关联，然后7的第一层指向50的第一层。
   • 由于7只有一层，遍历结束。
   • 同理，插入25，不过这里插入25后，由于25的节点有三层，比当前的最大层数2大，所以记得要更新当前最大层数。