1

REDIS のドキュメントでは、ソートされたセットに対する挿入操作と更新操作は O(log(n)) であると記載されています。

この質問では、基礎となるデータ構造であるスキップ リストに関する詳細を指定しています。

ただし、私がよく知らない REDIS 実装に依存する特殊なケースがいくつかあります。

  • ソートされたセットの先頭または末尾に追加することは、おそらく O(log(n)) 操作ではなく、O(1)ですよね? この質問は留保に同意するようです。
  • 要素を取り出してわずかに異なるスコアで再度挿入するか、順序が変更されていないことを確認する必要があるため、順序が変更されていない場合でもメンバーのスコアを更新することはまだ O(log(n)) です。変更されないため、違いはスコアの挿入または更新の間の一定の操作のみです。右？この場合、私が間違っていることを本当に願っています。

どんな洞察も大歓迎です。

4

2 に答える 2

2

注: リストが特定のサイズ (max_ziplist_entries) を超えるとスキップ リストが使用され、そのサイズを下回ると zip リストが使用されます。

再。最初の質問 - スキップ リストはバイナリ ツリーの一種であるため、まだ O(log(n)) になると思います。そのため、ヘッド/テール ノードがどこにあるかは保証されません。

再。2 番目の質問 - ソースによると、スコアの変更は、メンバーの削除と再追加によって実装されます: .com/antirez/redis/blob/209f266cc534471daa03501b2802f08e4fca4fe6/src/t_zset.c#L1272

于 2014-11-06T13:38:31.763 に答える