Redis zset内部实现

redis对象 Redis对象由redisObject结构体表示 。
typedef struct redisObject {unsigned type:4;// 对象的类型,包括 /* Object types */unsigned encoding:4;// 底部为了节省空间,一种type的数据,可以采用不同的存储方式unsigned lru:REDIS_LRU_BITS; /* lru time (relative to server.lruclock) */int refcount;// 引用计数void *ptr;} robj;【Redis zset内部实现】Redis中的每个键值对的键和值都是一个redisObject 。共有五种类型的对象:字符串(String)、列表(List)、哈希(Hash)、集合(Set)、有序集合(SortedSet),源码server.h如下定义:
/* The actual Redis Object */#define OBJ_STRING 0#define OBJ_LIST 1 #define OBJ_SET 2#define OBJ_ZSET 3#define OBJ_HASH 4每种类型的对象至少都有两种或以上的编码方式;可以在不同的使用场景上优化对象的使用场景 。用TYPE命令可查看某个键值对的类型
对象编码 Redis目前使用的编码方式:
/* Objects encoding. Some kind of objects like Strings and Hashes can be * internally represented in multiple ways. The 'encoding' field of the object * is set to one of this fields for this object.*/#define OBJ_ENCODING_RAW/* Raw representation */ 简单动态字符串#define OBJ_ENCODING_INT/* Encoded as integer */ 整数#define OBJ_ENCODING_HT/* Encoded as hash table */ 字典#define OBJ_ENCODING_ZIPLIST/* Encoded as ziplist */ 压缩列表#define OBJ_ENCODING_INTSET/* Encoded as intset */ 整数集合#define OBJ_ENCODING_SKIPLIST/* Encoded as skiplist */ 跳跃表#define OBJ_ENCODING_EMBSTR/* Embedded sds string encoding */ embstr编码的简单动态字符串#define OBJ_ENCODING_QUICKLIST/* Encoded as linked list of ziplists */本质上,Redis就是基于这些数据结构而构造出一个对象存储系统 。redisObject结构体有个ptr指针,指向对象的底层实现数据结构,encoding属性记录对象所使用的编码,即该对象使用什么数据结构作为底层实现 。
zset介绍 有序集合对象的编码可以是ziplist或者skiplist 。同时满足以下条件时使用ziplist编码:
元素数量小于128个 所有member的长度都小于64字节 以上两个条件的上限值可通过zset-max-ziplist-entries和zset-max-ziplist-value来修改 。
ziplist编码的有序集合使用紧挨在一起的压缩列表节点来保存,第一个节点保存member,第二个保存score 。ziplist内的集合元素按score从小到大排序,score较小的排在表头位置 。
skiplist编码的有序集合底层是一个命名为zset的结构体,而一个zset结构同时包含一个字典和一个跳跃表 。跳跃表按score从小到大保存所有集合元素 。而字典则保存着从member到score的映射,这样就可以用O(1)的复杂度来查找member对应的score值 。虽然同时使用两种结构,但它们会通过指针来共享相同元素的member和score,因此不会浪费额外的内存 。
skiplist介绍 跳表(skip List)是一种随机化的数据结构,基于并联的链表,实现简单,插入、删除、查找的复杂度均为O(logN) 。简单说来跳表也是链表的一种,只不过它在链表的基础上增加了跳跃功能,正是这个跳跃的功能,使得在查找元素时,跳表能够提供O(logN)的时间复杂度 。
先来看一个有序链表,如下图(最左侧的灰色节点表示一个空的头结点):

Redis zset内部实现

文章插图
 
在这样一个链表中,如果我们要查找某个数据,那么需要从头开始逐个进行比较,直到找到包含数据的那个节点,或者找到第一个比给定数据大的节点为止(没找到) 。也就是说,时间复杂度为O(n) 。同样,当我们要插入新数据的时候,也要经历同样的查找过程,从而确定插入位置 。
假如我们每相邻两个节点增加一个指针,让指针指向下下个节点,如下图:
Redis zset内部实现

文章插图
 
这样所有新增加的指针连成了一个新的链表,但它包含的节点个数只有原来的一半(上图中是7, 19, 26) 。现在当我们想查找数据的时候,可以先沿着这个新链表进行查找 。当碰到比待查数据大的节点时,再回到原来的链表中进行查找 。比如,我们想查找23,查找的路径是沿着下图中标红的指针所指向的方向进行的:
Redis zset内部实现

文章插图
 
  1. 23首先和7比较,再和19比较,比它们都大,继续向后比较 。
  2. 但23和26比较的时候,比26要小,因此回到下面的链表(原链表),与22比较 。
  3. 23比22要大,沿下面的指针继续向后和26比较 。23比26小,说明待查数据23在原链表中不存在,而且它的插入位置应该在22和26之间 。在这个查找过程中,由于新增加的指针,我们不再需要与链表中每个节点逐个进行比较了 。需要比较的节点数大概只有原来的一半 。


    推荐阅读