跳表(skiplist)学习笔记

    这段时间公司做了个项目，在项目里面用到了redis,爱学习的我又一次翻出了redis的源代码，从头开始看了起来(没看完，哈哈~~)，在这一次阅读中把redis的五大数据结构的代码给看了一遍，对于我这么一个菜鸟来说收获颇多，比如他的hash，list结构都没有使用我们平常使用的双向链表，而是使用一种非常节省内存的方式来实现了链表(zipmap和ziplist)，还有zset就使用了跳表，其实levelDB也有使用跳表。

    Skip List是在有序List(链表)数据结构的基础上的扩展，解决了有序链表结构查找特定值困难的问题，使用Skip List，可以使得在一个有序链表里查找特定值的时间复杂度为O(logn)，他是一种可以代替平衡树的数据结构。Skip lists应用概率保证平衡，平衡树采用严格的旋转(比如平衡二叉树有左旋右旋)来保证平衡，因此Skip list比较容易实现，而且相比平衡树有着较高的运行效率。 其实现原理是链表中每一个元素都有N层(N为随机数，并且1<=N

    

     #include

     #include

     #include

    typedef int key_t;

     typedef int value_t;

     typedef struct node_t

     key_t key;

     value_t value;

     struct node_t *forward[];

     } node_t;

    typedef struct skiplist

     int level;

     int length;

     node_t *header;

     } list_t;

    #define MAX_LEVEL 16

     #define SKIPLIST_P 0.25

    node_t* slCreateNode(int level, key_t key, value_t value)

     node_t *n = (node_t *)malloc(sizeof(node_t) + level * sizeof(node_t*));

     if(n == NULL) return NULL;

     n->key = key;

     n->value = value;

     return n;

    list_t* slCreate(void)

     list_t *l = (list_t *)malloc(sizeof(list_t));

     int i = 0;

     if(l == NULL) return NULL;

     l->length = 0;

     l->level = 0;

     l->header = slCreateNode(MAX_LEVEL - 1, 0, 0);

     for(i = 0; i < MAX_LEVEL; i++)

     l->header->forward[i] = NULL;

     return l;

    int randomLevel(void)

     int level = 1;

     while ((rand()&0xFFFF) < (SKIPLIST_P * 0xFFFF))

     level += 1;

     return (levelheader;

     int i;

     for(i = list->level - 1; i >= 0; i-)

     while(p->forward[i] && (p->forward[i]->key forward[i]->key == key){

     return &p->forward[i]->value;

     p = p->forward[i];

     return NULL;

    int slDelete(list_t *list, key_t key)

     node_t *update[MAX_LEVEL];

     node_t *p = list->header;

     node_t *last = NULL;

     int i = 0;

     for(i = list->level - 1; i >= 0; i-){

     while((last = p->forward[i]) && (last->key < key)){

     p = last;

     update[i] = p;

     if(last && last->key == key){

     for(i = 0; i < list->level; i++){

     if(update[i]->forward[i] == last){

     update[i]->forward[i] = last->forward[i];

     free(last);

     for(i = list->level - 1; i >= 0; i-){

     if(list->header->forward[i] == NULL){

     list->level-;

     list->length-;

     }else{

     return -1;

     return 0;

    int slInsert(list_t *list, key_t key, value_t value)

     node_t *update[MAX_LEVEL];

     node_t *p, *node = NULL;

     int level, i;

     p = list->header;

     for(i = list->level - 1; i >= 0; i-){

     while((node = p->forward[i]) && (node->key < key)){

     p = node;

     update[i] = p;

     if(node && node->key == key){

     node->value = value;

     return 0;

     level = randomLevel();

     if (level > list->level)

     for(i = list->level; i < level; i++){

     update[i] = list->header;

     list->level = level;

     node = slCreateNode(level, key, value);

     for(i = 0; i < level; i++){

     node->forward[i] = update[i]->forward[i];

     update[i]->forward[i] = node;

     list->length++;

     return 0;

    int main(int argc, char **argv)

     list_t *list = slCreate();

     node_t *p = NULL;

     value_t *val = NULL;

     for(int i = 1; i header->forward[0];

     for(int i = 0; i < list->length; i++){

     printf(“%d,%d\\n”, p->key, p->value);

     p = p->forward[0];

     getchar();

     return 0;

建议继续学习：