深入浅出Redis 跳表的实现原理（redis的跳表实现原理）

深入浅出：Redis 跳表的实现原理

Redis 是一款高性能的开源内存数据存储系统。在 Redis 中，跳表（Skip List）被广泛应用于有序集合的实现中。今天，我们将深入浅出地了解 Redis 跳表的实现原理，帮助更好地理解 Redis 底层数据结构。

跳表的定义

跳表是一种可以支持快速查找、插入、删除的有序数据结构。跳表由于具有高效的查找性能、容易实现等优点，成为了 Redis 内部实现有序集合的一种常用数据结构。

跳表的结构

跳表的整体结构是一个多层的链表，每一层都是一个有序序列，每个节点除了记录本节点的值和指向下一个节点的指针外，还会记录该节点在高层链表中的指针。以下是一个三层跳表的示意图：

![skip_list](https://user-images.githubusercontent.com/62681965/133344905-0f814a59-86d2-4422-bc8b-23c77edc4213.png)

跳表的节点定义如下：

“`c

typedef struct skipListNode {

int score;

struct skipListNode *forward[1];

}skipListNode;


参数说明：

score：节点的分值，用于排序；
forward：前向指针数组，在每一层都指向下一个节点，共计 n 层，数组大小为 forward[0] 至 forward[n]；
跳表查询

当跳表中存在 n 个节点时，对其中分值为 x 的节点进行查询，遍历的次数不超过 logn 代价最低。 执行跳表查询如下：

1.初始化指针
　　从最高层开始，将指针指向对应节点。
2.开始查找
　　从最高层开始，如果下一个节点的分值比目标分值小，就继续遍历下一个节点，直到找到查询的分值或者下一个节点的分值比目标分值大。
3.下移指针
　　如果下一个节点的分值比目标分值大，就将指针下移一层，并重新执行步骤2。
跳表插入

在跳表中插入一个新节点时，需要找到插入位置并插入节点。插入节点有 50% 的概率会在某一层被插入，而在下一级序列不出现。执行跳表插入的步骤如下：

1. 通过查询找到待插入节点的位置，并预先设置层数。
　　在插入节点之前，先从头开始查找要插入的位置，预先确定插入节点的所在层数。
2. 更新层信息
　　插入新节点后，须更新跳表每层中指向相邻节点的指针，同时确定插入节点的层数。
3. 完成插入操作

跳表删除

在跳表已知的删除节点后，需要找到删除节点的前后节点。为了保持跳表整体的有序性，必须依次删除该节点在各个层中的指针，并将前后节点的指针互相连接。执行跳表删除的步骤如下：

1. 从最高层开始遍历找到要被删除的节点，并记录其所有前继节点。
2. 遍历所有前继节点，并更新掉该节点在上一层的指针，如下图所示，删除节点 16 后需要重建节点 14 在上一层的指针，直至跳表的最低层。
3. 删除指定的节点。

跳表的实现

以下是一个基于C语言实现的跳表操作的代码：

```c
#include
#include
#include
// 跳表结构体
typedef struct skipListNode {
    int score;
    struct skipListNode *forward[1];
}skipListNode;

// 跳表结构体
typedef struct skipList {
    struct skipListNode *head;
    struct skipListNode *tl;
    int level;  // 当前跳表最高级别
}skipList;
// 创建新的节点
skipListNode* newNode(int level, int score) {
    skipListNode *node = (skipListNode*) malloc(sizeof(skipListNode) + level*sizeof(skipListNode*));
    node->score = score;
    return node;
}
// 创建新的跳表
skipList* createSkipList() {
    int i;
    skipList *list = (skipList*) malloc(sizeof(skipList));
    skipListNode *head = newNode(32, 0);
    list->head = head;
    for(i = 0; i 
        head->forward[i] = NULL;
    }
    list->tl = NULL;
    list->level = 1;
    srand(time(0));
    return list;
}
// 插入节点
void insert(skipList *list, int score) {
    skipListNode *update[32];
    skipListNode *current;
    int i, level;
    current = list->head;
    for(i = list->level-1; i >= 0; i--) {
        while(current->forward[i] && current->forward[i]->score 
            current = current->forward[i];
        }
        update[i] = current;
    }
    if(current->forward[0] && current->forward[0]->score == score) {
        return;
    }
    level = rand()%32 + 1;
    if(level > list->level ) {
        for(i=list->level; i 
            update[i] = list->head;
        }
        list->level = level;
    }
    current = newNode(level, score);
    for(i = 0; i 
        current->forward[i] = update[i]->forward[i];
        update[i]->forward[i] = current;
    }
}
// 删除节点
void delete(skipList *list, int score) {
    skipListNode *update[32];
    skipListNode *current;
    int i;
    current = list->head;
    for(i = list->level-1; i >= 0; i--) {
        while(current->forward[i] && current->forward[i]->score 
            current = current->forward[i];
        }
        update[i] = current;
    }
    current = current->forward[0];
    if(current && current->score == score) {
        for(i = 0; i level; i++) {
            if(update[i]->forward[i] == current) {
                update[i]->forward[i] = current->forward[i];
            }
        }
        free(current);
        while(list->level > 1 && list->head->forward[list->level-1] == NULL) {
            list->level--;
        }
    }
}

// 查找节点
skipListNode* find(skipList *list, int score) {
    skipListNode *current;
    int i;
    current = list->head;
    for(i = list->level-1; i >= 0; i--) {
        while(current->forward[i] && current->forward[i]->score 
            current = current->forward[i];
        }
    }
    if(current->forward[0] && current->forward[0]->score == score) {
        return current->forward[0];
    } else {
        return NULL;
    }
}