Redis学习笔记（四） 跳跃表与整数集合

（一）跳跃表

跳跃表是一种有序的数据结构，它通过每个节点中维持多个指向其他节点的指针，从而达到快速访问节点的目的。

Redis使用跳跃表作为有序集合键的底层实现之一，如果一个有序集合包含的元素数量比较多，或者有序集合中元素的成员是比较长的字符串时，Redis就会使用跳跃表作为有序集合键的底层实现。

Redis中的两个地方用到了跳跃表，一个是实现有序集合键，另一个是在集群节点中用作内部数据结构。

Redis的跳跃表由zskiplistnode 与 zskiplist 两个结构定义。其中zskiplistNode 结构用于标识跳跃表节点，zskiplist结构用于保存跳跃表节点的相关信息（表头、表尾节点、节点数量等）。

zskiplistNode

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

层中包含多个元素，每个元素是指向其他节点的指针，通过这些层可以加快访问其他节点的速度，层越多，访问其他节点的速度越快。没增加一个跳跃节点，程序根据幂次定律（越大的数出现概率越小）生成1-32之间的值作为层高。

每层都有一个指向表尾方向的前进指针，作为表头向表尾方向访问节点。

层中的跨度用于记录两个节点之间的距离。

后退指针则只能一次跨1个节点进行访问。

跳跃表的排序是按照所有节点的分值来排序的。

节点中的对象则是保存了一个SDS的字符串。

同一个跳跃表的对象必须唯一，但分值可以重复。（相同分数，成员小的靠前排）。

跳跃表zskiplist

typedef struct zskiplist{
    struct skiplistNode *header,*tail;//表头节点与表尾节点
    unsigned long length;//表中节点的数量
    int level;//表中层数最大的节点的层数(表头不计算在内)
} zskiplist;

（二）整数集合

整数集合是集合键的底层实现之一，当一个集合只包含整数值元素，并且集合的元素数量不多时，Redis就会使用整数集合作为集合键的底层实现，并且保证集合中不会出现重复元素。

intset

typedef struct intset{
    uint32_t encoding;//编码方式
    uint32_t length;//集合包含的元素数量。
    int8_t contents[];//保存元素的数组 
} intset;

contents数组是这个数集合的底层实现：整数集合的每个元素都是contents数组的一个数组项，各个项的数组中按值的大小从小到大有序地排列，并且数组中不包含任何重复项。

升级

当我们要将一个新元素添加到整数集合里面时，并且新元素类型比整数集合现有的所有元素类型都长时，整数集合需要先进性升级，然后才能将新的元素添加到整数集合中。

根据新元素的类型，扩展整数集合底层数组的空间大小，并为新元素分配空间。

将底层数组现有的所有元素都转换为与新元素相同的类型，并将类型转换后的元素放置到正确位置上，而且在放置元素过程中，需要继续维持底层数组的有序性质不变。

将新元素添加到底层数组里面。

修改整数集合encoding属性。

因为每次向整数集合添加新元素都有可能引起升级，而每次升级都需要将底层数组中已有的所有元素进行类型转换，所以向整数集合中添加新元素的时间复杂度为O(N);

---- end ----

每天学一点，总会有收获。

说明：尊重作者知识产权，文中内容参考《Redis设计与实现》，仅在此做学习与大家分享。