← 一覧へ
データベース
#스킵리스트#확률적자료구조#인덱스#RedisZSET#동시성
最終更新 · 2026-11-12

スキップリスト(Skip List)

1. 概要

A. 定義

スキップリスト(Skip List)とは、ソート済み連結リストの上に複数層の疎なショートカット(express lane)ポインタを確率的に積み上げ、平衡二分探索木のような複雑な回転・再平衡なしに探索・挿入・削除を平均O(log n)で行う確率的(probabilistic)データ構造である。

スキップリストは1990年にWilliam Pughが「平衡木を置き換える確率的な代替(A Probabilistic Alternative to Balanced Trees)」として提案したデータ構造である。基本的な発想は単純である。ソート済みの単方向連結リストは実装が容易だが探索がO(n)で遅い。そこに一つずつ飛び越える上位レベルのリストを載せると探索範囲を半分ずつ狭められ、これを複数層にわたり繰り返せば二分探索に近い効果を連結リストだけで達成する。各ノードが何層まで上がるかはコイン投げ(確率 p)で決めるため、木のように入力順序によって構造が偏らず、期待値の次元では常に平衡を保つ。

核心的な洞察は「平衡を強制的に合わせず確率的に期待する」という点である。AVL・赤黒木は挿入・削除のたびに不変条件を復元するため回転と彩色を行うが、このロジックは実装が厄介で、とりわけ並行環境で広範なロックを引き起こす。スキップリストは再平衡演算そのものがなくコードが短く、各ノードが局所的なポインタ数個だけを変えるため、ロック範囲が狭く並行性に有利である。この性質ゆえにRedis・LevelDB・HBaseなど多数の実務システムが中核インデックスとして採用した。

B. 登場背景と必要性

ソートデータに対する探索・範囲問い合わせ・順序維持が同時に必要となる状況は、データベースインデックス、インメモリストア、優先度付きキューなどで普遍的である。伝統的な解法である平衡二分探索木(B-Tree・赤黒木)は最悪でもO(log n)を保証するが、挿入・削除時の再平衡(回転・分割・併合)ロジックが複雑である。この複雑さはバグの温床となるだけでなく、マルチコア環境で構造変更が上位ノードまで伝播してロック競合を増大させる。すなわち「正確な平衡」の代償として「実装・並行性のコスト」を払う。

スキップリストはこの点を狙う。完全な平衡の代わりに確率的平衡を選ぶことで、再平衡コードを丸ごと除去しても平均O(log n)を得る。とりわけ挿入・削除が隣接する少数のポインタのみを修正するため、ノード単位の細粒度ロック(fine-grained locking)やロックフリー(lock-free)実装が木よりはるかに容易である。ハッシュテーブルが順序を保存できず範囲問い合わせに不向きなのに対し、スキップリストは下位レベルが完全なソートリストであるため、範囲スキャン(range scan)と順次アクセスが自然である。「実装の単純さ + 範囲問い合わせ + 並行性」という三つの要求が重なる場所で、スキップリストが実務の選択肢として浮上した背景である。

2. 構造と探索原理

スキップリストは、下段にすべての要素を収めた完全なソート連結リスト(レベル1)を置き、その上に要素の一部のみを含む上位レベルを積んだ多層連結リストである。各ノードは自身のレベル数だけ前方ポインタ(forward pointer)配列を持ち、最左の先頭(head)ノードは最大レベルまでのポインタを保持して探索の入口となる。

flowchart LR
    subgraph L3["レベル3 (最も疎なショートカット)"]
      H3["HEAD"] --> N6_3["30"] --> NIL3["NIL"]
    end
    subgraph L2["レベル2"]
      H2["HEAD"] --> N2_2["10"] --> N6_2["30"] --> N9_2["60"] --> NIL2["NIL"]
    end
    subgraph L1["レベル1 (全要素を含む)"]
      H1["HEAD"] --> A["5"] --> B["10"] --> C["20"] --> D["30"] --> E["45"] --> F["60"] --> G["75"] --> NIL1["NIL"]
    end

上の図で値10・30・60は上位レベルまで昇格してショートカットの役割を果たす。上位レベルは下に行くほど含む要素が増えピラミッド形を成し、理想的にはレベルkのノード数がレベルk−1の約p倍(通常p=1/2なら半分)になるよう設計する。この「層ごとに半分に減る」構造が二分探索の対数的な深さを生み出す。

探索(Search)は最上位レベルの先頭から出発し、現在のレベルで目標値を超えない限り右へ前進し、さらに進むと目標を通り過ぎる地点で一レベル下へ降りる。この過程をレベル1に到達するまで繰り返せば、飛び越え(ショートカット)で探索空間を階段状に狭め、平均O(log n)で目標に到達する。

flowchart TB
    S["探索開始: HEAD 最上位レベル"] --> C1{"右ノードのキー < 探すキー?"}
    C1 -->|"はい"| R["右へ前進 (ショートカット使用)"]
    R --> C1
    C1 -->|"いいえ (超過)"| C2{"現在のレベル > 1?"}
    C2 -->|"はい"| DN["一レベル下へ降下"]
    DN --> C1
    C2 -->|"いいえ (レベル1到達)"| CHK{"次ノードのキー == 探すキー?"}
    CHK -->|"はい"| FOUND["探索成功"]
    CHK -->|"いいえ"| NOT["探索失敗 (存在しない)"]

例えば値45を探すとする。レベル3で先頭の次は30であり30<45なので30へ前進するが、30のレベル3の次はNILでこれ以上進めないためレベル2へ降りる。レベル2で30の次は60であり60>45なのでレベル1へ降りる。レベル1で30→45へ一歩前進して45を見つける。単方向連結リストなら5・10・20・30・45まで五回比較せねばならないが、ショートカットのおかげで比較回数が減ることが分かる。

3. 挿入・削除とレベル決定の確率モデル

挿入・削除の共通の前提は、まず探索を実行しつつ、各レベルで「降りる直前のノード」をupdate[]配列に記録しておくことである。この配列は新ノードを差し込むか取り外す際にポインタを更新する隣接ノードの一覧となる。

挿入(Insert)は三段階で行われる。第一に、目標位置を探索しつつ各レベルのupdate[]を記録する。第二に、新ノードのレベルを確率的に決定する — レベル1から始めてコインを投げ、表(確率 p)が出る間はレベルを1ずつ上げ、裏が出れば止める。第三に、決定されたレベル数だけupdate[i]の前方ポインタを新ノードへ繋ぎ、新ノードのポインタは元々update[i]が指していたノードへ繋ぐ。このように挿入は決定されたレベル数(期待値は定数)だけのポインタのみを修正するため、回転のような広域演算がない。

削除(Delete)も探索でupdate[]を埋めた後、削除対象ノードが参加する各レベルで先行ノードのポインタを対象ノードの次へ迂回させることで終わる。すべてのレベルで対象が外れると、上位レベルが空になる場合はリストの現在の最大レベルを下げておける。削除が触れるポインタも対象のレベル数(期待値は定数)に比例する。

具体的な挿入例として、値50をレベル3のノードとして差し込む場合を見よう。まず先頭から50の位置を探索しつつ、レベル3・2・1それぞれで「50より小さい最後のノード」をupdate[3]、update[2]、update[1]に記録する。新ノードのレベルをコイン投げで3と決めたなら、レベル1・2・3の三層でupdate[i]の前方ポインタを50へ変え、50の三つのポインタをそれぞれ元々update[i]が指していたノードへ接続する。木なら平衡復元のために上位へ回転が伝播しうるが、ここでは正確に三対のポインタのみを再配線すれば終わる点が、構造変更の局所性をよく示す。

レベル決定の確率モデルはスキップリスト性能の根拠である。ノードがレベルk以上に上がる確率はp^(k−1)なので、p=1/2のときノードの約1/2はレベル1、1/4はレベル2以上、1/8はレベル3以上にのみ存在する。ノード一つの期待レベル数(ポインタ個数)は1/(1−p)で、p=1/2なら平均2個にすぎない。すなわち追加メモリは要素あたり平均ポインタ一個あまりで、空間計算量は依然としてO(n)である。リストの期待最大レベルはlog_(1/p) nであり、探索の期待比較回数は(log_(1/p) n)/p 程度と分析され、平均O(log n)が導かれる。ただしこれは期待値であり、運が悪ければ一つのノードが過度に高いレベルを引いて性能が揺らぎうるため、実装上最大レベルに上限(MaxLevel)を設ける。

演算 平均時間計算量 最悪時間計算量 備考
探索(Search) O(log n) O(n) 最悪は全ノードがレベル1のとき
挿入(Insert) O(log n) O(n) 探索 + 定数個のポインタ修正
削除(Delete) O(log n) O(n) 探索 + 定数個のポインタ修正
範囲問い合わせ O(log n + k) O(n) kは結果要素数、下位レベルの順次スキャン
空間 O(n) O(n log n) 期待ポインタ n/(1−p)個

表が示すとおり最悪計算量はO(n)だが、これは全ノードが偶然レベル1のみを引く確率的に極めて稀な事象であり、レベルが入力値に無関係に乱数で定まるため悪意ある入力で最悪を強制できない点が、木の偏り入力への脆弱性と対照的である。

4. 平衡木との比較および適用事例

スキップリストを平衡二分探索木(特に赤黒木・AVL)と比較すると選択基準が明確になる。両者とも平均O(log n)を提供するが、差は「平衡を保証する方式」で生じ、その差が実務的含意につながる。木は不変条件を厳格に守り最悪でもO(log n)を保証する代わりに再平衡ロジックが複雑で構造変更が上位へ伝播する。スキップリストは平衡を確率に委ね最悪保証を放棄する代わりにコードが単純で変更が局所的である。

区分 スキップリスト 赤黒木 B+Tree
平衡方式 確率的(乱数レベル) 決定的(色・回転) 決定的(分割・併合)
平均探索 O(log n) O(log n) O(log n)
最悪探索 O(n) (稀) O(log n) 保証 O(log n) 保証
実装難易度 低 高 高
並行性(同時性) 有利(局所的修正) 不利(広域ロック) 中(ノードロック)
範囲問い合わせ 優秀(下位レベルスキャン) 中間順序巡回が必要 優秀(リーフ連結)
キャッシュ局所性 ポインタ追跡で低い 低い 高い(ブロック単位)

この比較から実務的含意が現れる。ディスクベースのデータベースインデックスは一度のI/Oで多くのキーを読む必要があり、ブロック単位のキャッシュ局所性に優れたB+Treeが支配的である。一方インメモリ環境ではポインタ追跡コストが相対的に小さく実装の単純さ・並行性の利点が大きくなり、スキップリストが競争力を持つ。すなわち「どこに保存するか(ディスク対メモリ)」が選択を分ける核心変数である。

数値で体感すると、ショートカットの威力が明確になる。1,000万(n=10⁷)人が参加するゲームのリーダーボードで特定ユーザーの順位を問い合わせるとする。単一のソートリストなら平均500万回の比較が必要だが、p=1/2のスキップリストは期待レベルがlog₂(10⁷)≈23層にすぎず、数十回の比較で目標に到達する。スコア上位100人を取る範囲問い合わせ(ZRANGE)も入口までO(log n)で降りた後に下位レベルを100マス順次スキャンすればよいのでO(log n + k)で終わる。このように「順序維持 + 順位・範囲」が同時に必要なワークロードで、スキップリストはハッシュ・配列が与えられない組み合わせを提供する。

適用事例はこの原理を裏付ける。第一に、Redisのソート済み集合(Sorted Set, ZSET)はスコア基準のソート・順位問い合わせ・範囲問い合わせのためにスキップリストをハッシュテーブルと併用する — ハッシュでメンバー→スコアをO(1)で見つけ、スキップリストでスコア順の範囲・順位(ZRANGE・ZRANK)をO(log n)で処理する。リーダーボードの順位問い合わせが代表的な活用である。第二に、LevelDB・RocksDBのMemTableはディスクへ降ろす前に書き込みをメモリに集める構造としてスキップリストを使うが、これは多数の書き込みスレッドが同時に挿入してもロック競合が小さくソート状態に保たれ、その後SSTableへ順次flushするのに適するためである。第三に、Apache HBaseのMemStoreとJava標準ライブラリのConcurrentSkipListMap/ConcurrentSkipListSetも同じ理由でスキップリストベースの並行ソートデータ構造を提供する。これらはすべて「順序維持 + 高い同時書き込み」という共通の要求を持つ。

5. 深化: ロックフリー・並行スキップリストと設計変種

スキップリストが現代システムで脚光を浴びる決定的な理由は並行性親和性である。木の再平衡は回転がルート方向に伝播して広い範囲をロックせねばならないが、スキップリストの挿入・削除は隣接する先行ノードのポインタのみを変えるため、細粒度ロックまたはロックフリー(lock-free)実装が可能である。JavaのConcurrentSkipListMapはCAS(Compare-And-Swap)演算のみでポインタを更新するロックフリーアルゴリズムを採用し、ロックなしでも線形化可能(linearizable)なソートマップを提供する。削除時にはノードを即座に外さず論理削除マーカー(marker)を置いた後に物理的に整理する手法で同時アクセスの整合性を守る。このように「構造変更の局所性」がそのまま「同時性の拡張性」に直結する点が、木に対する本質的な差別点である。

設計変種も多様である。確率pを1/4に下げるとノードあたり平均ポインタが1/(1−p)=4/3個に減ってメモリを節約する代わりにレベルが浅くなり探索比較がやや増え、pを1/2にすると探索が速くなる代わりにポインタが増えて空間をより使う — すなわちpは時間・空間の調整つまみである。決定論が必要な環境では乱数の代わりに規則でレベルを付与し最悪O(log n)を保証する決定的スキップリスト(Deterministic Skip List)が提案され、キャッシュ効率を高めるため一つのノードに複数要素を収めるアンロールド(unrolled)・Bスキップリスト変種も研究される。近年はインメモリ・リアルタイム分析の需要が高まり、ログ構造ストレージ(LSM-Tree)のメモリ階層の標準データ構造としてスキップリストの地位がいっそう強固になっている。

6. 考慮事項および示唆点

スキップリストを技術士の観点で適用・評価する際は、次を総合的に考慮せねばならない。

  • 保存媒体に応じた選択戦略が先行せねばならない。 ポインタ追跡はキャッシュミスを誘発するため、ブロック単位I/Oが支配するディスクインデックスにはB+Treeが、ポインタコストが小さく実装・同時性の利点が大きいインメモリ構造にはスキップリストが適する。媒体特性を無視してデータ構造を選ぶと性能が逆転しうる。

  • 最悪計算量の保証が必須な領域には慎重であらねばならない。 スキップリストは平均O(log n)だが最悪はO(n)である。確率的に稀でも、ハードリアルタイム(hard real-time)・安全必須システムのように最悪遅延の上限を契約せねばならない領域では、決定的平衡木や決定的スキップリストを検討する方が安全である。

  • 確率パラメータpとMaxLevelをデータ規模に合わせて調整する。 pは時間・空間のトレードオフを決め、MaxLevelは予想最大要素数nに対しlog_(1/p) n以上に取らねばショートカット効果が保証されない。乱数源が偏ると理論的平衡が崩れるため良質な乱数生成器を使わねばならない。

  • 並行性要求が高いほどスキップリストの相対的利点が大きくなる。 多数スレッドの同時挿入・削除が頻繁なインメモリストア・キャッシュ・メッセージキューでは、ロックフリースキップリストが木より拡張性の面で有利である。逆に単一スレッド・読み取り支配のワークロードならキャッシュ局所性のよいデータ構造がより良いこともあり、ワークロード特性(読み書き比率・並行性水準)を選択基準とせねばならない。

  • 範囲問い合わせ・順位演算の要求を併せて設計する。 ハッシュテーブルはメンバーシップ・点(point)問い合わせに強いが順序・範囲に弱い。リーダーボード・時系列範囲問い合わせのように順序が核心のワークロードでは、Redis ZSETのようにハッシュとスキップリストを併置して各演算を最適なデータ構造で処理するハイブリッド設計が効果的である。

総合すると、スキップリストは「完全な平衡を確率的平衡で置き換え」て実装の単純さ・並行性・範囲問い合わせという実質的利得を得る工学的妥協の典型である。ディスク領域ではB+Treeに場所を譲るが、インメモリ・高同時性・順序維持という現代データインフラの要求が高まるほどその活用価値はむしろ拡大しており、保存媒体・最悪保証の要求・並行性水準・問い合わせパターンを軸に木系と比較して適切な場所に配置することが設計の核心である。

参考資料


一言まとめ: スキップリストはソート連結リストの上に確率的にショートカットポインタを積み、平均O(log n)の探索・挿入・削除を再平衡なしに達成するデータ構造であり、実装の単純さと並行性・範囲問い合わせの利点ゆえにRedis ZSET・LevelDB MemTableなどインメモリ高同時性システムの中核インデックスとして用いられる。