algorithm - redis.hのskiplistnode変数「スパン」はどういう意味ですか?

Question

ではredis.h、skipnode は次のように定義されています。

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

var とはspanどういう意味ですか? この変数は何を保存しますか?

Answer 1

spanat 特定のノードは、現在のノードとノード間のノードの数を格納します->現在のレベルで転送します。spanスキップ リスト内の要素の 1 ベースのランクを計算するために使用されます。

たとえば、次のスキップ リストを考えてみましょう。

ヘッド ノードを考えてみましょう。すべてのレベルのスパンは 1 になります。

ノード 1 を考えてみましょう。レベル 0 では、前方ポインターをたどると 1 つの要素をスパンするため、スパンは 1 です。レベル 1 では、フォワード ポインターをたどると 2 つの要素 (ノード 2 とノード 3)にまたがるため、スパンは 2 です。

t_zet.cの関数 zslGetRank を見てください。各レベルのスパンの値からランクがどのように計算されるかがわかります。