私はこの質問をRedisのWebサイトにクロスポストしましたが、Pieter Noordhuisがそこに回答を提供しました。これは、ここでクロスポストしています：
それは正しいです。ソートされたセットは、RNGに依存して、ノードごとのレベル数を決定します（これは確率的なデータ構造です）。スキップリストの先頭にある要素の挿入/削除はO（1）ですが、理論上の最悪の場合のパフォーマンスはO（N）です（すべてのノードが同じレベルになります）。ただし、ノード間のレベルの分布を考慮すると、償却時間計算量はO（log N）です。