Redisのデータ構造のジャンプテーブルの詳細説明

次のコラム Redis チュートリアル では、Redis データ構造のジャンプ テーブルについて詳しく説明します。困っている友人の役に立てば幸いです。

まえがき

ジャンプ リストは、ノードにすばやくアクセスするという目的を達成するために、各ノード内の他のノードへの複数のポインタを保持する順序付けされたデータ構造です。このように、理解するのは難しいかもしれませんが、まずリンクされたリストを思い出してください。

1. ジャンプ テーブルを確認する

1.1 ジャンプ テーブルとは

単一リンク リストの場合、必要に応じて、リンク リストに格納されているデータが順序付けされている場合でも、その中の特定のデータを見つけるには、リンクされたリストを最初から最後までたどることしかできません。この方法では、検索効率は非常に低くなり、時間計算量は O(n) と非常に高くなります。

検索効率を向上させたい場合は、リンクされたリストにインデックスを構築することを検討できます。前のレベルまでの 2 つのノードごとに 1 つのノードを抽出し、抽出されたレベルをインデックスと呼びます。

この時点では、ノード 8 を見つけたいと仮定します。最初にインデックス レイヤをトラバースできます。インデックス レイヤの値 7 を持つノードまでトラバースすると、次のことがわかります。次のノードが 9 である場合、検索するノード 8 はこれら 2 つのノードの間にある必要があります。リンク リスト レベルまで降下し、ノード 8 を見つけるためにトラバースを続けました。当初、単一リンク リストでノード 8 を見つけるには 8 つのノードを走査する必要がありましたが、第 1 レベルのインデックスを使用することで、5 つのノードを走査するだけで済みます。

この例から、インデックスのレイヤーを追加した後、ノードを見つけるために通過する必要があるノードの数が減少し、検索効率が向上していることがわかります。 、別のレベルのインデックスを追加します。

写真を見ると、検索効率が再び向上していることがわかります。この例ではデータが非常に少ないですが、データが大量にある場合は、マルチレベルのインデックスを追加すると、検索効率が大幅に向上します。

このリンク リストと複数レベルのインデックスのような構造は、ジャンプ リストです。

2. Redis ジャンプ テーブル

Redis は、順序付きセット キーの基礎となる実装の 1 つとしてジャンプ テーブルを使用します。順序付きセットに多数の 要素が含まれる場合、または順序付きセット内の要素の メンバーが比較的長い文字列 である場合、Redis は順序付きセット キーの基礎となる実装としてジャンプ テーブルを使用します。

ここで、疑問について考える必要があります。多数の要素がある場合、またはメンバーが比較的長い文字列である場合、Redis はなぜジャンプ テーブルを使用して実装するのでしょうか?

上記のことから、ジャンプ リストはリンク リストにマルチレベルのインデックスを追加して検索の効率を向上させていることがわかりますが、これは時間に対するスペースを考慮したソリューションであり、必然的に問題 - インデックスはメモリを消費します。元のリンク リストは非常に大きなオブジェクトを格納する場合がありますが、インデックス ノードはキー値といくつかのポインタを格納するだけでよく、オブジェクトを格納する必要がないため、ノード自体が比較的大きい場合や要素数が少ない場合には、比較的大きいため、その利点は必然的に拡大されますが、欠点は無視できます。

2.1 Redis でのスキップ テーブルの実装

Redis のスキップ テーブルは、Redisのデータ構造のジャンプテーブルの詳細説明 と Skiplist の 2 つの構造体によって定義されます。Redisのデータ構造のジャンプテーブルの詳細説明 構造体はスキップ テーブル ノードを表すために使用され、zskiplist 構造体はジャンプを保存するために使用されます。ノード数、先頭ノードと末尾ノードへのポインタなど、テーブル ノードに関連する情報です。

上図はスキップ リストの例を示しており、一番左はスキップリスト構造であり、次の属性が含まれています。

• header: ジャンプ テーブルのヘッダー ノードを指します。このポインター プログラムを通じてヘッダー ノードを見つける時間計算量は O(1)

• です。

  tail: ジャンプ テーブルの末尾ノードを指します。このポインタ プログラムを通じてテーブルの末尾ノードを見つける時間計算量は O(1)

• レベル: レコードです現在のジャンプ テーブル、最大レイヤー数を持つノードのレイヤー数 (ヘッダー ノードのレイヤー数は含まれません)、この属性を通じて、最適なレイヤー高さを持つノードのレイヤー数を決定できます。 O(1) 時間計算量で取得されます。

• length: ジャンプ テーブルの長さ、つまり、ジャンプ テーブルに現在含まれているノードの数 (ヘッド ノードは含まれません) を記録します。この属性により、プログラムは O( 1) ジャンプ リストの長さを時間計算量で返します。

  構造体の右側には 4 つの Redisのデータ構造のジャンプテーブルの詳細説明 構造体があり、次の属性が含まれています。

• ## レベル (レベル):
  1、2 を使用します。ノード 、L3 およびその他の単語はノードの各層をマークし、L1 は最初の層を表し、L は 2 番目の層を表します。
  各レイヤーには、フォワード ポインターとスパンという 2 つの属性があります。前方ポインタはテーブルの最後にある他のノードにアクセスするために使用され、スパンは前方ポインタが指すノードと現在のノードの間の距離を記録します (スパンが大きいほど、距離は長くなります)。上の図では、接続線上の数字の付いた矢印は前方ポインタを表しており、その数字がスパンです。プログラムがテーブルの先頭からテーブルの末尾まで移動するとき、アクセスはレイヤーの前方ポインタに沿って進行します。
  新しいジャンプ テーブル ノードが作成されるたびに、プログラムはべき乗則 (べき乗則、数値が大きいほど発生確率が小さくなります) に基づいてレベルとして 1 ～ 32 の値をランダムに生成します。配列のサイズ。このサイズはレイヤーの「高さ」です。

• 後方ポインタ:
  ノード内の BW とマークされたノードの後方ポインタは、現在のノードの前のノードを指します。バック ポインタは、プログラムがテーブルの末尾から先頭に移動するときに使用されます。前方ポインタとの違いは、各ノードが後方ポインタを 1 つだけ持つため、一度に 1 ノードしか後方に移動できないことです。

• スコア:
  各ノードの 1.0、2.0、および 3.0 は、ノードによって保存されたスコアです。ジャンプ テーブルでは、保存されたスコアに従ってノードが小さいものから大きいものへと配置されます。

• メンバー オブジェクト (oj):
  各ノードの o1、o2、および o3 は、ノードによって保存されたメンバー オブジェクトです。同じジャンプ テーブル内では、各ノードによって保存されるメンバー オブジェクトは一意である必要がありますが、複数のノードによって保存されるスコアは同じであってもかまいません。同じスコアを持つノードは、メンバー オブジェクトのサイズに従って辞書順に並べ替えられます。小さいメンバー オブジェクトを持つノードは前 (テーブルの先頭に近い方向) に配置され、大きいメンバー オブジェクトを持つノードは後ろ (テーブルの最後に近い方向) に配置されます。

2.2 Redis ジャンプ テーブルの一般的な操作の時間計算量

操作時間計算量スキップ テーブルの作成O(1) リリース指定されたジャンプ テーブルとそれに含まれるノードO(N)指定されたメンバーとスコアを持つ新しいノードを追加します平均 O (logN)、最悪の場合 O(logN) (N はスキップ リストの長さ)#指定されたメンバーとスコアを含むノードをスキップ テーブルから削除します指定されたメンバーとスコアを持つノードのランキングを返しますテーブル内 指定されたランキングでノードを返しますスコア範囲が指定された場合、ジャンプの最初のスコアを返します。この範囲に一致するリスト Node#スコア範囲を指定すると、この範囲に一致するジャンプ テーブル内の最後のノードを返します平均 O(logN)、最悪 O(logN) (N はジャンプ テーブルの長さ)スコア範囲を指定します。ただし、この範囲内にあるジャンプ テーブル内のすべてのノードは除きます。範囲平均 O(logN)、最悪 O(logN) (N はジャンプ リストの長さ)O(N)、N は分割するノードの数ですO(N), N は削除するノードの数。

平均は O(logN)、最悪は O(logN) (N はジャンプ テーブルの長さ)
平均 O(logN)、最悪 O(logN) (N はジャンプ テーブルの長さ)
平均 O(logN)、最悪 O(logN) (N はジャンプ リストの長さ)
#O(1)
	指定されたランキングの範囲。ただし、ジャンプ リスト この範囲内のノード
	0 ～ などのスコア範囲 (範囲) を指定します。 15 、 20 ～ 28 など。ジャンプ テーブル内の少なくとも 1 つのノードのスコアがこの範囲内にある場合は 1 が返され、そうでない場合は 0 が返されます。
	この記事の焦点 ジャンプ テーブルは、単一のリンク リストとインデックスに基づいて実装されます ジャンプ テーブルは、スペースと時間を交換することで検索速度を向上させます Redis では、シーケンス セットは、ノード要素が大きい場合、または要素の数が多い場合にスキップ リストを使用します。 Redis のスキップ リスト実装は、zskiplist と zskiplistnode の 2 つの構造で構成されます。zskiplist は、次の目的で使用されます。スキップ テーブル情報 (ヘッダー ノード、テーブル末尾ノード、長さなど) を保存し、スキップ テーブル ノードを表すために zskiplistnode が使用されます。 Redis の各スキップ テーブル ノードのレイヤーの高さは、1 ～ 32 の乱数です。 同じ ジャンプ テーブルでは、複数のノードに同じスコアを含めることができますが、各ノードのメンバー オブジェクトは一意である必要があります。ジャンプ テーブル内のノードは、スコアのサイズに従って並べ替えられます。スコアが同じ場合、ノードはメンバー オブジェクトのサイズに従って並べ替えられます。 概要 ジャンプ テーブルは、私たちにとって少し馴染みのないデータ構造かもしれません。この記事では、ジャンプ テーブルのデータ構造を簡単に紹介し、Redis でのジャンプ テーブルの使用法を分析します。次の記事では、引き続き Redis で使用されるデータ構造の整数コレクションを共有します。乞うご期待！＃＃＃

以上がRedisのデータ構造のジャンプテーブルの詳細説明の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。