Redisのジャンプテーブル実装
Redisのジャンプテーブルはredis.h/zskiplistNodeとredis.h/zskiplistの2つの構造定義で、zskiplistNode構造はジャンプテーブルノードを表すために使用され、zskiplist構造は、ノードの数や、テーブルヘッダノードとテーブルエンドノードへのポインタなど、ジャンプテーブルノードに関する情報を保存するために使用されます.
図5-1は、画像の一番左に位置するzskiplist構造のジャンプテーブルの例を示し、この構造は以下の属性を含む.
ヘッダー:ジャンプテーブルのヘッダーノードを指します.
tail:ジャンプテーブルのテーブルテールノードを指します.
level:現在のジャンプテーブル内で、レイヤ数が最も大きいノードのレイヤ数を記録します(ヘッダノードのレイヤ数は計算されません).
length:ジャンプテーブルの長さを記録します.すなわち、ジャンプテーブルには現在ノードの数が含まれています(ヘッダノードは計算されません).
zskiplist構造の右側にある4つのzskiplistNode構造です.この構造には、次のプロパティが含まれています.
レイヤ(level):ノードにノードの各レイヤをL 1、L 2、L 3などの文字でマークし、L 1は第1のレイヤを表し、L 2は第2のレイヤを表す.各レイヤには、前進ポインタとスパンの2つのアトリビュートがあります.前進ポインタは、表の最後の方向にある他のノードにアクセスするために使用され、スパンは、前進ポインタがノードと現在のノードを指す距離を記録します.上の画像では、線に数字が付いた矢印が前進ポインタを表し、その数字がスパンです.プログラムがヘッダからテーブルの末尾に遍歴すると、アクセスはレイヤの前進ポインタに沿って行われます.
後退(backward)ポインタ:ノード内のBW文字でノードをマークする後退ポインタで、現在のノードにある前のノードを指します.後退ポインタは、プログラムが表の末尾から表の先頭に遍歴して使用されます.
スコア(score):各ノードの1.0、2.0、3.0は、ノードに保存されているスコアです.ジャンプテーブルでは、ノードは、それぞれの保存されたスコアで小さいものから大きいものに並べられます.
メンバーオブジェクト(obj):各ノードのo 1、o 2、o 3は、ノードが保存するメンバーオブジェクトである.
注意ヘッダノードは他のノードと同様に構成されています.ヘッダノードには後退ポインタ、スコア、メンバーオブジェクトもありますが、ヘッダノードのこれらの属性は使用されませんので、図ではこれらの部分を省略し、ヘッダノードの各層のみを表示します.
このセクションでは、zskiplistNodeとzskiplistの2つの構造についてさらに詳しく説明します.
ジャンプテーブルノードの実現はredis.h/zskiplistNode構造定義:
ジャンプテーブルノードのlevel配列には複数の要素が含まれ、各要素には他のノードへのポインタが含まれており、プログラムはこれらのレイヤを通じて他のノードへのアクセスを高速化することができます.一般的に、レイヤの数が多ければ多いほど、他のノードへのアクセスが速くなります.
新しいジャンプテーブルノードを作成するたびに、プログラムはべき乗則(power law)に基づいて、1と32の間の値をlevel配列のサイズとしてランダムに生成します.このサイズはレイヤの「高さ」です.
図5−2は、C言語の配列インデックスが常に0から始まるため、ノードの第1層がlevel[0]、第2層がlevel[1]の3つの高さのノードをそれぞれ示している.
各レイヤには、テーブルヘッダからノードにアクセスするためのテーブルテール方向への前進ポインタ(level[i].forwardプロパティ)があります.
図5-3は、プログラムがヘッダーからテール方向にジャンプテーブル内のすべてのノードを巡る経路を破線で示している.
反復プログラムは、まずジャンプテーブルの最初のノード(ヘッダ)にアクセスし、4番目のレイヤの前進ポインタからテーブルの2番目のノードに移動します.
2番目のノードでは、プログラムは2番目のレイヤの前進ポインタに沿ってテーブルの3番目のノードに移動します.
3番目のノードの場合、プログラムは同様に2番目のレイヤの前進ポインタに沿ってテーブルの4番目のノードに移動します.
プログラムが再び4番目のノードの前進ポインタに沿って移動すると、NULLにぶつかり、ジャンプテーブルの表尾に達したことを知り、今回の遍歴を終了する.
レイヤのスパン(level[i].spanプロパティ)は、2つのノード間の距離を記録するために使用されます.
2つのノード間のスパンが大きいほど、距離が遠くなります.
NULLを指すすべての前進ポインタのスパンは0です.ノードに接続されていないためです.
最初は、スパンがループ操作と関係があると思われがちでしたが、実際にはそうではありません.ループ操作は前進ポインタだけで完了し、スパンは実際にはランキングを計算するために使用されます.あるノードを検索する過程で、沿道にアクセスしたすべてのレイヤのスパンを累計し、結果としてターゲットノードのジャンプテーブルでの順位が得られます.
例えば、図5〜図4は、ジャンプテーブルにおいてスコア3.0、メンバーオブジェクトo 3のノードを検索する際に、沿道で経験するレイヤを破線でマークしている.検索の過程は1つのレイヤしか通過せず、レイヤのスパンは3であるため、ターゲットノードのジャンプテーブルにおける順位は3である.
さらに例を挙げると、図5−5において、スキップテーブルにおいてスコア2.0、メンバオブジェクトo 2のノードを検索する際に、途中で経験するレイヤが破線で表記されている.ノードを検索する過程で、プログラムは2つのスパン1のノードを通過したので、ジャンプテーブルにおけるターゲットノードの順位は2であると算出できる.
ノードの後退ポインタ(backwardプロパティ)は、テーブルの末尾からヘッダ方向にノードにアクセスするために使用されます.複数のノードを一度にスキップできる前進ポインタとは異なり、各ノードに1つの後退ポインタしかないため、毎回前のノードに後退するしかありません.
図5−6は、スキップテーブル内のすべてのノードを表の末尾から表の先頭に遍歴する場合、プログラムが最初にスキップテーブルのtailポインタを介して表の末尾ノードにアクセスし、その後、後退ポインタを介して最後から2番目のノードにアクセスし、その後、後退ポインタに沿って最後から3番目のノードにアクセスし、その後、NULLを指す後退ポインタに遭遇し、アクセスが終了することを点線で示している.
ノードのスコア(scoreプロパティ)はdoubleタイプの浮動小数点数であり、ジャンプテーブルのすべてのノードはスコアが小さいから大きいまでソートされます.
ノードのメンバーオブジェクト(objプロパティ)は、文字列オブジェクトを指し、文字列オブジェクトはSDS値を保存するポインタです.
同じジャンプ・テーブルでは、各ノードに保存されているメンバー・オブジェクトは一意でなければなりませんが、複数のノードに保存されているスコアは同じです.スコアが同じノードは、メンバー・オブジェクトのディクショナリ・シーケンスのサイズに従ってソートされ、メンバー・オブジェクトの小さいノードは前面(ヘッダーに近い方向)に、メンバー・オブジェクトの大きいノードは背面(表の末尾に近い方向)に配置されます.
例えば、図5−7に示すジャンプテーブルにおいて、3つのジャンプテーブルノードはいずれも同じスコア10086.0を保持しているが、メンバーオブジェクトo 1を保持するノードは、メンバーオブジェクトo 2およびo 3を保持するノードの前に並び、メンバーオブジェクトo 2を保持するノードは、メンバーオブジェクトo 3を保持するノードの前に並び、o 1、o 2、o 3の3つのメンバーオブジェクトの辞書でのソートは、o 1<=o 2<=o 3である.
図5〜8に示すように、複数のジャンプテーブルノードだけで1つのジャンプテーブルを構成することができる.
しかし、zskiplist構造を用いてこれらのノードを保持することにより、図5−9に示すように、ジャンプテーブルのヘッダノードやテーブルテールノードに素早くアクセスしたり、ジャンプテーブルの数(すなわちジャンプテーブルの長さ)などの情報を迅速に取得したりするなど、ジャンプテーブル全体をより容易に処理することができる.
zskiplist構造の定義は以下の通りです.
ヘッダとtailポインタはそれぞれジャンプテーブルのヘッダとヘッダノードを指し,この2つのポインタによりプログラムがヘッダノードとヘッダノードを位置決めする複雑さは
lengthプロパティを使用してノードの数を記録することで、プログラムは複雑さの中でジャンプテーブルの長さを返すことができます.
levelプロパティは、ジャンプテーブルで最も高いレイヤのレイヤ数を複雑度で取得するために使用されます.ヘッダノードのレイヤ数は計算されません.
原文住所:
http://redisbook1e.readthedocs.org/en/latest/preview/skiplist/datastruct.html
図5-1は、画像の一番左に位置するzskiplist構造のジャンプテーブルの例を示し、この構造は以下の属性を含む.
ヘッダー:ジャンプテーブルのヘッダーノードを指します.
tail:ジャンプテーブルのテーブルテールノードを指します.
level:現在のジャンプテーブル内で、レイヤ数が最も大きいノードのレイヤ数を記録します(ヘッダノードのレイヤ数は計算されません).
length:ジャンプテーブルの長さを記録します.すなわち、ジャンプテーブルには現在ノードの数が含まれています(ヘッダノードは計算されません).
zskiplist構造の右側にある4つのzskiplistNode構造です.この構造には、次のプロパティが含まれています.
レイヤ(level):ノードにノードの各レイヤをL 1、L 2、L 3などの文字でマークし、L 1は第1のレイヤを表し、L 2は第2のレイヤを表す.各レイヤには、前進ポインタとスパンの2つのアトリビュートがあります.前進ポインタは、表の最後の方向にある他のノードにアクセスするために使用され、スパンは、前進ポインタがノードと現在のノードを指す距離を記録します.上の画像では、線に数字が付いた矢印が前進ポインタを表し、その数字がスパンです.プログラムがヘッダからテーブルの末尾に遍歴すると、アクセスはレイヤの前進ポインタに沿って行われます.
後退(backward)ポインタ:ノード内のBW文字でノードをマークする後退ポインタで、現在のノードにある前のノードを指します.後退ポインタは、プログラムが表の末尾から表の先頭に遍歴して使用されます.
スコア(score):各ノードの1.0、2.0、3.0は、ノードに保存されているスコアです.ジャンプテーブルでは、ノードは、それぞれの保存されたスコアで小さいものから大きいものに並べられます.
メンバーオブジェクト(obj):各ノードのo 1、o 2、o 3は、ノードが保存するメンバーオブジェクトである.
注意ヘッダノードは他のノードと同様に構成されています.ヘッダノードには後退ポインタ、スコア、メンバーオブジェクトもありますが、ヘッダノードのこれらの属性は使用されませんので、図ではこれらの部分を省略し、ヘッダノードの各層のみを表示します.
このセクションでは、zskiplistNodeとzskiplistの2つの構造についてさらに詳しく説明します.
ジャンプテーブルノード
ジャンプテーブルノードの実現はredis.h/zskiplistNode構造定義:
typedef struct zskiplistNode {
//
struct zskiplistLevel {
//
struct zskiplistNode *forward;
//
unsigned int span;
} level[];
//
struct zskiplistNode *backward;
//
double score;
//
robj *obj;
} zskiplistNode;
レイヤー
ジャンプテーブルノードのlevel配列には複数の要素が含まれ、各要素には他のノードへのポインタが含まれており、プログラムはこれらのレイヤを通じて他のノードへのアクセスを高速化することができます.一般的に、レイヤの数が多ければ多いほど、他のノードへのアクセスが速くなります.
新しいジャンプテーブルノードを作成するたびに、プログラムはべき乗則(power law)に基づいて、1と32の間の値をlevel配列のサイズとしてランダムに生成します.このサイズはレイヤの「高さ」です.
図5−2は、C言語の配列インデックスが常に0から始まるため、ノードの第1層がlevel[0]、第2層がlevel[1]の3つの高さのノードをそれぞれ示している.
ぜんしんししん
各レイヤには、テーブルヘッダからノードにアクセスするためのテーブルテール方向への前進ポインタ(level[i].forwardプロパティ)があります.
図5-3は、プログラムがヘッダーからテール方向にジャンプテーブル内のすべてのノードを巡る経路を破線で示している.
反復プログラムは、まずジャンプテーブルの最初のノード(ヘッダ)にアクセスし、4番目のレイヤの前進ポインタからテーブルの2番目のノードに移動します.
2番目のノードでは、プログラムは2番目のレイヤの前進ポインタに沿ってテーブルの3番目のノードに移動します.
3番目のノードの場合、プログラムは同様に2番目のレイヤの前進ポインタに沿ってテーブルの4番目のノードに移動します.
プログラムが再び4番目のノードの前進ポインタに沿って移動すると、NULLにぶつかり、ジャンプテーブルの表尾に達したことを知り、今回の遍歴を終了する.
スパン
レイヤのスパン(level[i].spanプロパティ)は、2つのノード間の距離を記録するために使用されます.
2つのノード間のスパンが大きいほど、距離が遠くなります.
NULLを指すすべての前進ポインタのスパンは0です.ノードに接続されていないためです.
最初は、スパンがループ操作と関係があると思われがちでしたが、実際にはそうではありません.ループ操作は前進ポインタだけで完了し、スパンは実際にはランキングを計算するために使用されます.あるノードを検索する過程で、沿道にアクセスしたすべてのレイヤのスパンを累計し、結果としてターゲットノードのジャンプテーブルでの順位が得られます.
例えば、図5〜図4は、ジャンプテーブルにおいてスコア3.0、メンバーオブジェクトo 3のノードを検索する際に、沿道で経験するレイヤを破線でマークしている.検索の過程は1つのレイヤしか通過せず、レイヤのスパンは3であるため、ターゲットノードのジャンプテーブルにおける順位は3である.
さらに例を挙げると、図5−5において、スキップテーブルにおいてスコア2.0、メンバオブジェクトo 2のノードを検索する際に、途中で経験するレイヤが破線で表記されている.ノードを検索する過程で、プログラムは2つのスパン1のノードを通過したので、ジャンプテーブルにおけるターゲットノードの順位は2であると算出できる.
後退ポインタ
ノードの後退ポインタ(backwardプロパティ)は、テーブルの末尾からヘッダ方向にノードにアクセスするために使用されます.複数のノードを一度にスキップできる前進ポインタとは異なり、各ノードに1つの後退ポインタしかないため、毎回前のノードに後退するしかありません.
図5−6は、スキップテーブル内のすべてのノードを表の末尾から表の先頭に遍歴する場合、プログラムが最初にスキップテーブルのtailポインタを介して表の末尾ノードにアクセスし、その後、後退ポインタを介して最後から2番目のノードにアクセスし、その後、後退ポインタに沿って最後から3番目のノードにアクセスし、その後、NULLを指す後退ポインタに遭遇し、アクセスが終了することを点線で示している.
スコアとメンバー
ノードのスコア(scoreプロパティ)はdoubleタイプの浮動小数点数であり、ジャンプテーブルのすべてのノードはスコアが小さいから大きいまでソートされます.
ノードのメンバーオブジェクト(objプロパティ)は、文字列オブジェクトを指し、文字列オブジェクトはSDS値を保存するポインタです.
同じジャンプ・テーブルでは、各ノードに保存されているメンバー・オブジェクトは一意でなければなりませんが、複数のノードに保存されているスコアは同じです.スコアが同じノードは、メンバー・オブジェクトのディクショナリ・シーケンスのサイズに従ってソートされ、メンバー・オブジェクトの小さいノードは前面(ヘッダーに近い方向)に、メンバー・オブジェクトの大きいノードは背面(表の末尾に近い方向)に配置されます.
例えば、図5−7に示すジャンプテーブルにおいて、3つのジャンプテーブルノードはいずれも同じスコア10086.0を保持しているが、メンバーオブジェクトo 1を保持するノードは、メンバーオブジェクトo 2およびo 3を保持するノードの前に並び、メンバーオブジェクトo 2を保持するノードは、メンバーオブジェクトo 3を保持するノードの前に並び、o 1、o 2、o 3の3つのメンバーオブジェクトの辞書でのソートは、o 1<=o 2<=o 3である.
ジャンプテーブル
図5〜8に示すように、複数のジャンプテーブルノードだけで1つのジャンプテーブルを構成することができる.
しかし、zskiplist構造を用いてこれらのノードを保持することにより、図5−9に示すように、ジャンプテーブルのヘッダノードやテーブルテールノードに素早くアクセスしたり、ジャンプテーブルの数(すなわちジャンプテーブルの長さ)などの情報を迅速に取得したりするなど、ジャンプテーブル全体をより容易に処理することができる.
zskiplist構造の定義は以下の通りです.
typedef struct zskiplist {
//
struct zskiplistNode *header, *tail;
//
unsigned long length;
//
int level;
} zskiplist;
ヘッダとtailポインタはそれぞれジャンプテーブルのヘッダとヘッダノードを指し,この2つのポインタによりプログラムがヘッダノードとヘッダノードを位置決めする複雑さは
lengthプロパティを使用してノードの数を記録することで、プログラムは複雑さの中でジャンプテーブルの長さを返すことができます.
levelプロパティは、ジャンプテーブルで最も高いレイヤのレイヤ数を複雑度で取得するために使用されます.ヘッダノードのレイヤ数は計算されません.
原文住所:
http://redisbook1e.readthedocs.org/en/latest/preview/skiplist/datastruct.html