Redis的设计与原理(三)

叁歲伎倆 2021-12-10 12:21 245阅读 0赞

## 数据结构与对象——跳跃表 ##

跳跃表是一种有序的数据结构，它通过在每个节点中维持多个指向其他节点的指针，从而达到快速访问节点的目的。Redis使用跳跃表作为有序集合键的底层实现之一，如果一个有序集合包含的元素数量比较多，又或者有序集合中元素的成员是比较长的字符串时，Redis就会使用跳跃表来作为有序集合键的底层实现。跳跃表是什么就不再详细介绍，需要的可以去看看数据结构中的跳跃表概念。跳跃表节点的代码

### 跳跃节点： ###

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

**层：**  
跳跃表节点的level数组可以包含多个元素，每个元素都包含一个指向其他节点的指针，程序可以通过这些层来加快访问其他节点的速度，一般来说，层的数量越多，访问其他节点的速度就越快。  
**前进指针：**  
每个层都有一个指向表尾方向的前进指针，用于从表头向表尾方向访问节点。  
**跨度：**  
用来记录两个节点之间的距离。  
**后退指针：**  
用于从表尾向表头方向访问节点，和前进指针不同的是，每个节点只有一个后退指针，即每次后退只能退到前一个节点。  
**分值和成员：**  
分值是一个double类型的浮点数，跳跃表中的所有节点都按分值从小到大来排序。  
成员对象时一个指针，它指向一个字符串对象，而字符串对象则保存着一个SDS值。

### 跳跃表： ###

仅靠多个跳跃节点就可以构成一个跳跃表，结构如下：

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