redisジャンプテーブル

ジャンプテーブル(skiplist)は、各ノードに複数の他のノードへのポインタを維持することによって、ノードへの迅速なアクセスを達成する秩序化されたデータ結果である.
ジャンプテーブルの実装
zskiplistNodeとzskiplistの2つの構造によってzskiplistの構成が定義されます.header:ジャンプテーブルのヘッダーノードを指します.tail:ジャンプテーブルのテーブルテールノードを指します.level:現在のジャンプテーブル内で、成熟した最大のノードの層数を記録します.length:ジャンプテーブルの長さを記録します.

typedef struct zskiplist{
    //         
    structz skiplistNode *header, *tail;

    //      
    unsigned long length;

    //           
    int level;
}

zskiplistNodeの構成:level:ジャンプテーブルノードのlevel配列には、複数の要素が含まれ、各要素には他のノードへのポインタが含まれます.forward:前進ポインタ、次のレベルへのポインタ.span:スパン.2つのノード間の距離を記録します.backward:バックポインタ、逆遍歴用のポインタ.≪スコア|Score|emdw≫:ノードのスコアは、タイプが変更された浮動小数点数であり、ジャンプ・テーブル内のすべてのノードは、スコアの小さい順にソートされます.≪メンバー｜Members｜oem_src≫:ノードのメンバー・オブジェクト.保存された文字列オブジェクトを指し、文字列オブジェクトはSDS値を保存します.

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

まとめ
ジャンプテーブルは秩序化された集合の最下位実装の1つである.redisのジャンプテーブル実装は、zskiplistとzskiplistNodeの2つの構造からなり、zskiplistは、ジャンプテーブル情報(ヘッダーノード、テーブルテールノード、長さなど)を保存するために使用され、zskiplistNodeはジャンプテーブルノードを表すために使用される.各ジャンプテーブルノードのレベルの高さは、同じジャンプテーブル内の1～32の乱数であり、複数のノードには同じスコアを含めることができますが、各ノードのメンバーオブジェクトは一意でなければなりません.ジャンプ・テーブルのノードは、スコア・サイズでソートされ、スコアが同じ場合、ノードはメンバー・オブジェクトのサイズでソートされます.