Redisデータ構造の概要：ソートされたセット

ソートされたセットは、Redisで最も高度なデータ構造の一部です。並べ替えられたセットは、基本的に、数値スコアが関連付けられた順序付けされたRedis文字列の一意のコレクションです。順序付けは、スコアと文字列辞書式順序に基づいています（これについては後で詳しく説明します）。スコアが繰り返される可能性がある間、文字列は一意である必要があります。

リストのほかに、注文された唯一のリストです。 Redisのデータ構造であり、リストのいずれかの部分へのアクセスが重要な場合はリストよりも優先されます（リストの終わりへのアクセスを提供するリストとは異なります）。ソートされたセットでの平均的なケースの挿入、削除、検索はO（N）です。ここで、Nはセット内の要素の数です。

並べ替え

並べ替えられたセットのスコアは、-（2 ^）と+（2 ^）の範囲の倍精度64ビット浮動小数点数を含みます。並べ替えられたセットは、スコアの昇順で並べ替えられます。スコアは既存のキーに対して更新できます。スコアの結びつきを解消するために、ソートされたセット内の文字列は辞書式順序で昇順で並べられます。 Redis 2.8では、この辞書式順序を活用するための新機能が実装されました。辞書式順序クエリです。これには、後で見る魅力的なユースケースがあります。

コマンド

Redisで並べ替えられたセットは、単純なセット、取得、メンバー数から複雑な辞書式範囲の計算まで、さまざまな操作をサポートします。約25以上の操作がサポートされています。それらのサブセットを見ていきます。基本的なものから始めましょう：

# ZADD key [NX|XX] [CH] [INCR] score member [score member ...] Add elements into the set
# O(log(N) where N is the number of elements in the set
# [NX|XX], [CH] & [INCR] available on > 3.0.2
127.0.0.1:6379> zadd scoreboard 999 "anorak"
(integer) 1
# Analogous: use ZREM key member [member ...] to remove members from a sorted set.
# ZCARD key O(1): Cardinality of the set
127.0.0.1:6379> zcard scoreboard
(integer) 1
# Insert multi
127.0.0.1:6379> zadd scoreboard 99 "daito" 99 "shoto" 199 "aech" 299 "art3mis" 399 "parzival"
(integer) 5
# ZSCORE key member. O(1) Returns the score of member in the sorted set at key.
127.0.0.1:6379> zscore scoreboard parzival
"399"
# ZRANK key member O(log(N)) Get the rank of the member.
127.0.0.1:6379> zrank scoreboard anorak
(integer) 5
127.0.0.1:6379> zrank scoreboard shoto
(integer) 1
# ZREVRANK key member O(log(N)) Get the rank of the member with scores ordered high to low
127.0.0.1:6379> zrevrank scoreboard anorak
(integer) 0
127.0.0.1:6379> zrevrank scoreboard shoto
(integer) 4
# ZINCRBY key increment member O(log(N)) Increments the score of member in the sorted set stored at key by increment.
127.0.0.1:6379> zincrby scoreboard 100 parzival
"499"

上記の操作は、並べ替えられたセットで可能な基本的な操作の一部です。ソートされたセットの実際の値は、セット内のクエリに基づいた範囲で輝いています。それらを見てみましょう。

# ZRANGE key start stop [WITHSCORES]. O(log(N)+M) with N being the number of elements in the sorted set and M the number of elements returned.
# start and stop are inclusive zero based indexes.
127.0.0.1:6379> zrange scoreboard 0 -1 WITHSCORES
 1) "daito"
 2) "99"
 3) "shoto"
 4) "99"
 5) "aech"
 6) "199"
 7) "art3mis"
 8) "299"
 9) "parzival"
10) "499"
11) "anorak"
# 0: 1st member. -1: last member
# Analogous: ZREVRANGE key start stop [WITHSCORES]
127.0.0.1:6379> zrevrange scoreboard 0 -1 WITHSCORES
 1) "anorak"
 2) "999"
 3) "parzival"
 4) "499"
 5) "art3mis"
 6) "299"
 7) "aech"
 8) "199"
 9) "shoto"
10) "99"
11) "daito"
12) "99"
# ZRANGEBYSCORE key min max [WITHSCORES] [LIMIT offset count]. O(log(N)+M) Returns all the elements in the sorted set at key with a score between min and max (inclusive)
# Analogous: ZREVRANGEBYSCORE key max min [WITHSCORES] [LIMIT offset count]
# 499 <= score <= +inf 127.0.0.1:6379> zrangebyscore scoreboard 499 +inf
1) "parzival"
2) "anorak"
# 499 < score <= +inf 127.0.0.1:6379> zrangebyscore scoreboard (499 +inf
1) "anorak"
# ZCOUNT key min max O(log(N)) Returns the number of elements in the sorted set at key with a score between min and max.
127.0.0.1:6379> zcount scoreboard -inf 499
(integer) 5
127.0.0.1:6379> zcount scoreboard -inf +inf
(integer) 6

他の同様の範囲関連コマンドは、ZREMRANGEBYRANK、ZREMRANGEBYSCOREなどです。

Redis 2.8で導入されたsetqueryコマンドの別のセットがあります。それはレキシコグラフィック範囲（* BYLEX）コマンドです。これらのコマンドの間隔の指定方法の詳細は、ここに記載されています。これらのコマンドが正しく機能するための要件は、ソートされたセットのメンバーが同じスコアを持っている必要があることです。辞書式範囲を操作するための主なコマンドは、ZRANGEBYLEX、ZREVRANGEBYLEX、ZREMRANGEBYLEX、およびZLEXCOUNTです。いくつかの例を見てみましょう：

127.0.0.1:6379> zadd lexscores 0 dd 0 aa 0 ccc 0 aaa 0 bb 0 d 
(integer) 6
# Once inserted, lexicographic sorting for free!
127.0.0.1:6379> zrange lexscores 0 -1
1) "aa"
2) "aaa"
3) "bb"
4) "ccc"
5) "d"
6) "dd"
# ZRANGEBYLEX key min max [LIMIT offset count]. O(log(N)+M). min max specify range. LIMIT is like limit in SQL.
# min: exclude a max: exclude c
127.0.0.1:6379> ZRANGEBYLEX lexscores (a (c
1) "aa"
2) "aaa"
3) "bb"
# min: exclude a max: include c
127.0.0.1:6379> ZRANGEBYLEX lexscores (a [c
1) "aa"
2) "aaa"
3) "bb"
# min: exclude a max: include ccc
127.0.0.1:6379> ZRANGEBYLEX lexscores (a [ccc
1) "aa"
2) "aaa"
3) "bb"
4) "ccc"
# min: exclude aa max: include cccc
127.0.0.1:6379> ZRANGEBYLEX lexscores (aa [ccc
1) "aaa"
2) "bb"
3) "ccc"
# min: exclude aa max: upto all
127.0.0.1:6379> ZRANGEBYLEX lexscores (aa +
1) "aaa"
2) "bb"
3) "ccc"
4) "d"
5) "dd"

ソートされたセットのさらに別のコマンドセットは、和集合と共通部分の操作です。

内部

ソートされたセットは、デュアルデータ構造として実装されます。これは、ハッシュリストとスキップリストの両方の組み合わせです。ハッシュ部分はオブジェクトをスコアにマップし、スキップリストはスコアをオブジェクトにマップします。以前の投稿から、Redisでハッシュがどのように実装されているかはすでにわかっています。スキップリストにより、検索が高速になり、平均してほとんどの操作がO（log N）になります。スキップリストはファイルt_zset.cに実装されています。

他のほとんどのRedisデータ構造と同様に、並べ替えられたセットでさえ、小さい場合はサイズが最適化されます。並べ替えられたセットは、特定のサイズになるまでハッシュとしてのみ保存されます。このサイズを制御する構成パラメーターは次のとおりです。zset-max-ziplist-entries （デフォルトは128）および zset-max-ziplist-value （デフォルトは64）。
サイズの見積もり：https：//stackoverflow.com/questions/6076342/is-there-a-practical-limit-to-the-number-of-elements-in-a-sorted- set-in-redis

アプリケーション

高度なデータ構造であるため、並べ替えられたセットにはさまざまなユースケースがあります：

最も明白な使用例は、スコアボードとしての使用です。スコアでソートされた一意のメンバーの順序付きリストを維持します。たとえば公式のRedisドキュメントで説明されているMMORPGのリーダースコアボード。
同じスコアのソートされたセットは、Redisのインデックスとして使用されます。これは、非常に単純なユースケースから非常に複雑なユースケースまでさまざまです。 Redisのドキュメントには、ソートされたセットを使用したインデックス作成に関するすばらしい記事があります。
並べ替えられたセットを使用したインデックス作成の特殊なケースは、Redis3.2.0で導入されたRedis用のGEOAPIです。
サイズは、並べ替えられたセットを使用する際の考慮事項です。複雑なバッキングデータ構造を考えると、ソートされたセットのメモリフットプリントは比較的大きくなります。正確な数は、データセットの性質によって異なります。このStackOverflowの投稿では、適切なサイズのデータセットの球場番号について言及しています。

並べ替えられたセットにはかなり高度なユースケースがあるため、並べ替えられたセットのそのようなユースケースについては、以降の投稿で説明します。とりあえず、簡単な例を見てみましょう。

MOOCをゲーム化してください！

Redisビットマップに関する前回の投稿では、非常に人気のあるMOOCをサポートする開発者でした。ファシリテーターは、コミュニティの投稿に貢献しているトップの学生を追跡するリーダーボードを使用してコースをガミファイすることを決定します。コースコミュニティの投稿に投稿された問題に対する受け入れられた回答の数が最も多い学生は、毎週特別な言及を受け取ります。
これは、Redisソートセットとも呼ばれる一意のキーのスコアベースの順序付けの典型的な使用例です。学生IDはメンバーになり、スコアは受け入れられた回答の数になります。 ZINCRBYを使用してスコアを更新する場合がありますリアルタイムで、または毎日または毎週実行できるバックグラウンドジョブで。明らかに、私たちのユースケースではリアルタイムでスコアを更新する必要があります。初期挿入用ZADD 新しいフラグの1つがあれば便利です。スコアボードを生徒に表示するには、逆範囲クエリ（ ZREVRANGE ）を利用する必要があります。など）

脚注

Redisデータ構造シリーズの他の投稿：

セット
ハッシュ
ビットマップ