Redis数据结构之跳表 skiplist

跳表（skiplist）是一种可以替代平衡树的数据结构，它允许快速的插入、删除、查找操作，所有操作的平均时间复杂度都是O(logN)。

Redis中的跳表用于有序集合数据类型（Sorted Set）的实现。

以下是一个简单的C语言实现的跳表节点和跳表结构的示例：

#include <stdlib.h>
 
// 跳表节点结构体
typedef struct skiplistNode {
    double key;         // 键值
    void *value;        // 值
    struct skiplistNode *backward;  // 后退指针
    struct skiplistLevel {
        struct skiplistNode *forward;  // 前进指针
        unsigned int span;             // 跳跃的长度
    } level[];
} skiplistNode;
 
// 跳表结构体
typedef struct skiplist {
    struct skiplistNode *header, *tail;  // 头尾节点指针
    unsigned long length;               // 节点数量
    int level;                          // 最大层数
} skiplist;
 
// 创建一个跳表节点
skiplistNode *createNode(int level, double key, void *value) {
    skiplistNode *node = malloc(sizeof(skiplistNode) + level * sizeof(skiplistNode));
    node->key = key;
    node->value = value;
    return node;
}
 
// 初始化一个跳表
skiplist *initSkipList() {
    int level = 1;  // 起始层数
    skiplistNode *node = createNode(level, 0, NULL); // 创建头节点
    skiplist *list = malloc(sizeof(skiplist));
    list->header = list->tail = node;
    list->length = 0;
    list->level = level;
    return list;
}
 
// 插入操作示例
void insert(skiplist *list, double key, void *value) {
    skiplistNode *update[64], *node;
    int i, level;
 
    // 找到所有层次的更新节点，同时确保node为空
    node = list->header;
    for (i = list->level - 1; i >= 0; i--) {
        while (node->level[i].forward && node->level[i].forward->key < key) {
            node = node->level[i].forward;
        }
        update[i] = node;
    }
 
    // 随机生成层数
    level = randomLevel();  // 实现随机层数的函数
    if (level > list->level) {
        for (i = list->level; i < level; i++) {
            update[i] = list->header;
        }
        list->level = level;
    }
 
    // 创建新节点
    node = createNode(level, key, value);
 
    // 将新节点链接到跳表
    for (i = 0; i < level; i++) {
        node->level[i].forward = update[i]->level[i].forward;
        update[i]->level[i].forward = node;
 
        // 更新前后节点指针
        if (node->level[i].forward) {
            node->level[i].span = node->level[i].forward->level[i].span - (node->key > node->level[i].forward->key);
        } else {
            node->level[i].span = list->length - (update[i] == list->header);
        }
        if (update[i] == list->header) {
            list->header->level[i].span = list->length + 1;
        } else {
            up