Redis深入之路（四）

跳跃表（Skip List）

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

在Redis中的应用：

作为有序集合的底层实现。在集群节点中用作内部数据结构。

跳跃表节点

redis.h/zskiplistNode

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

跳跃表

redis.h/zskiplist

typedef struct zskiplist { // 表头节点和表尾节点 structz skiplistNode *header, *tail; // 表中节点数量 unsigned long length; // 层数 int level; } zskiplist;

重点

跳跃表是有序结合俄底层实现之一。Redis跳跃表由跳跃表节点：zskiplistNode 和 跳跃表 zskiplist 两个结构组成；其中 zskiplistNode 保存信息包括：后退指针、分值、成员对象、层级数组（zskiplistLevel包括：前进指针、跨度）；zskiplist 保存信息包括：表头节点、表尾节点、表中节点数量、层数每个跳跃表节点的层高都是 1 到 32 之间的随机数在同一个跳跃表中，多个节点分值可以相同，但成员对象必须唯一。跳跃表中节点按照分值大小进行排序，如果份分值大小相同，则按照成员对象（obj）的大小进行排序。