なぜRedis SortedSetはバランスツリーの代わりにスキップリストを使用しますか？

Question

はRedisの文書は以下のように言った：

ZSETs取得するために、同じ要素 を保持するために2つのデータ構造を使用して順序付けられたセットはO（ログ（N））を挿入し、ソート データ構造に動作を削除。

要素は、Redisオブジェクトを スコアにマッピングするハッシュテーブルに追加されます。同時に、エレメントはスキップリスト に追加され、Redisオブジェクトにスコアがマッピングされます（オブジェクトは の "view"のスコアでソートされます）。

私は非常に理解できません、誰かが私に詳細な説明を教えてくれますか？誰かが私に詳細な説明をくれますか？

Answer 1

まず、私はRedisの文書が何を言っているのかを知っていると思います。 Redis ordered setは、ユーザーが指定した要素のスコアで要素の順序を維持します。しかし、ユーザーがいくつかの赤いZset apisを使用している場合、それは要素argsを与えるだけです。例えば：

ZREM key member [member ...] 
ZINCRBY key increment member 
... 

それは文書が言ったと同じように、マッピングを維持し、ハッシュテーブルを使用するよう

Redisのは、このメンバー（要素）に約あるか値を知る必要があります。

要素が追加されていますRedisオブジェクトを スコアにマッピングするハッシュテーブル

メンバーを受け取ると、ハッシュテーブルを介してその値を見つけて、その設定を維持するためにスキップリストの操作を操作します。 redisは2つのデータ構造を使用して、異なるapiの必要性を満たすために二重マッピングを維持します。

私はウィリアム・プーの論文スキップリスト読み：バランス木に確率 代替を、スキップリストは非常にエレガントで、かつ回転より実装が簡単である見つけました。

また、私は一般的なバイナリバランスツリーが同じ時間コストでこの作業を行うことができると思います。もし私が見逃したことがあれば、plsを指してください。
1）彼らは非常にメモリ集約的ではありません。

Answer 2

Antirezは、いくつかの理由がありhttps://news.ycombinator.com/item?id=1171423
で見る、と述べました。基本的にはあなた次第です。ノードが所定のレベル数になる確率に関するパラメータを変更すると、btreeよりもメモリ集中が少なくなります。
2）ソートされたセットは、多くのZRANGEまたはZREVRANGE操作の対象となることがよくあります。つまり、スキップリストをリンクリストとしてトラバースします。この操作により、スキップリストのキャッシュ局所性は、少なくとも他の種類のバランスのとれたツリーの場合と同じくらい良好です。
3）実装やデバッグなどが簡単です。たとえば、スキップリストのシンプルさのおかげで、O（log（N））にZRANKを実装した拡張スキップリストを持つパッチ（Redis masterには既にあります）を受け取りました。コードの変更はほとんど必要ありませんでした。
耐久性について&スピードについては、より多くのコードを使用してRedisを最適化することは良い考えではないと考えています.IMHOはRedisターゲット（fsync（）コマンド）。とにかくパフォーマンスヒントが大きいので、ACID SQLデータベースでもこの機能を使用している人はほとんどいません。
スレッドについて：私たちの経験によれば、RedisはほとんどがI/O境界です。私は仮想メモリから物事を提供するためにスレッドを使用しています。あなたのリンクが非常に速く単一のコアを飽和させることができると仮定すると、すべてのコアを活用する長期的なソリューションは、複数のRedisインスタンス（ロックなし、コア数でほぼ完全スケーラビリティ）を実行し、 "Redis Cluster私が将来開発しようとしているソリューションです。