rediszset底层数据结构
zset底层存储结构
 zset底层的存储结构包括ziplist或skiplist，在同时满⾜以下两个条件的时候使⽤ziplist，其他时候使⽤skiplist，两个条件如下：
有序集合保存的元素数量⼩于128个
有序集合保存的所有元素的长度⼩于64字节
 当ziplist作为zset的底层存储结构时候，每个集合元素使⽤两个紧挨在⼀起的压缩列表节点来保存，第⼀个节点保存元素的成员，第⼆个元素保存元素的分值。
 当skiplist作为zset的底层存储结构的时候，使⽤skiplist按序保存元素及分值，使⽤dict来保存元素和分值的映射关系。
ziplist数据结构
 ziplist作为zset的存储结构时，格式如下图，细节就不多说了，我估计⼤家都看得懂，紧挨着的是元素memeber和分值socore，整体数据是有序格式。
zset ziplist结构
skiplist数据结构
 skiplist作为zset的存储结构，整体存储结构如下图，核⼼点主要是包括⼀个dict对象和⼀个skiplist对象。dict保存key/value，key为元素，value为分值；skiplist保存的有序的元素列表，每个元素包括元素和分值。两种数据结构下的元素指向相同的位置。
zset skiplist结构
skiplist的源码格式
 zset包括dict和zskiplist两个数据结构，其中dict的保存key/value，便于通过key(元素)获取score(分值)。zskiplist保存有序的元素列表，便于执⾏range之类的命令。
/*
* 有序集合
*/
typedef struct zset {
// 字典，键为成员，值为分值
// ⽤于⽀持 O(1) 复杂度的按成员取分值操作
dict *dict;
// 跳跃表，按分值排序成员
// ⽤于⽀持平均复杂度为 O(log N) 的按分值定位成员操作
// 以及范围操作
zskiplist *zsl;
} zset;
zskiplist作为skiplist的数据结构，包括指向头尾的header和tail指针，其中level保存的是skiplist的最⼤的层数。
/*
* 跳跃表
*/
typedef struct zskiplist {
// 表头节点和表尾节点
struct zskiplistNode *header, *tail;
// 表中节点的数量
unsigned long length;
// 表中层数最⼤的节点的层数
int level;
} zskiplist;
skiplist跳跃列表中每个节点的数据格式，每个节点有保存数据的robj指针，分值score字段，后退指针backward便于回
溯，zskiplistLevel的数组保存跳跃列表每层的指针。
/*
* 跳跃表节点
*/
typedef struct zskiplistNode {
// 成员对象
robj *obj;
// 分值
double score;
// 后退指针
struct zskiplistNode *backward;
// 层
struct zskiplistLevel {
// 前进指针
struct zskiplistNode *forward;
// 跨度
unsigned int span;
} level[];
} zskiplistNode;
zset存储过程
 zset的添加过程我们以zadd的操作作为例⼦进⾏分析，整个过程如下：
解析参数得到每个元素及其对应的分值
查key对应的zset是否存在不存在则创建
如果存储格式是ziplist，那么在执⾏添加的过程中我们需要区分元素存在和不存在两种情况，存在情况下先删除后添加；不存在情况下则添加并且需要考虑元素的长度是否超出限制或实际已有的元素个数是否超过最⼤限制进⽽决定是否转为skiplist对象。
如果存储格式是skiplist，那么在执⾏添加的过程中我们需要区分元素存在和不存在两种情况，存在的情况下先删除后添加，不存在情况下那么就直接添加，在skiplist当中添加完以后我们同时需要更新dict的对象。
void zaddGenericCommand(redisClient *c, int incr) {
static char *nanerr = "resulting score is not a number (NaN)";
robj *key = c->argv[1];
robj *ele;
robj *zobj;
robj *curobj;
double score = 0, *scores = NULL, curscore = 0.0;
int j, elements = (c->argc-2)/2;
int added = 0, updated = 0;
// 输⼊的 score - member 参数必须是成对出现的
if (c->argc % 2) {
addReply(c,shared.syntaxerr);
return;
}
// 取出所有输⼊的 score 分值
scores = zmalloc(sizeof(double)*elements);
for (j = 0; j < elements; j++) {
if (getDoubleFromObjectOrReply(c,c->argv[2+j*2],&scores[j],NULL)            != REDIS_OK) goto cleanup;
}
// 取出有序集合对象
zobj = lookupKeyWrite(c->db,key);
if (zobj == NULL) {
// 有序集合不存在，创建新有序集合
if (server.zset_max_ziplist_entries == 0 ||
server.zset_max_ziplist_value < sdslen(c->argv[3]->ptr))
{
zobj = createZsetObject();
} else {
zobj = createZsetZiplistObject();
}
// 关联对象到数据库
dbAdd(c->db,key,zobj);
} else {
// 对象存在，检查类型
if (zobj->type != REDIS_ZSET) {
addReply(c,shared.wrongtypeerr);
goto cleanup;
}
}
// 处理所有元素
for (j = 0; j < elements; j++) {
score = scores[j];
// 有序集合为 ziplist 编码
if (zobj->encoding == REDIS_ENCODING_ZIPLIST) {
unsigned char *eptr;
/
/ 查成员
ele = c->argv[3+j*2];
if ((eptr = zzlFind(zobj->ptr,ele,&curscore)) != NULL) {
// 成员已存在
// ZINCRYBY 命令时使⽤
if (incr) {
score += curscore;
if (isnan(score)) {
addReplyError(c,nanerr);
goto cleanup;
}
}
// 执⾏ ZINCRYBY 命令时，
// 或者⽤户通过 ZADD 修改成员的分值时执⾏
if (score != curscore) {
// 删除已有元素
zobj->ptr = zzlDelete(zobj->ptr,eptr);
// 重新插⼊元素
zobj->ptr = zzlInsert(zobj->ptr,ele,score);
// 计数器
server.dirty++;
updated++;
}
} else {
// 元素不存在，直接添加
zobj->ptr = zzlInsert(zobj->ptr,ele,score);
// 查看元素的数量，
// 看是否需要将 ZIPLIST 编码转换为有序集合
if (zzlLength(zobj->ptr) > server.zset_max_ziplist_entries)                    zsetConvert(zobj,REDIS_ENCODING_SKIPLIST);
// 查看新添加元素的长度
// 看是否需要将 ZIPLIST 编码转换为有序集合
if (sdslen(ele->ptr) > server.zset_max_ziplist_value)
zsetConvert(zobj,REDIS_ENCODING_SKIPLIST);
server.dirty++;
added++;
}
// 有序集合为 SKIPLIST 编码
} else if (zobj->encoding == REDIS_ENCODING_SKIPLIST) {            zset *zs = zobj->ptr;
zskiplistNode *znode;
dictEntry *de;
// 编码对象
ele = c->argv[3+j*2] = tryObjectEncoding(c->argv[3+j*2]);
// 查看成员是否存在
de = dictFind(zs->dict,ele);
if (de != NULL) {
// 成员存在
// 取出成员
curobj = dictGetKey(de);
// 取出分值
curscore = *(double*)dictGetVal(de);
// ZINCRYBY 时执⾏
if (incr) {
redis支持的数据结构score += curscore;
if (isnan(score)) {
addReplyError(c,nanerr);
goto cleanup;
}
}
// 执⾏ ZINCRYBY 命令时，
// 或者⽤户通过 ZADD 修改成员的分值时执⾏

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。