Redisのスキップリストの仕組みは何ですか？
Redisのスキップリストは、ソート済みコレクションを実装するための基盤となるデータ構造で、一部の正確性を犠牲にして検索効率を向上させています。
スキップリストの仕組みは次のとおりです。
- ノード構造：スキップリストは複数のノードで構成されており、各ノードは値と、他のノードを指すポインター配列を含んでいます。ポインター配列内の各ポインターは現在のノードの値よりも大きいノードを指しており、いわばそのポインターは現在のノードと自分より大きなノードをつなぐと考えて良いでしょう。
- 階層構造：スキップリストのノードは階層構造で整理されており、最初のレイヤにはすべてのノードが含まれ、レイヤごとにノード数は前のレイヤの 1/2 になります。それぞれのノードのポインタ配列の長さもランダムに生成されており、通常 ポインタ配列の長さは 1 ～ 32 のランダムな値になります。
- 最上位のヘッダノードから逐次右移動し、目的値より大きいノードが見つかればその下の階層に移動し、階層を下ろしながら同じ操作を繰り返す。最下層で目的値が見つかれば終了、それより大きいノードが見つからなくなった場合も終了する。
- 挿入方法：ジャンプ表に値を挿入するには、まず最下層で適切な位置を見つけて、それから上層に向けて挿入し、一定の確率に基づいて新しい階層を生成します。
- 削除方法：ジャンプ表から値を削除するとき、まず最下層で対象ノードを見つけ、その後上位の層を順番に削除していきます。削除したノードの結果、ある層のノード数が0になった場合は、その層を削除します。
スキップリストにより、Redisは挿入、削除、検索操作を O(log N) の時間複雑度で行うことができるため、通常のリンクリスト (時間複雑度 O(N)) よりもはるかに効率的です。また、スキップリストは赤黒木 (時間複雑度 O(log N)) よりも単純で、実装が容易です。
