redis相关知识(六)

视频的容积

　　1.7.1.3 SkipList(跳跃表)操作
　　1) An empty SkipList

　　2) Finding an element with key x

12345678910111213p=topWhile(1){while (p->next->key < x ) p=p->next;If (p->down == NULL ) return p->nextp=p->down ;}　　Observe that we return x, if exists, or succ(x) if x is not in the SkipList
　　3) Inserting new element X
　　
　　Determine k the number of levels in which x participates (explained later)
　　Do find(x), and insert x to the appropriate places in the lowest k levels. (after the elements at which the search path turns down or terminates)
　　Example – inserting 119. k=2
　　If k is larger than the current number of levels, add new levels (and update top)
　　Example – inser(119) when k=4

　　Determining k
　　k – the number of levels at which an element x participate.
　　Use a random function OurRnd() — returns 1 or 0 (True/False) with equal probability.
　　k=1 ;
　　While( OurRnd() ) k++ ;
　　Deleteing a key x
　　Find x in all the levels it participates, and delete it using the standard ‘delete from a linked list’ method.
　　If one or more of the upper levels are empty, remove them (and update top)
　　
　　Facts about SkipList
　　The expected number of levels is O( log n )
　　(here n is the numer of elements)
　　The expected time for insert/delete/find is O( log n )
　　The expected>n )
1.7.2 redis SkipList 实现　　/* ZSETs use a specialized version of Skiplists */
12345678910111213141516171819202122232425262728293031323334353637383940414243typedef struct zskiplistNode{robj *obj;double score;struct zskiplistNode *backward;struct zskiplistLevel{struct zskiplistNode *forward;unsigned int span;} level[];} zskiplistNode;typedef struct zskiplist{struct zskiplistNode *header, *tail;unsigned long length;int level;} zskiplist;typedef struct zset{dict *dict;zskiplist *zsl;} zset;