博客

跳跃列表（skipList）、压缩列表(zipList)和快速列表（quicklist）都是Redis底层重要的数据结构。

跳跃列表（skipList）

Redis使用跳跃表作为有序集合键的底层实现之一，通过在每个节点中维持多个指向其他节点的指针，从而达到快速访问节点的目的，如果一个有序集合包含的元素数量比较多，

又或者有序集合中元素的成员（member）是比较长的字符串时，Redis就会使用跳跃表来作为有序集合键的底层实现。

Redis只在两个地方用到了跳跃表，

一个是实现有序集合键，另一个是在集群节点中用作内部数据结构，除此之外，跳跃表在Redis里面没有其他用途。

C语言代码实现：

typedef struct zskiplistNode {
	//用于存储字符串类型的数据
    robj *obj;
    //用于存储排序的分值
    double score;
    //回退指针
    struct zskiplistNode *backward;
    struct zskiplistLevel {
    	//前进指针
        struct zskiplistNode *forward;
        //跨度
        unsigned int span;
    } level[];
} zskiplistNode;

压缩列表(zipList)

压缩列表本质上就是一个字节数组，是Redis为了节约内存而设计的一种线性数据结构，可以包含多个元素，每个元素可以是一个字节数组或一个整数。Redis的有序集合、散列和列表都直接或者间接使用了压缩列表。

当有序集合或散列表的元素个数比较少，且元素都是短字符串时，Redis便使用压缩列表作为其底层数据存储结构。当元素数量大于128个，所有元素长度大于64字节时，Redis使用快速链表（quicklist）数据结构存储，而快速链表就是双向链表与压缩列表的组合。

快速列表（quicklist）

快速列表是Redis中List的底层数据结构，它实质上是双向链表与压缩列表的组合，每个节点的实际数据存储结构为ziplist。这种结构的主要优势在于节省存储空间，同时也保证了数据读写性能。

C语言代码实现

typedef struct quicklist{
	quicklistNode *head;
	quicklistNode *tail;
	unsigned long count;//快速列表中元素总数
	unsigned long len;//快速列表中Node（节点）个数
	int fill : 16;//每个quicklistNode中ziplist长度
}quicklist;