ZADD の redisドキュメントには、操作が O(log N ) であると記載されています。
ただし、挿入された要素がソート順の最初または最後にある場合、ZADD が O(log N ) よりも優れているかどうかは誰にもわかりませんか?
たとえば、特定の実装では、これは O(1) になる可能性があります。
具体的には、redisチュートリアルには次のように記載されています。
ソートされたセットは、スキップ リストとハッシュ テーブルの両方を含むデュアル ポート データ構造を介して実装されるため、要素を追加するたびに、Redis は O(log( N )) 操作を実行します。
最初と最後に O( k ) 挿入をサポートするようにスキップ リストを変更することはもっともらしく思われます。ここで、 kはスキップ リストの最大レベルです。
私は Redis の Web サイトにこの質問をクロスポストしましたが、Pieter Noordhuis が回答を提供してくれました。
それは正しいです。ソートされたセットは、RNG に依存してノードごとのレベル数を決定します (これは確率論的データ構造です)。スキップリストの先頭での要素の挿入/削除は O(1) になる可能性がありますが、理論上の最悪の場合のパフォーマンスは O(N) (すべてのノードが同じレベルを持つ場合) です。ただし、ノード間のレベルの分布を考慮すると、償却された時間の複雑さは O(log N) になります。
kとlog（N ）の間に関係はありますか？それらが一定の要因で関連付けられている場合、実際には何も変更されていません。（その関係が存在するかどうかはわかりませんが、トピックに関するウィキペディアのページがレイヤー構造でその関係を持っていることを考えると、非常にもっともらしいようです。OTOH、ページは証明にリンクしておらず、私は感じません今すぐ手でそれを導き出すようなものなので、これは推測にすぎません。）
また、一般に、アルゴリズム全体がO（log N）であるという事実は、特定の特殊なケース（O（1）など）の改善を妨げるものではありません。