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
http://www.searchtb.com/wp-content/uploads/2011/04/Image011760.jpg
//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
http://www.searchtb.com/wp-content/uploads/2011/04/Image011770.jpg
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
http://www.searchtb.com/wp-content/uploads/2011/04/Image011780.jpg
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
http://www.searchtb.com/wp-content/uploads/2011/04/Image011790.jpg
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.
http://www.searchtb.com/wp-content/uploads/2011/04/Image011800.jpg
页:
[1]