Redis 跳跃表 API 在数据检索中的高效运用
Redis 跳跃表基础概述
Redis 中的跳跃表（Skip List）是一种有序的数据结构，它通过在每个节点中维持多个指向其他节点的指针，来达到快速查找的目的。跳跃表的设计灵感来源于链表，但是相比普通链表，跳跃表在查找效率上有了质的飞跃。
在普通链表中，查找一个元素的时间复杂度为 O(n)，因为需要依次遍历链表中的每个节点。而跳跃表通过构建多层索引结构，使得查找操作可以跳过部分节点，从而将时间复杂度降低到 O(log n)。
跳跃表由多层节点组成，最底层是一个普通的有序链表，每一层都是下面一层的“快速通道”。每个节点包含一个分值（score）和一个或多个指针，指针指向其他节点。分值用于决定节点在跳跃表中的顺序，相同分值的节点会按照插入顺序排列。
Redis 跳跃表的结构定义
在 Redis 源码中，跳跃表的结构定义如下：
// 跳跃表节点
typedef struct zskiplistNode {
sds ele; // 成员对象
double score; // 分值
struct zskiplistNode *backward; // 后退指针
struct zskiplistLevel {
struct zskiplistNode *forward; // 前进指针
unsigned long span; // 跨度
} level[];
} zskiplistNode;
// 跳跃表
typedef struct zskiplist {
struct zskiplistNode *header, *tail; // 表头节点和表尾节点
unsigned long length; // 表中节点的数量
int level; // 表中层数最大的节点的层数
} zskiplist;
zskiplistNode是跳跃表节点的结构体。ele是一个 SDS（简单动态字符串），用于存储节点的值；score是分值，用于排序；backward是后退指针，指向前一个节点；level是一个柔性数组，包含多个zskiplistLevel结构体，每个结构体包含一个forward前进指针和span跨度。zskiplist是跳跃表的结构体。header和tail分别指向表头节点和表尾节点；length记录表中节点的数量；level表示表中层数最大的节点的层数。
Redis 跳跃表的创建与初始化
- 创建跳跃表节点 创建一个跳跃表节点的函数如下：
zskiplistNode *zslCreateNode(int level, double score, sds ele) {
zskiplistNode *zn =
zmalloc(sizeof(*zn)+level*sizeof(struct zskiplistLevel));
zn->score = score;
zn->ele = ele;
return zn;
}
该函数使用 zmalloc 分配内存，sizeof(*zn) 是 zskiplistNode 结构体本身的大小，level * sizeof(struct zskiplistLevel) 是柔性数组 level 的大小。然后设置节点的 score 和 ele。
- 创建跳跃表 创建一个跳跃表的函数如下：
zskiplist *zslCreate(void) {
int j;
zskiplist *zsl;
zsl = zmalloc(sizeof(*zsl));
zsl->level = 1;
zsl->length = 0;
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;
return zsl;
}
这里先分配 zskiplist 结构体的内存，初始化 level 为 1，length 为 0。然后创建表头节点，表头节点的分值为 0，ele 为 NULL，并且将表头节点的所有层的 forward 指针初始化为 NULL，span 初始化为 0。backward 指针也初始化为 NULL，tail 指针初始化为 NULL。
Redis 跳跃表的插入操作
插入操作是跳跃表的核心操作之一。在 Redis 跳跃表中插入一个节点时，需要确定插入的位置，并更新相关节点的指针。
- 确定插入位置
在插入节点前，首先要确定该节点在跳跃表中的插入位置。这需要从表头节点的最高层开始查找，找到第一个
forward指针指向的节点的score大于要插入节点的score的位置。
void zslInsert(zskiplist *zsl, double score, sds ele) {
zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x;
unsigned int rank[ZSKIPLIST_MAXLEVEL];
int i, level;
x = zsl->header;
for (i = zsl->level-1; i >= 0; i--) {
rank[i] = i == (zsl->level-1) ? 0 : rank[i+1];
while (x->level[i].forward &&
(x->level[i].forward->score < score ||
(x->level[i].forward->score == score &&
sdscmp(x->level[i].forward->ele,ele) < 0)))
{
rank[i] += x->level[i].span;
x = x->level[i].forward;
}
update[i] = x;
}
// 省略后续插入节点的代码
}
在上述代码中，update 数组用于记录每一层需要更新指针的节点，rank 数组用于记录从表头到当前节点的跨度。从最高层开始遍历，通过比较 score 和 ele 来确定插入位置。
- 生成随机层数 跳跃表节点的层数是随机生成的，这样可以保证跳跃表的结构相对平衡。
int zslRandomLevel(void) {
int level = 1;
while ((random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF))
level += 1;
return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
}
这里使用 random() 函数生成一个随机数，通过与 ZSKIPLIST_P * 0xFFFF 比较来决定是否增加层数，ZSKIPLIST_P 是一个概率值，通常为 0.25。
- 插入节点 确定插入位置和生成随机层数后，就可以插入节点了。
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;
}
for (i = level; i < zsl->level; i++) {
update[i]->level[i].span++;
}
if (update[0] == zsl->header)
x->backward = NULL;
else
x->backward = update[0];
if (x->level[0].forward)
x->level[0].forward->backward = x;
else
zsl->tail = x;
zsl->length++;
if (level > zsl->level)
zsl->level = level;
上述代码将新节点插入到跳跃表中，并更新相关节点的指针和跨度。同时更新跳跃表的长度和最大层数。
Redis 跳跃表的删除操作
删除操作与插入操作类似，也需要先确定要删除节点的位置，然后更新相关节点的指针。
- 确定删除节点位置
void zslDelete(zskiplist *zsl, double score, sds ele, zskiplistNode **node) {
zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x;
int i;
x = zsl->header;
for (i = zsl->level-1; i >= 0; i--) {
while (x->level[i].forward &&
(x->level[i].forward->score < score ||
(x->level[i].forward->score == score &&
sdscmp(x->level[i].forward->ele,ele) < 0)))
{
x = x->level[i].forward;
}
update[i] = x;
}
// 省略后续删除节点的代码
}
这里与插入操作类似，通过从最高层开始遍历找到要删除节点的位置，并记录每一层需要更新指针的节点。
- 删除节点
x = update[0]->level[0].forward;
if (x && score == x->score && sdscmp(x->ele,ele) == 0) {
zslDeleteNode(zsl, x, update);
if (!zsl->length) {
zsl->tail = zsl->header;
} else if (zsl->tail == x) {
zsl->tail = update[0];
}
if (node)
*node = x;
zslFreeNode(x);
zsl->length--;
while(zsl->level > 1 && zsl->header->level[zsl->level-1].forward == NULL)
zsl->level--;
} else {
if (node)
*node = NULL;
}
首先检查找到的节点是否是要删除的节点，如果是，则调用 zslDeleteNode 函数删除节点，并更新跳跃表的相关信息，如 tail 指针、长度和最大层数。如果不是，则直接返回。
Redis 跳跃表在数据检索中的应用
- 范围查询 Redis 跳跃表非常适合进行范围查询。例如，要查询分值在某个范围内的所有节点，可以从表头节点开始，通过比较分值找到范围的起始节点，然后顺着链表遍历，直到找到范围的结束节点。
zskiplistNode *zslFirstInRange(zskiplist *zsl, zrangespec *range) {
zskiplistNode *x;
int i;
x = zsl->header;
for (i = zsl->level-1; i >= 0; i--) {
while (x->level[i].forward &&
!zslValueGteMin(x->level[i].forward->score,x->level[i].forward->ele,range))
{
x = x->level[i].forward;
}
}
x = x->level[0].forward;
if (x &&!zslValueLteMax(x->score,x->ele,range))
return NULL;
return x;
}
上述代码通过从最高层开始查找，找到第一个分值大于等于范围最小值的节点，然后检查该节点是否在范围内，如果在则返回该节点，否则返回 NULL。
- 快速定位
由于跳跃表的多层索引结构，在查找特定分值的节点时，可以快速定位。例如，要查找分值为
score的节点：
zskiplistNode *zslFind(zskiplist *zsl, double score, sds ele) {
zskiplistNode *x = zsl->header;
int i;
for (i = zsl->level-1; i >= 0; i--) {
while (x->level[i].forward &&
(x->level[i].forward->score < score ||
(x->level[i].forward->score == score &&
sdscmp(x->level[i].forward->ele,ele) < 0)))
{
x = x->level[i].forward;
}
}
x = x->level[0].forward;
if (x && x->score == score && sdscmp(x->ele,ele) == 0)
return x;
else
return NULL;
}
从最高层开始遍历，通过比较分值和 ele 找到目标节点，如果找到则返回，否则返回 NULL。
基于 Redis 跳跃表 API 的应用示例（以 C 语言为例）
下面通过一个简单的示例展示如何使用 Redis 跳跃表 API 进行数据检索。假设我们要实现一个简单的排行榜功能，使用跳跃表来存储玩家的得分。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "redis.h"
int main() {
zskiplist *zsl = zslCreate();
// 插入玩家得分
zslInsert(zsl, 85.0, sdsnew("Player1"));
zslInsert(zsl, 92.0, sdsnew("Player2"));
zslInsert(zsl, 78.0, sdsnew("Player3"));
zslInsert(zsl, 95.0, sdsnew("Player4"));
// 查找特定玩家
zskiplistNode *node = zslFind(zsl, 92.0, sdsnew("Player2"));
if (node) {
printf("找到玩家: %s, 得分: %f\n", node->ele, node->score);
} else {
printf("未找到玩家\n");
}
// 范围查询
zrangespec range = {.min = 80.0, .max = 90.0, .minex = 1, .maxex = 1 };
zskiplistNode *rangeNode = zslFirstInRange(zsl, &range);
while (rangeNode) {
printf("范围内玩家: %s, 得分: %f\n", rangeNode->ele, rangeNode->score);
rangeNode = zslNextInRange(zsl, rangeNode, &range);
}
// 释放跳跃表
zslFree(zsl);
return 0;
}
在上述示例中，首先创建一个跳跃表，然后插入一些玩家的得分信息。接着使用 zslFind 函数查找特定玩家，使用 zslFirstInRange 和 zslNextInRange 函数进行范围查询。最后释放跳跃表的内存。
Redis 跳跃表与其他数据结构在数据检索方面的比较
- 与普通链表比较 普通链表在数据检索方面的时间复杂度为 O(n)，因为需要依次遍历链表中的每个节点。而 Redis 跳跃表通过多层索引结构，将时间复杂度降低到 O(log n)。例如，在一个包含 10000 个节点的链表中查找一个节点，平均需要遍历 5000 次；而在同样规模的跳跃表中，平均只需要遍历约 14 次（以 2 为底 10000 的对数约为 13.29）。
- 与平衡二叉树比较 平衡二叉树（如 AVL 树、红黑树）在数据检索方面的时间复杂度也为 O(log n)。但是，平衡二叉树的插入和删除操作相对复杂，需要进行旋转操作来维持树的平衡。而 Redis 跳跃表的插入和删除操作相对简单，不需要进行复杂的旋转操作，并且在实现上更加简洁。
- 与哈希表比较 哈希表在查找单个元素时的时间复杂度为 O(1)，但是哈希表不支持范围查询。而 Redis 跳跃表不仅可以快速查找单个元素，还可以高效地进行范围查询。例如，在一个存储用户信息的系统中，如果需要根据用户的年龄范围查询用户，哈希表就无法直接实现，而跳跃表可以很方便地做到。
Redis 跳跃表在实际项目中的优化与注意事项
- 内存优化
跳跃表节点的层数是随机生成的，为了避免层数过高导致内存浪费，可以适当调整随机层数生成的概率。例如，将
ZSKIPLIST_P的值从 0.25 适当调小，可以减少高层节点的出现概率，从而降低内存消耗。 - 并发访问 在多线程环境下使用 Redis 跳跃表时，需要注意并发访问的问题。可以使用互斥锁等机制来保证跳跃表操作的原子性，避免数据竞争。例如，在插入和删除节点时，先获取锁，操作完成后再释放锁。
- 数据规模与性能 随着数据规模的增大，跳跃表的性能可能会受到一定影响。虽然其时间复杂度为 O(log n)，但在非常大规模的数据量下，多层索引结构可能会占用大量内存，导致缓存命中率下降。此时可以考虑对跳跃表进行分段管理，或者结合其他数据结构来优化性能。
通过深入理解 Redis 跳跃表的 API 以及其在数据检索中的应用，可以在实际项目中更高效地使用跳跃表来管理和检索数据，提高系统的性能和效率。无论是在排行榜系统、搜索引擎的倒排索引，还是其他需要有序数据管理和范围查询的场景中，Redis 跳跃表都能发挥重要作用。同时，合理地对跳跃表进行优化和注意并发访问等问题，可以进一步提升其在实际应用中的表现。