redis相关知识(七)

760176104

　　zset 的实现用到了2个数据结构: hash_table 和 skip list (跳跃表),其中 hash table 是使用 redis 的 dict 来实现的,主要是为了保证查询效率为 O(1),而 skip list (跳跃表) 是用来保证元素有序并能够保证 INSERT 和 REMOVE 操作是 O(logn)的复杂度。
　　1) zset初始化状态
　　createZsetObject函数来创建并初始化一个 zset
12345678910111213141516171819robj *createZsetObject(void){zset *zs = zmalloc(sizeof(*zs));robj *o;zs->dict = dictCreate(&zsetDictType,NULL);zs->zsl = zslCreate();o = createObject(REDIS_ZSET,zs);o->encoding = REDIS_ENCODING_SKIPLIST;return o;}　　zslCreate()函数用来创建并初如化一个 skiplist。 其中，skiplist 的 level 最大值为 ZSKIPLIST_MAXLEVEL=32 层。
12345678910111213141516171819202122232425262728293031zskiplist *zslCreate(void){int j;zskiplist *zsl;zsl = zmalloc(sizeof(*zsl));zsl->level = 1;zsl->length = 0;zsl->header = zslCreateNode(ZSKIPLIST_MAXLEVEL,0,NULL);for (j = 0; j < ZSKIPLIST_MAXLEVEL; j++) {zsl->header->level[j].forward = NULL;zsl->header->level[j].span = 0;}zsl->header->backward = NULL;zsl->tail = NULL;return zsl;}

　　2) ZADD myzset 1 “one”
　　ZADD 命令格式：
　　ZADD key score member

• 　　根据 key 从 redisDb 进行查询，返回 zset 对象。
  
• 　　以 member 作为 key,score 作为 value ，向 zset的 dict 进行中插入;
  
• 　　如果返回成功，表明 member 没有在 dict 中出现过，直接向 skiplist 进行插入。
  
• 　　如果步骤返回失败，表明以 member 已经在 dict中出现过，则需要先从 skiplist 中删除，然后以现在的 score 值重新插入。
  

　　3) ZADD myzset 3 “three”

　　4) ZADD myzset 2 “two”

　　redis学习系列
　　淘宝的redis内存分析
　　http://www.searchtb.com/2011/05/redis-storage.html
　　淘宝关于zipmap和skiplist的分析
　　http://rdc.taobao.com/blog/cs/?tag=redis
　　redis各个点的分析,值得一看!!!
　　http://www.petermao.com/category/redis
　　协议,主从复制,事件模型,持久化
　　http://www.hoterran.info/redis_protocol
　　http://www.hoterran.info/redis_replication
　　http://www.hoterran.info/redis_eventlibrary
　　http://www.hoterran.info/redis_persistence
　　http://pauladamsmith.com/articles/redis-under-the-hood.html#tcp-socket
　　http://www.cnblogs.com/liping13599168/category/293173.html
　　http://www.cnblogs.com/huli/archive/2010/06/06/1752778.html
　　http://pauladamsmith.com/articles/redis-under-the-hood.html