Redis で順序付けられたコレクションの内部実装を実装する方法-Redis-php.cn

順序付きコレクションの内部実装

順序付きコレクションに使用できる内部実装には、圧縮リスト (ziplist) とスキップリスト (skiplist) という 2 つがあります。次に、それぞれについて詳しく見ていきます。

圧縮リストを内部実装として使用する

順序付きセット内の要素の数がzset-max-ziplist-entries(デフォルトは 128) 未満の場合、およびeach 要素メンバーの長さがzset-max-ziplist-value(デフォルトは 64 バイト) 未満の場合、圧縮リストが順序付きセットの内部実装として使用されます。

各 set 要素は、互いに近接した 2 つの圧縮リストノードで構成されます。最初のノードは要素のメンバーを保存し、2 番目のノードは要素のブランチを保存します。圧縮リスト内の要素をスコアサイズの順に並べることで、メモリスペースの使用量を効果的に削減できます。

たとえば、zaddコマンドを使用して、圧縮リストで実装された順序付きセットを作成します。

127.0.0.1:6379> zadd one-more-zset 1 one 2 two 3 three (integer) 3 127.0.0.1:6379> zrange one-more-zset 0 -1 1) "one" 2) "two" 3) "three" 127.0.0.1:6379> object encoding one-more-zset "ziplist"

ログイン後にコピー

内部実装としてジャンプテーブルを使用します

順序付きセット内の要素の数がzset-max-ziplist-entries(デフォルトは 128) 以上の場合、または各要素メンバーの長さが # 以上の場合##zset-max-ziplist-value(デフォルトは 64 バイト)、順序付きセットの内部実装としてスキップリストを使用します。

現時点では、オーダードセットには実際には 2 つの構造が含まれており、1 つはジャンプテーブル、もう 1 つはハッシュテーブルです。

ジャンプリストでは、すべての要素が小さいものから大きいものへの順序で配置されます。ジャンプテーブルのノードの

objectポインタは要素メンバーの文字列オブジェクトを指し、scoreは要素のスコアを保存します。 Redis は、ジャンプテーブルを通じて、スコア範囲、ランキング、その他の順序付きセットの操作を迅速に実行できます。

ハッシュテーブルでは、要素メンバーから要素スコアへのマッピングが順序付きセットに対して作成されます。キーと値のペアでは、キーは文字列オブジェクトで要素メンバーを指し、値は要素のスコアを保持します。 Redis は、ハッシュテーブルを通じて、指定された要素のスコアを迅速に見つけることができます。

順序付きセットはジャンプテーブルとハッシュテーブルの両方を使用しますが、どちらのデータ構造もポインターを使用して、追加のメモリを無駄にすることなく、要素内のメンバーとスコアを共有します。

たとえば、

zaddコマンドを使用して、スキップテーブルを実装した順序付きセットを作成します。

127.0.0.1:6379> zadd one-more-zset 1 long-long-long-long-long-long-long-long-long-long-long-long-long-long (integer) 1 127.0.0.1:6379> zrange one-more-zset 0 -1 1) "long-long-long-long-long-long-long-long-long-long-long-long-long-long" 127.0.0.1:6379> object encoding one-more-zset "skiplist"

ログイン後にコピー

内部実装された変換

When When an順序付きセットは内部実装として圧縮リストを使用し、順序付きセットに長い要素メンバーが追加された場合、または順序付きセット内の要素が多すぎる場合、順序付きセットはジャンプに変換されます。。内部実装として圧縮リストを使用する順序付きセットはスキップリストに変換されません。

たとえば、最初に内部実装として圧縮リストを含む順序付きセットを作成します。

127.0.0.1:6379> zadd one-more-zset 1 one 2 two 3 three (integer) 3 127.0.0.1:6379> zrange one-more-zset 0 -1 1) "one" 2) "two" 3) "three" 127.0.0.1:6379> object encoding one-more-zset "ziplist"

ログイン後にコピー

次に、長いメンバーを持つ要素を追加すると、Jump に変換されます。内部実装としてのリスト:

127.0.0.1:6379> zadd one-more-zset 4 long-long-long-long-long-long-long-long-long-long-long-long-long-long (integer) 1 127.0.0.1:6379> zrange one-more-zset 0 -1 1) "one" 2) "two" 3) "three" 4) "long-long-long-long-long-long-long-long-long-long-long-long-long-long" 127.0.0.1:6379> object encoding one-more-zset "skiplist"

ログイン後にコピー

次に、長いメンバーの要素が順序付きセットから削除されます。順序付きセットは引き続き内部実装としてジャンプリストを使用します:

127.0.0.1:6379> zrem one-more-zset long-long-long-long-long-long-long-long-long-long-long-long-long-long (integer) 1 127.0.0.1:6379> zrange one-more-zset 0 -1 1) "one" 2) "two" 3) "three" 127.0.0.1:6379> object encoding one-more-zset "skiplist"

ログイン後にコピー

以上がRedis で順序付けられたコレクションの内部実装を実装する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。