Zenn
❓

スキップリストはなぜBSTほど採用されないのか？

2024/12/10に公開
algorithm
Computer science
初心者
tech

二分探索木 (BST) の代替として使われるデータ構造にスキップリスト (Skip List) というものがあります。シンプルなアイデアで実装も理解しやすいのですが、BSTほどメジャーではない理由が気になったので調査してみました。

スキップリストの特徴

スキップリストは、連結リストの拡張として設計されながら、ツリーのような性能を持つデータ構造です。以下はその簡単な構造の例です：

Level 3: A ------> C ----------------> Z
Level 2: A ------> C ------> X ------> Z
Level 1: A -> B -> C -> M -> X -> Y -> Z
  • 特徴
    • 階層構造:
      • 一番下のレベルは通常のソートされた連結リスト
      • 上位レベルは一部のノードだけをリンクしており、検索時に下位レベルをスキップできる
      • 最上位レベルには最小限のノードのみが含まれる（例: リストの先頭と末尾）
    • 効率性:
      • 検索・挿入・削除の期待時間計算量はO(\log{}n)
    • シンプルさ:
      • 実装が比較的簡単で、平衡ツリーより直感的に理解できる

実装も含めた詳細について知りたい方はAdvanced Data Structures Series— Skip Listにわかりやすい解説がありますので、ご参照ください。

BSTのほうがなぜメジャー？

BST（特に平衡BST）が一般的に使われる理由を、スキップリストとの比較で整理しました。

調査をしてみると、BSTは1960年に登場していますが、SkipListは1989年にWilliam Pugh氏によって発明されています。およそ30年の差があり、実装の成熟度や標準ライブラリのサポートの点で、BSTが優位に立っています。

項目 BST SkipList
時間計算量 ✅ -
メモリ効率 ✅ -
ロバスト性 ✅ -
クエリ拡張性 ✅ -
並列処理対応 - ✅

時間計算量の保証

スキップリストの検索・挿入・削除の期待計算量はO(\log{}n)と効率的ですが、ランダム性に依存しているので、最悪ケースでO(n)になる可能性があります。一方で、平衡BSTでは挿入・削除のたびにリバランスを行うので、最悪ケースでもO(\log{}n)の計算量を保証しています。このような安定性は、実務で性能保証が求められる場面において特に重要です。そのため、パフォーマンスの一貫性が重視される場合には平衡BSTが優先されることが多いのです。

メモリ効率

スキップリストは一つのデータに対して階層を作るために複数のポインタが必要となり、メモリ消費量が多くなります。BSTはノードに対して左右2つのポインタのみで済むのでメモリ効率が高くなります。メモリ使用量を抑えたい、またはメモリ効率が重要な場面では、BSTが適した選択肢となります。

ロバスト性

スキップリストは階層分割がランダム性に依存しているため、実行ごとに構造が異なるという特性があります。このランダム性はシンプルさと効率を提供する一方で、性能のばらつきを生じる原因にもなります。一方で、平衡BSTは決定論的な構造を持ち、同じデータに対して同じ操作を行うと常に同じ結果を得ることができます。このような予測可能性は、システム全体の信頼性や安定性を向上させるため、特に堅牢性が求められるシステムにおいて重要です。

クエリ拡張性

平衡BSTは、最小値・最大値の検索、順序付き探索、範囲検索といった順序に基づく高度な操作を豊富にサポートしています。一方で、スキップリストはこれらのクエリ操作に対する拡張性が比較的乏しく、特定の範囲クエリなどには適しているものの、柔軟性に欠ける場面があります。そのため、複雑なクエリが必要なアプリケーションでは、BSTが適しているといえます。

並列処理対応

スキップリストは各ノードが独立したリンク構造を持つので、並列処理に適しています。BSTはツリー全体で再バランスが必要となるため、並列処理への対応が難しくなります。並列処理が必要となるケースではスキップリストが有利に立つケースが多いでしょう。

まとめ

スキップリストはそのシンプルさゆえ、実装しやすく、検索や挿入・削除操作が効率的に行える便利なデータ構造です。特に Redis のようなインメモリデータベースや、スピード重視のシステムで有用です。一方で、以下の理由から平衡BSTの方が一般的に採用されます：

  1. 時間計算量の保証（最悪ケースでO(\log{}n))
  2. メモリ効率の高さ
  3. ランダム性に依存しない予測可能な動作
  4. 豊富なクエリ拡張性

主観的なイメージですが、BSTとSkip Listの関係は、「プロのフルコース vs 家庭の定番料理」のようなものかなと思いました。BSTは厳しいコスト管理と細やかな調整を行い、常に100点の結果を提供します。一方で、Skip Listはシンプルなレシピと手軽な工程で、80点以上のおいしい料理を短時間で提供できる、そんな感覚です。

実務面では、ランダム性に依存する揺らぎをどこまで許容するかについてビジネスサイドとの折り合いが必要そうですが、選択肢の一つとして頭の中には入れておきたいと思いました。

参考

Discussion