redis相关知识(五)

　　1.7 zset 结构
　　首先，介绍一下 skip list 的概念，然后再分析 zset 的实现.
1.7.1 Skip List 介绍1.7.1.1 有序链表　　1) Searching a key in a Sorted linked list

//Searching an element xcell *p =head ;while (p->next->key < x ) p=p->next ;return p ;　　Note: we return the element proceeding either the element containing x, or the smallest element with a key larger than x (if x does not exists)
　　2) inserting a key into a Sorted linked list

1234567891011//To insert 35 -p=find(35);CELL *p1 = (CELL *) malloc(sizeof(CELL));p1->key=35;p1->next = p->next ;p->next = p1 ;　　3) deleteing a key from a sorted list

123456789//To delete 37 -p=find(37);CELL *p1 =p->next;p->next = p1->next ;free(p1);1.7.1.2 SkipList(跳跃表)定义　　SKIP LIST : A data structure for maintaing a set of keys in a sorted order.
　　Consists of several levels.
　　All keys appear in level 1
　　Each level is a sorted list.
　　If key x appears in level i, then it also appears in all levels below i

　　An element in level i points (via down pointer) to the element with the same key in the level below.
　　In each level the keys and appear. (In our implementation, INT_MIN and INT_MAX
　　Top points to the smallest element in the highest level.