【スキップリスト】
スキップリスト とは？
最終更新:
💡 急行から各停へ乗り換えるように、飛ばしリンクで探すリスト
ソート済みの連結リストに複数段の飛ばしリンクを設けた確率的データ構造。ランダムに段数を決める方法では、検索・挿入・削除の期待時間はO(log n)、最悪はO(n)になる。
📌 このページのポイント
- 一番下の段には全要素があり、上の段のリンクは途中の要素を飛ばす
- 探す値を越えないように進み、進めなくなったら下の段へ移る
- 各要素の段数をランダムに決める方法では、期待時間O(log n)を目指せる
- 木の回転は不要だが、最悪時間や並行アクセスの安全性は別に考える
ひよこ スキップリストって普通のリンクリストと何が違うの？
ペンギン先生 整列した連結リストに、途中の要素を飛ばすリンクを何段も加えるんだ。上の段で大きく進み、下の段で細かく探す。急行から各停へ乗り換えるイメージだよ。次の値が探す値以上なら、そのリンクを進まず下の段へ移り、一番下で一致を確認する方法があるんだ。
ひよこ どの要素に飛ばしリンクを付けるか、どうやって決めるの？
ペンギン先生 代表的な方法はコイントスのような乱数だよ。新しい要素を入れるとき、一定の確率でもう1段上のリンクを持たせる操作を繰り返す。上の段ほど要素が少なくなる傾向があるけれど、必ず均等な間隔になるわけではないんだ。
ひよこ ランダムで大丈夫なの？偏ったりしない？
ペンギン先生 偏る可能性はあるよ。論文のランダムな段数決定などの条件では、検索・挿入・削除は期待時間O(log n)だけれど、最悪はO(n)。いつでも対数時間を保証する平衡木とは違う。期待時間と、1回の操作にかかる時間を分けて考えるんだ。
ひよこ 実際にどこで使われてるの？
ペンギン先生 RedisのSorted Setにはスキップリストを使う内部表現があるよ。ただし、小さいSorted Setなどでは別の省メモリ表現も使う。LevelDBにもスキップリストの実装がある。一つの製品のすべてのデータを、この構造だけで管理するわけではないんだ。
ひよこ 平衡二分木より良いことってあるの？
ペンギン先生 木の回転を使わず、挿入や削除をリンクの付け替えで表せるよ。ただし、並行処理の安全性は別の設計が必要。たとえばLevelDBの実装は、読み取りには内部ロックが不要でも、書き込み同士は外部のロックなどで競合しないよう調整が必要と説明している。スキップリストなら自動的に全部ロックフリー、とは言えないんだ。
まとめ：ざっくりこれだけ覚えればOK！
「スキップリスト」って出てきたら「段ごとの飛ばしリンクで探す、整列したリスト」と思えばだいたいOK！
📖 おまけ：英語の意味
「Skip List」 ＝ 飛ばしリスト
💬 Skip（飛ばす）の名の通り、途中の要素を飛ばすリンクを持つリストだよ。William Pughの論文が1990年に発表されている。