redis中有序集合zset是用跳跃表实现的，所以今天学习了一下跳跃表。本文主要讲redis中跳跃表的实现。

一、结构

跳跃表由两个结构组成，zskiplist和zskiplistnode，zskiplist用于保存跳跃表相关节点的信息，zskiplistnode用于保存跳跃表节点。

1. zskiplist以下几个属性

    a. header：指向跳跃表头的节点。

    b. tail：指向跳跃表尾的节点。

    c. level：记录目前跳跃表内，层数最大的那个节点的层数（表头节点的层数不计算在内）。

    d. length：记录跳跃表的长度，也即是，跳跃表目前包含节点的数量（表头节点不计算在内）。

2. zskiplistnode有以下几个属性

    a. level：表示跳跃表节点的各个层。每个层又有两个属性，forward(前进)指针和跨度。

    b. backward：表示指向后一个节点(也即指向表头方向)的后退指针。

    c. score：分值，在整个表中，分值可以重复。

    d. obj：成员对象，在整个表中，成员对象不可以重复。

跳跃表结构图

注意：

1). 跳跃表各个 zskiplistnode的排序方式是根据分值大小来的，最小的排左边，依次往右排。如果分值相同，那么会成员对象大小来排(成员对象保存着一个SDS).

2). 表头节点层数为32，其它节点定义层数的规则是根据幂次定律(power law，越大的数出现的概率越小)来的，生成一个大小介于1-32之间的数。

二、应用

跳跃表查找数据步骤图

如图，要查找分值为41的节点

1. 先找到最高层的节点23，与其比较，看23是否比要查找的数字小，是则将指针(因为redis底层由C语言实现)指向它，否则降层(指针下移)再比较。此处将指针指向23表示的节点。

2. 发现L6, L5, L4都没有其他节点，就降层到L3层，与L3层指向的41分值表示的节点进行比较，发现相等，于是就找到了要查找的数据。

注意：如果要插入数据，找到相应的位置后，生成节点，根据幂次定律随机生成层数就可以了；如果是要删除数据，那么会将整个层都删掉。

                                                                                                                                   2019-06-16