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

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

順序付きコレクションに使用できる内部実装には、圧縮リスト (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 サイトの他の関連記事を参照してください。