とチェーンテーブル,辞書などのデータ構造はRedis内部に広く応用されているのとは異なり,Redisは2つの場所でのみジャンプテーブルを用い,1つは秩序化集合キーを実現し,もう1つはクラスタノードで内部データ構造として用いられるほか,ジャンプテーブルはRedisにおいて他の用途はない. ジャンプテーブル(skiplist)は、各ノードに複数のポインタを維持することによって、ノードへの迅速なアクセスを達成する秩序化されたデータ構造である. ジャンプテーブルは、平均O(logn)、最悪O(N)の複雑度をサポートするノードルックアップをサポートする.
ほとんどの場合、ジャンプテーブルの効率はバランスツリーに匹敵し、ジャンプテーブルの実現はバランスツリーよりも簡単であるため、バランスツリーの代わりにジャンプテーブルを使用するプログラムが多い. Redisは、順序セットキーの最下位実装の1つとしてジャンプテーブルを使用し、1つの順序セットに含まれる要素の数が比較的多い場合、または順序セット内の要素のメンバーが比較的長い文字フィールドである場合、Redisは、順序セットキーの最下位実装としてジャンプテーブルを使用する. Redisのジャンプテーブルはredis.h/zskiplistNodeとredis.h/zskiplist 2つの構造定義 typedef struct zskiplistNode {
robj *obj;
double score;
struct zskiplistNode *backward;
struct zskiplistLevel {
struct zskiplistNode *forward;
unsigned int span;
} level[];
} zskiplistNode;
typedef struct zskiplist {
struct zskiplistNode *header, *tail;
unsigned long length;
int level;
} zskiplist;
重点的回顧ジャンプテーブルは、秩序化された集合の下位実装の1つであるである.
RedisのジャンプテーブルはzskiplistとzskiplistNodeの2つの構造からなる各ジャンプテーブルノードの層の高さは、1〜32の間の乱数である. 同じジャンプテーブルでは、複数のノードは同じスコアを含んでもよいが、各ノードのメンバーオブジェクトは一意でなければならない. ジャンプテーブルのノードをスコアサイズでソートし、スコアが同じである場合、ノードをメンバーオブジェクトサイズでソートする.