Redis数据结构之跳跃表（SkipList）

Redis是一个开源的、使用ANSI C语言编写、支持网络、可基于内存亦可持久化的日志型、Key-Value数据库，并提供多种语言的API。Redis凭借其高性能、高可用性、丰富的数据结构以及简洁的API而备受青睐。其中，跳跃表（SkipList）作为Redis中的一种重要数据结构，被广泛用于有序集合（Sorted Set）的底层实现，以支持高效的插入、删除和查找操作。

什么是跳跃表（SkipList）

跳跃表（SkipList）是一种用于有序元素序列快速搜索的随机化的数据结构，由美国计算机科学家William Pugh于1989年在其论文《Skip lists: a probabilistic alternative to balanced trees》中提出。它通过在每个节点中维持多个指向其他节点的指针，以达到快速访问节点的目的。跳跃表可以看作是对单链表的一种优化，通过添加多级索引来提高查找效率。

跳跃表的基本结构

跳跃表是一个包含多个节点和层级信息的结构体。每个节点都包含多个层，每一层都构成了一个有序链表。查找时，从最高层开始，根据目标值的大小逐层向下查找，直到找到目标节点或确定目标节点不存在。

跳跃表节点（zskiplistNode）：

跳跃表的节点结构通常包含以下信息：

• 成员对象（ele）：存储节点的元素值。
• 分数（score）：用于排序和比较的元素分数，确保有序性。
• 后退指针（backward）：指向前一个节点的指针，便于反向遍历。
• 层级数组（level）：一个柔性数组，每个元素都是一个结构体，包含指向同一层次和下一层次节点的指针（forward）和跨度（span）。

跳跃表（zskiplist）：

包含多个节点和层级信息的结构体，通常还包含表头节点（header）、表尾节点（tail）以及最大层级（level）等信息。表头节点和表尾节点用于快速定位跳跃表的边界，而最大层级则决定了跳跃表的高度。

跳跃表的优势

1. 查找效率高：对于包含n个节点的跳跃表，其查找操作的时间复杂度为O(log n)，这是因为每次查找都可以跳过部分节点，从而减少比较次数。
2. 实现简单：与平衡树相比，跳跃表的实现更加简单直观，插入和删除操作只需要修改相邻节点的指针，不涉及复杂的子树调整。
3. 空间换时间：通过增加数据冗余（即多层索引），跳跃表实现了查找效率的显著提升。

Redis中的跳跃表实现

Redis中的跳跃表主要用于有序集合（Sorted Set）的底层实现。有序集合是一种元素不重复且按照成员分数进行排序的集合。Redis使用跳跃表来维护有序集合中的元素顺序，以便实现高效的插入、删除和查找操作。

Redis跳跃表节点的C语言结构体定义：

typedef struct zskiplistNode {     sds ele; // 节点元素     double score; // 节点分数     struct zskiplistNode *backward; // 回退指针     // 层级数组，level 数组中的每个元素都包含两个指针：forward 和 span     struct zskiplistLevel {         struct zskiplistNode *forward;         unsigned int span;     } level[]; } zskiplistNode; 

跳跃表操作的详细代码示例：

以下是一个简化的Redis跳跃表插入操作的C语言代码示例。这个示例主要展示了如何创建新的节点、计算新节点的层级、更新跳跃表以及处理插入过程中的一些细节。

#include <stdio.h> #include <stdlib.h> #include <string.h>  // 假设一些基础函数已经定义，如zslRandomLevel(), zslCreateNode()等  // 插入新元素到跳跃表 int zslInsert(zskiplist *zsl, double score, sds ele) {     zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x;     int rank[ZSKIPLIST_MAXLEVEL];     int i, level;      // 更新update数组和rank数组     // 省略具体实现，这里只展示框架      level = zslRandomLevel();     if (level > zsl->level) {         for (i = zsl->level; i < level; i++) {             rank[i] = 0;             update[i] = zsl->header;             update[i]->level[i].span = zsl->length;         }         zsl->level = level;     }      x = zslCreateNode(level, score, ele);      // 遍历每一层，更新指针和跨度     for (i = 0; i < level; i++) {         x->level[i].forward = update[i]->level[i].forward;         update[i]->level[i].forward = x;          // 更新跨度         x->level[i].span = update[i]->level[i].span - (rank[0] - rank[i]);         update[i]->level[i].span = (rank[0] - rank[i]) + 1;     }      // 设置后退指针     x->backward = (rank[0] == 0) ? NULL : update[0];     if (x->level[0].forward != NULL) {         x->level[0].forward->backward = x;     } else {         zsl->tail = x;     }      // 更新跳跃表的长度     zsl->length++;      // 返回新插入节点的排名（通常为0，因为是从头开始插入）     return 0; }  // 辅助函数：随机生成节点层级 int zslRandomLevel(void) {     int level = 1;     while ((random() & 0xFFFF) < (ZSKIPLIST_P * 0xFFFF))         level += 1;     return (level < ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL; }  // 辅助函数：创建新节点 zskiplistNode *zslCreateNode(int level, double score, sds ele) {     zskiplistNode *zn = zmalloc(sizeof(*zn) + level * sizeof(struct zskiplistLevel));     zn->score = score;     zn->ele = ele;     for (int i = 0; i < level; i++) {         zn->level[i].forward = NULL;         zn->level[i].span = 0;     }     zn->backward = NULL;     return zn; }  // 假设的跳跃表结构体定义 typedef struct zskiplist {     struct zskiplistNode *header, *tail;     unsigned long length;     int level; } zskiplist;  // 初始化跳跃表 zskiplist *zslCreate(void) {     int j;     zskiplist *zsl;      zsl = zmalloc(sizeof(*zsl));     zsl->header = zslCreateNode(ZSKIPLIST_MAXLEVEL, 0, NULL);     for (j = 0; j < ZSKIPLIST_MAXLEVEL; j++) {         zsl->header->level[j].forward = NULL;         zsl->header->level[j].span = 0;     }     zsl->header->backward = NULL;     zsl->tail = NULL;     zsl->length = 0;     zsl->level = 1;     return zsl; }  // 假设的常量定义 #define ZSKIPLIST_MAXLEVEL 32 /* Should be enough for 2^32 elements */ #define ZSKIPLIST_P 0.25      /* Skiplist P = 1/4 */  // 示例使用 int main() {     zskiplist *zsl = zslCreate();     sds ele1 = sdsnew("one");     sds ele2 = sdsnew("two");     zslInsert(zsl, 1.0, ele1);     zslInsert(zsl, 2.0, ele2);      // 假设有额外的函数来遍历和打印跳跃表     // printSkipList(zsl);      // 清理资源     // 省略具体的资源释放代码      return 0; }  

注意：上述代码是一个简化的示例，用于说明如何在Redis的上下文中实现跳跃表的插入操作。在实际Redis实现中，跳跃表的操作会更加复杂，包括更详细的错误处理、内存管理以及与其他Redis数据结构的交互等。

此外，Redis的跳跃表实现还包含删除和查找等操作，这些操作同样基于节点的层级和跨度信息来实现高效的遍历和更新。

最后，虽然上述代码使用了C语言的标准库函数（如random(), malloc(), free()等），但在Redis的实际实现中，它使用了一套自定义的内存分配和错误处理机制，以确保高效和稳定的运行。