algorithm - redis.h 中的 skiplistnode 变量“span”是什么意思？

Question

在redis.h中，skipnode 定义如下：

typedef struct zskiplistNode {
    robj *obj;
    double score;
    struct zskiplistNode *backward;
    struct zskiplistLevel {
        struct zskiplistNode *forward;
        unsigned int span;
    } level[];
} zskiplistNode;

varspan是什么意思？这个 var 存储什么？

Answer 1

spanat a specific node 存储当前节点和当前级别的 node->forward 之间的节点数。span用于计算跳过列表中元素的从 1 开始的排名。

例如，考虑以下跳过列表：

考虑头节点。所有级别的跨度均为 1。

考虑节点 1。在级别 0，跨度为 1，因为如果您跟随前向指针，您将跨越1 个元素。在级别 1，跨度为 2，因为如果您遵循前向指针，您将跨越2 个元素（节点 2 和节点 3）。

看看t_zet.c 中的函数 zslGetRank。您可以看到如何根据每个级别的 span 值计算排名。