Что означает переменная skiplistnode "span" в redis.h?

Question

В redis.h, то skipnode определяется следующим образом:

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

Что делает вар span значит? Что этот магазин хранит?

Answer 1

span в конкретном узле хранит количество узлов между текущим узлом и узлом-> вперед на текущем уровне. span используется для вычисления ранга элемента 1 в списке пропуска.

Например, рассмотрим следующий список пропуску:

Рассмотрим узел головки. Пролет на всех уровнях будет равен 1.

Рассмотрим узел 1. На уровне 0 диапазон равен 1, так как вы будете span 1 элемент, если следовать указателю вперед. На уровне 1 диапазон равен 2, потому что вы будете span 2 элемента (узел 2 и узел 3), если вы будете следовать указателю вперед.

Посмотрите на function zslGetRank in t_zet.c. Вы можете видеть, как ранг вычисляется из значения диапазона на каждом уровне.